MikeMirzayanov's blog

By MikeMirzayanov, 12 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

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

Will this be the same as today's Timus?

»
12 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

How to solve problem B, F, K ?

»
12 years ago, hide # |
 
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?

  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    12 years ago, hide # ^ |
     
    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

  • »
    »
    12 years ago, hide # ^ |
    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 ) {

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

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

»
12 years ago, hide # |
 
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

»
12 years ago, hide # |
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.

»
12 years ago, hide # |
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;
}
  • »
    »
    12 years ago, hide # ^ |
    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.

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

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