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 »

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 »

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 »

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 »

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 »

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. »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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)”