MikeMirzayanov's blog

Internet-version of the Southern (Saratov) Subregional Contest (NEERC) 2013
By MikeMirzayanov, 11 years ago, translation, In English

Hello,

Did you already notice that this Sunday it will be Internet-version of 2013-2014 ACM-ICPC, NEERC, Southern Subregional Contest? It will start on 07:00 (UTC).

The contest will be held in Gym. I invite teams mostly because the contest was designed as a team contest.

I'm sure this contest is a great way to train before coming regional (or subregional for some of you) ACM-ICPC contest.

  • Vote: I like it
  • +80
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this be the same as today's Timus?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Nope. On Timus was the quarterfinal of Eastern subregional of NEERC. Tomorrow will be the quarterfinal of South subregional of NEERC

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. They do other Subregional Contest.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem B, F, K ?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 7   Vote: I like it +9 Vote: I do not like it

    Problem B: Move the camera lazily to the nearest good position in every step. You can find the nearest good position in each step by doing f.ex. binary search on the array C.

    Problem F: You can write the solution of the expected value as such:

    where .

    and t[i] represents the time when i-th testcase will be processed.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your reply. I have done the same thing for Problem B. Here is my submission: http://pastie.org/8434448

      Getting WA on test #6 , can you tell me why ?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        double low = pos[i] — 1.0*r; double hi = pos[i] + 1.0*r;

        I think these are incorrect. You should use Pythagoras' theorem here.

        r2 = 12 + D2 (where D is the distance you need to add/subtract from pos[i]).

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          damn !! my code was correct , just that was the issue. :(

          Thanks.. :)

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell me what kind of test is #6 in B? this is my code. .

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's interesting in problem L that : It is guaranteed that there will be no overow of the 32-bit signed integer type, so feel free to use type int (in C++ or Java) to store the number of dollars and shares.

but I use "int64" got ac ,"int" got WA...

Is it a evil trick?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I used int ( 32 bit signed) got AC. Maybe you have other problem.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got same issue as you. Just changed my variables to long and got AC. Bizarre o_O

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    If it helps :

    if(d - (inc * a) * p[i] >= 0){

    This is the line where the overflow is happening for you, looks like for the test case 17(first one, at least), inc * a * p[i] is out of int range. I think most people have written the check if(d/p[i] - inc * a >= 0 ) {

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem K : Wrong answer on test 9. Any Critical input please !!!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My code for problem H gets WA on testcase #55! Does anybody know that testcase or can spot my mistake? My code

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For this case 5 <<<<><<<< you got -1, but the answer should be abcdeabcde.

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

11/6 Finally got it. Sort of. It took about 80min to generate the answers for n=6, which I then hardcoded, so I'm wondering what the intended solution was.

============

EDIT: Well, I decided to test more for J, and I see that I clearly get things wrong, time to fix... (4 2 != 2 4)

I seem to be quite hasty in my conclusions.

============

I'm suspicious of the judge for problem J. I get WA on test case 10, and through testing the judge, this is the first case which relies on the modulus. I've changed the modulus and still get AC up to test case 10, so I suspect that the judge code used a different modulus than the problem statement.

Alternatively, it could be some small case that I get wrong regardless, but I've verified that my program correctly solves n=1, for any m, and perhaps also for n=2, any m.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

I'm getting WA at test case 32 at problem I. Any help...

/* in the name of ALLAH, most gracious, most merciful */

using namespace std;

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

#define forab(i, a, b)	for (__typeof (b) i = (a), i##_b = (b); i <= i##_b; ++i)
#define rep(i, n)		forab (i, 0, (n) - 1)

#define pb				push_back

typedef long long int64;
const int MAX_N = int (5e3) + 7;

struct pc {
    int64 type, capacity, idx;
    pc () {}
    pc (int64 _type, int64 _capacity, int64 _idx) : type (_type), capacity (_capacity), idx (_idx) {}
    bool operator <  (const pc &rhs) const {
        if (capacity == rhs.capacity) type > rhs.type;
        return capacity < rhs.capacity;
    }
    bool operator == (const pc &rhs) const {
        if (type == rhs.type && capacity == rhs.capacity && idx == rhs.idx) return true;
        return false;
    }
} arr [MAX_N], s [MAX_N];

vector <pc> v;

int main () {
#ifdef Local
	freopen ("input.txt", "r", stdin);
	// freopen ("output.txt", "w", stdout);
#endif
    int64 n, a, b;
    pc identity = pc (-1, -1, -1);

    cin >> n >> a >> b;
    rep (i, n) {
        int64 t, w;
        cin >> t >> w;
        arr [i] = pc (t, w, i);
    }

    sort (arr, arr + n);
    rep (i, a + b) s [i] = identity;

    int64 _a  = 0;
    int64 _b  = 0;
    int64 cnt = 0;
    int64 sum = 0;

    rep (i, n) {
        if (_a + _b + cnt >= a + b) break;
        if (arr [i].type == 1) {
            if (_a >= a) continue;
            s [_a] = arr [i];
            sum += arr [i].capacity;
            ++_a;
        } else if (arr [i].type == 2) {
            if (_b >= b) continue;
            s [a + _b] = arr [i];
            sum += arr [i].capacity;
            ++_b;
        } else {
            v.pb (arr [i]);
            sum += arr [i].capacity;
            ++cnt;
        }
    }

    cout << _a + _b + cnt << " " << sum << endl;
    int idx = 0;
    for (int i = 0; i < a + b && idx < cnt; ++i) if (s [i] == identity) s [i] = v [idx++];

    rep (i, a + b) {
        if (s [i] == identity) continue;
        cout << s [i].idx + 1 << " " << i + 1 << endl;
    }
    return 0;
}
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Each of a and b can be up to 5000, so you need to double the size of s. By the way, you’re missing a return keyword in operator <, but you don’t actually need that line anyway.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any plan to organize Internet-version NEERC 2013?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It will be published as a training in Gym as soon as jury will publish tests.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is there any editorial for this contest?

      → Reply