10613 - Mushroom Misery

All about problems in Volume 106. 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
pminkov
New poster
Posts: 8
Joined: Wed Oct 17, 2001 2:00 am
Location: Bulgaria, Sofia

10613 - Mushroom Misery

Post by pminkov » Thu Feb 26, 2004 1:56 pm

Can anyone please give me some test cases for this problem,
I keep getting WA, although I think I handle all special cases.

Petko Minkov

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Fri Apr 16, 2004 8:41 am

Just this:

Input:
1
1 1
0 0 40

Output:
1

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Mon May 10, 2004 7:14 pm

Hello,

I have totally stucked with this problem. The only solution I could think of, is to cover the circles with rectangles, and then solve simpler problem with rectangles in O(N log N) (N is number of rectangles).

We can trivially cover one circle with 2*r rectangles (r is circle radius) , horizontal or vertical stripes, but that's too much (r can be 1000000). It's not difficult to cover circle with something like 1+(4-2*sqrt(2))*r rectangles (just inscribe largest possible square, and cover the rest with stripes) But that seems still to much.

Could somebody give me some hint? Thank you.

Marian

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

Post by Adrian Kuegel » Mon May 10, 2004 7:21 pm

I used divide and conquer to solve this problem.

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Mon May 10, 2004 10:26 pm

OK, now I'm ashamed. It's sort of school algorithm :-? I got accepted. Thank you very much for your hint.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Tue May 11, 2004 4:41 pm

Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!
JongMan @ Yonsei

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue May 11, 2004 4:58 pm

Whinii F. wrote:Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!
You just divide ALL area onto parts and parts onto smaller parts and so on.
You should stop when size of area is 1 square meter or when no one circle intersect your area.
All you need on each step you should check all circles.
I check if area completely covered by some circle as well (for speed purposes).
I've got AC.
Thanks Adrian.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Fri May 21, 2004 4:38 am

marian wrote: I have totally stucked with this problem. The only solution I could think of, is to cover the circles with rectangles, and then solve simpler problem with rectangles in O(N log N) (N is number of rectangles).
Sorry, I have one question.
How to cover the circles with some proper rectangles?
Any bettor method?
Please give some hints, thx

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Post by Miguel Angel » Sun May 23, 2004 11:45 pm

I think it's possible to make the circles just as 2 rectangles (like making a cross) and then solve with NlogN.
:D Miguel & Marina :D

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon May 24, 2004 5:23 am

Miguel Angel wrote:I think it's possible to make the circles just as 2 rectangles (like making a cross) and then solve with NlogN.
I thought it is possible.
But how to find the two rectangles.
First I can find an big rectangle to cover the circle.
Let rectangle represent as (left,up,right,down)
I could find a rectange (floor(x-r),ceil(y+r),ceil(x+r),floor(y-r)) to cover the circle.
But the four corners maybe not used.
Many special cases should be considered.
Would someone give better method to represent the circle? Thx :D

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Post by Miguel Angel » Thu Jun 03, 2004 11:04 pm

Yeap, well if you think it as a big square first, is hard for sure..But you may agree the following, in the big square you can fit two rectangles of with w and height h, making a cross and covering the whole circle. If don't believe me, let's suppose it exist, if exist those 2 rectangles cross in 4 points..each point is at 45
:D Miguel & Marina :D

fennec
New poster
Posts: 4
Joined: Thu Jul 29, 2004 12:18 pm

WAing...

Post by fennec » Thu Oct 21, 2004 2:34 pm

I change each circle to two rectangles, and use O(n*log(n)) to solve it, but I got wa :( , Could some one give me some special Input&Output?
TKS

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: WAing...

Post by windows2k » Fri Oct 22, 2004 8:25 am

fennec wrote:I change each circle to two rectangles, and use O(n*log(n)) to solve it, but I got wa :( , Could some one give me some special Input&Output?
TKS
Maybe it needs more rectangle to represent a circle.

fennec
New poster
Posts: 4
Joined: Thu Jul 29, 2004 12:18 pm

ths,I will try

Post by fennec » Mon Oct 25, 2004 5:08 am

But just in my alg, I first found the 45 degree points, and use floor and ceil to deal with them separately, so can you give me an example to show my fault , Tks:)

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:

Post by Margarita » Fri Feb 17, 2006 7:37 pm

rotoZOOM wrote: You just divide ALL area onto parts and parts onto smaller parts and so on.
You should stop when size of area is 1 square meter or when no one circle intersect your area.
All you need on each step you should check all circles.
I check if area completely covered by some circle as well (for speed purposes).
I used the same method but & got TLE. I divide all area in 4 parts, check if this part is covered by circle or, on the contrary, if it's not intersected and does not contains circle. i thought i made all optinizations but still got TLE :'(

Post Reply

Return to “Volume 106 (10600-10699)”