10869 - Brownie Points II

All about problems in Volume 108. 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
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

10869 - Brownie Points II

Post by BiK » Wed Jul 06, 2005 2:35 pm

The n^2 algorithm most probably won't do. Is there a n*log(n) algorithm for this problem?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Jul 06, 2005 11:28 pm

Yes. More precisely, the authors had both an O(N log N) and an O(N sqrt N) algorithm implemented. Keep on thinking, don't give up :)

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK » Sat Nov 26, 2005 7:32 am

I don't see how Stan can achieve a 7 for the sample test. For every vertical line he chooses, Olie can push him below 7 ?!

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

Post by Cho » Sat Nov 26, 2005 7:20 pm

Maybe you missed this sentence from the problem statement:
Then Ollie places a horizontal line that must cross a brownie point already crossed by the vertical line.
If Stan places the line x=0, Ollie has to place the line y=0.
Then, Stan gets 7 points and Ollies gets 3 points.
If Stan places the line x=2, Ollie has to place the line y=-2.
Then, Stan gets 7 points and Ollies gets 2 points.
So the output is "Stan: 7; Ollie: 2 3;".

Post Reply

Return to “Volume 108 (10800-10899)”