10869 - Brownie Points II

BiK · 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 · 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 · 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 ?!

Cho · 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;".