Help With USACO Problem

cypressx · Post by **cypressx** » Sun Jul 04, 2004 1:35 pm

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 · Post by **anupam** » Mon Jul 05, 2004 3:37 pm

Hello, I am also sufferer for the problem. and, so posted in another thread. Watch it and help.

cypressx · Post by **cypressx** » Mon Jul 05, 2004 6:06 pm

Ok. Thanks

mbakht · Post by **mbakht** » Thu Jul 08, 2004 6:29 pm

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

anupam · Post by **anupam** » Fri Jul 09, 2004 3:04 pm

Well Mehdi bhai, tried in that way. But, MLE and the other is TLE. Now, trying by sorting the coordinates.

allornothing · Post by **allornothing** » Sat Jul 10, 2004 11:57 am

Sorry, I don't know what's MLE, TLE mean?
I also stuck in this problem

Can you give me some hint?
Thank you.

Dominik Michniewski · Post by **Dominik Michniewski** » Sat Jul 10, 2004 1:52 pm

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

Best regards
DM

yaro · Post by **yaro** » Sat Jul 10, 2004 9:01 pm

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 · Post by **yaro** » Fri Jul 16, 2004 5:14 pm

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

anupam · Post by **anupam** » Sat Jul 17, 2004 6:33 pm

Please describe more..

cypressx · Post by **cypressx** » Mon Jul 26, 2004 12:46 am

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 · Post by **yaro** » Mon Jul 26, 2004 6:32 pm

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 · Post by **cypressx** » Mon Jul 26, 2004 9:00 pm

Thank you very much yaro

Minilek · Post by **Minilek** » Thu Jul 29, 2004 3:09 am

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.

OJ Board

Help With USACO Problem

Help With USACO Problem

Idea

Thanks

Easier algorithm