11315 - Attacker

All about problems in Volume 113. 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
fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

11315 - Attacker

Post by fpavetic » Sun Oct 21, 2007 12:18 pm

can someone please give a hint or an idea for this problem?

my idea was to rotate the plane for 45 degrees but it didn't handle the boundary constraint ( it counted fields outside the chessboard as well )

Filip

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Oct 21, 2007 3:09 pm

Think about handling the white cells and black cells seperately.

But after that i dont know. AFAIK the NlogN solution (Klee's method) for Union of rectangle is too complex to code. And N^2 seems not to be feasible here! So i am not sure what to do from here!

If NlogN is the one that is to be used here, can any one please refer me to some site or send me his/her code?
Self judging is the best judging!

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Oct 22, 2007 10:50 am

I think line sweeping will help us.
Two intersecting rectangles will can always divide into three non intersecting ones. And non intersecting rectangles can be sorted by thier y value.

So let's sort rectangles by their X cordinate. Now we will hold examined rectanges in RBTree by their Y cordinnate.
Then two rectangles intersect we change them into three non rectangles.
When we examine second point of rectangle it is removed from the tree, we add his area to an answer.

It is just a guess, I do not have AC :)

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Oct 22, 2007 10:52 am

i think checking intersecting fact is going to take way more than N^2 in worst case!
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Tue Oct 23, 2007 6:21 am

well there is a problem with the union of rectangle procedure. note that some rectangle may get out of board. and in that case what to do? coz then only making union does not work!
Self judging is the best judging!

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Tue Oct 23, 2007 2:29 pm

shanto86 wrote:well there is a problem with the union of rectangle procedure. note that some rectangle may get out of board. and in that case what to do? coz then only making union does not work!
that is my problem as well :)

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Wed Oct 24, 2007 12:05 pm

See solution notes for "Soldiers" (identical problem) from the PKU POJ:

http://acm.pku.edu.cn/JudgeOnline/showc ... st_id=1251

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Wed Oct 24, 2007 12:11 pm

ya i saw that this morning, (some one gave the link at TC forum).

But how the judge says that the first part is easy to compute? To me the second part is easy to compute. And for the first part i cant think of other way than using NlgN union of rectangle! Now if the judge wants to say that NlgN computation is easy then i dont have anything to say!
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Wed Oct 24, 2007 2:47 pm

YUPPY!!!

GOT AC :)

My timing is, .890s. I am not sure, but you people may try it with N^2 algorithm.

My algorithm is: Computing the first part in NlgN.
Then doing the second part in also NlgN time.
Self judging is the best judging!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Oct 25, 2007 8:50 pm

i guess nlog n union of rectangle is considered to be easy in China.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Mon Dec 24, 2007 3:56 am

Hello, i have seen there is a called Bentley's algorithm to get the union of n rectangles in O ( n log n ) ... but i havent found any tutorial or source to read about it.... could anyone give me some link? or some hints, if the idea is not so difficult?, thanks. Eric.

Post Reply

Return to “Volume 113 (11300-11399)”