## 10869 - Brownie Points II

Moderator: Board moderators

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

### 10869 - Brownie Points II

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