10771 - Barbarian tribes

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

10771 - Barbarian tribes

Post by Adrian Kuegel » Sat Nov 06, 2004 8:22 pm

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.
Reason: thread title

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sat Nov 06, 2004 9:26 pm

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

Post by w k » Mon Nov 08, 2004 9:57 pm

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

Post by CDiMa » Tue Nov 09, 2004 11:15 am

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 8)

Ciao!!!

Claudio

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Wed Nov 10, 2004 10:52 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

Post by .. » Thu Nov 18, 2004 7:14 pm

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Nov 18, 2004 7:58 pm

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

Post by .. » Thu Nov 18, 2004 8:40 pm

I see, thanks :D
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Wed Jun 01, 2005 4:49 pm

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 :D thanx a lot before :D
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:

Post by Larry » Wed Jun 01, 2005 6:42 pm

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

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Thu Jun 02, 2005 7:06 am

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 :D
i'll try to fix my code now :D
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...

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Thu Jun 02, 2005 7:38 am

WOW !!! i got AC now .... thanx a lot :wink:
i must take a warming up for my brain by solving easy problem first before i try to solve more difficult problem :D
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

Post by DD » Fri Mar 01, 2013 9:59 pm

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.

Post Reply

Return to “Volume 107 (10700-10799)”