Page 1 of 1
Help With USACO Problem
Posted: Sun Jul 04, 2004 1:35 pm
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 ! )
Posted: Mon Jul 05, 2004 3:37 pm
by anupam
Hello, I am also sufferer for the problem. and, so posted in another thread. Watch it and help.
Posted: Mon Jul 05, 2004 6:06 pm
by cypressx
Ok. Thanks
Posted: Thu Jul 08, 2004 6:29 pm
by mbakht
Take a recursive approach. Approach the problem from backwards (at least that is what I did).
Posted: Fri Jul 09, 2004 3:04 pm
by anupam
Well Mehdi bhai, tried in that way. But, MLE and the other is TLE. Now, trying by sorting the coordinates.
Posted: Sat Jul 10, 2004 11:57 am
by allornothing
Sorry, I don't know what's MLE, TLE mean?
I also stuck in this problem
Can you give me some hint?
Thank you.
Posted: Sat Jul 10, 2004 1:52 pm
by Dominik Michniewski
MLE - memory limit exceeded
TLE - time limit exceeded
RTE - run-time error (crash)
Best regards
DM
Posted: Sat Jul 10, 2004 9:01 pm
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
Posted: Fri Jul 16, 2004 5:14 pm
by yaro
Yes, sweeping worked out. My algorithm runs in O(n^2*lg n) time and it passed all tests.
Posted: Sat Jul 17, 2004 6:33 pm
by anupam
Please describe more..
Idea
Posted: Mon Jul 26, 2004 12:46 am
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
Posted: Mon Jul 26, 2004 6:32 pm
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
Thanks
Posted: Mon Jul 26, 2004 9:00 pm
by cypressx
Thank you very much yaro
Easier algorithm
Posted: Thu Jul 29, 2004 3:09 am
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.