Help With USACO Problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Help With USACO Problem

Post by cypressx »

Hello . I want to ask you for some idea for one usaco problem. It is called Shaping Regions. It is a Chapter 2 problem. If you can give some idea please do it . Thank you very much . ( I am a newbie in the forum and my english is not so good - sorry ! )

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Hello, I am also sufferer for the problem. and, so posted in another thread. Watch it and help.
"Everything should be made simple, but not always simpler"

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx »

Ok. Thanks :)

mbakht
New poster
Posts: 16
Joined: Fri Feb 28, 2003 7:54 pm
Location: Bangladesh
Contact:

Post by mbakht »

Take a recursive approach. Approach the problem from backwards (at least that is what I did).

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Well Mehdi bhai, tried in that way. But, MLE and the other is TLE. Now, trying by sorting the coordinates.:-)
"Everything should be made simple, but not always simpler"

allornothing
New poster
Posts: 4
Joined: Thu Jul 08, 2004 3:13 pm

Post by allornothing »

Sorry, I don't know what's MLE, TLE mean?
I also stuck in this problem 8)
Can you give me some hint?
Thank you.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

MLE - memory limit exceeded
TLE - time limit exceeded
RTE - run-time error (crash)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro »

Hi,

I think in this problem you have to create some kind of sweeping (at the moment I'm thinking about that :). It's similar to calculating common area of rectangles, if you perform that counting colors will be easy.

yaro

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro »

Yes, sweeping worked out. My algorithm runs in O(n^2*lg n) time and it passed all tests.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Please describe more..
"Everything should be made simple, but not always simpler"

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Idea

Post by cypressx »

Is it is possible for someone who passed this USACO problem to post the USACO analysis ? I mean only the analysis of the algorithm , no - source . Thank you

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro »

My algorithm works something like that:
I sort rectangles' edges ('opening' and 'closing' edges) by x-coordinate. Then I start to sweep from left to right - for every event (edge parallel to y axis) I count the area (and also the colors) of rectangles which intersect or cover this event and next event (some of them may not intersect next event). The problem is to calculate that area between two events, you have to use some kind of interval tree or structure which give you possibilty to add new interval in O(log n) time. 'Interval' is the height of rectangle and its y coordinates.
If one rectangle is 'higher' (abstract - contains the problem statement) than another then you have to erase all intervals its intersect from your structure. After you have added all the intervals you only need to count the colors. Thus running all that costs you O (n^2*log n) time - n*2 events * n*log n interval addings.

Maybe it'll help.

Cheers,
yaro

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Thanks

Post by cypressx »

Thank you very much yaro :-)

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Easier algorithm

Post by Minilek »

yaro's algorithm works in n^2lgn, but there is an algorithm that is easier to code which works in n^3 (which is still good enough for the test cases). basically note that everytime you put a new rectangle on top, it intersects each rectangle to make at most 4 new rectangles. so just loop through adding each rectangle and checking which of the 4 u can make for each intersection.

Post Reply

Return to “Algorithms”