10771 - Barbarian tribes

[Adrian Kuegel]

I wonder why this problem had a time limit of 6 seconds, if a O(n log n) solution gives TLE ( n was <=2000 !!! ). So it seems they only wanted to allow the constant time solution ( http://www.cse.iitd.ernet.in/~suban/cs1 ... node1.html ). But with a time limit of 1 second and n <= 1000000000 this would have been much clearer, and avoids that the judge becomes busy judging a lot of too slow programs.

[Per]

Perhaps it was a trick to make people believe that Omega(n) solutions would work, though I tend to think it was just negligence.
The time limits for the other problems also seemed a bit higher than necessary, though E was the only problem where this became an issue because of the vast amount of TLEs.

By the way, I think this (E) was an absolutely brilliant problem! One of the best I've seen in months, in my opinion.

[w k]

In problem 10771 my solution used as much as 388 kb of memory. Other solutions in ranklist use only 64kb. Since I used only 3 int variables in the code, I guess that the problem is related to the input reading method. I simply used scanf(). Could anybody explain why I need 388kb despite I use 3 variables only and how to read inputs with efficiency similar to scanf() and reduce the size of used memory at the same time?

Wojciech

[CDiMa]

In problem 10771 my solution used as much as 388 kb of memory. Other solutions in ranklist use only 64kb. Since I used only 3 int variables in the code, I guess that the problem is related to the input reading method. I simply used scanf(). Could anybody explain why I need 388kb despite I use 3 variables only and how to read inputs with efficiency similar to scanf() and reduce the size of used memory at the same time?

Wojciech

Programs with fast run times often get 64kb of memory usage regardless of the real memory usage.
Probably if you submit your program a couple of times you will get a 64kb solution too

Ciao!!!

Claudio

[w k]

Claudio,

You're right. After 3rd submission I've got 64 kb!

Anyway - strange.

Wojciech

[..]

Could anyone give me the proof why does the answer only depend on the parity of m?

[Cho]

In every two sacrifices, there are three possible cases:
1. 1 G and 1 K are sacrificed, 1 K is placed.
2. 2 G are sacrificed, 1 G is placed.
3. 2 K are sacrificed, 1 G is placed.
In any case, the parity of K doesn't change. So the initial parity of K is the same as the final parity of K.

[..]

I see, thanks

[Shaka_RDR]

i got TLE for this problem...
i use simple simulation (with modulus of course). First i stored the data into an array and then start simulating.
are the judge's test cases very big so that my program can get TLE ? any help will be appreciate thanx a lot before

[Larry]

Yes, they can get very big. Use what ".." said as hint..

[Shaka_RDR]

oh, i see why i got a TLE now... thanx a lot... being idle from uva for about 1 and a half year sure makes my brain working very very slow now
i'll try to fix my code now

[Shaka_RDR]

WOW !!! i got AC now .... thanx a lot
i must take a warming up for my brain by solving easy problem first before i try to solve more difficult problem

[DD]

The parity trick works like a charm However, even with that, I still cannot get 0.00 A.C. Just curious how other people solve this problem?