## 10771 - Barbarian tribes

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 10771 - Barbarian tribes

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.
Last edited by brianfry713 on Wed Sep 10, 2014 10:00 pm, edited 2 times in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

### Memory size

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: Memory size

w k wrote: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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Claudio,

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

Anyway - strange.

Wojciech

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 10771 - Barbarian Tribes

Could anyone give me the proof why does the answer only depend on the parity of m?
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I see, thanks
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
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
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Yes, they can get very big. Use what ".." said as hint..

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
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
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
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
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10771 - Barbarian Tribes

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?
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.