Re: help with a contest problem..

From: Dave (recneps.w.divad_at_elcaro.moc)
Date: 12/19/03 

Date: Fri, 19 Dec 2003 16:03:44 +0000

Bhaskara Aditya wrote:
> Hi everyone, I've tried to solve the foll problem.. but my program
> runs for more than the allowed time for the last of the 11 test cases
> in the problem. (in particular, for A=B=10000, N=1000, it takes too
> long.. not even close to the time limit of 5 sec). I basically tried
> the naive approach of going to each unit square, then incrementing the
> area of the last rectangle in the list containing it by 1, and so on..
> but it takes too long. Could anyone suggest a better algorithm??
>
> N opaque rectangles (1 <= N <= 1000) of various colors are placed on a
> white sheet of paper whose size is A wide by B long. The rectangles
> are put with their sides parallel to the sheet's borders. All
> rectangles fall within the borders of the sheet so that different
> figures of different colors will be seen.
>
> The coordinate system has its origin (0,0) at the sheet's lower left
> corner with axes parallel to the sheet's borders.
>
> PROGRAM NAME: rect1
> INPUT FORMAT
> The order of the input lines dictates the order of laying down the
> rectangles. The first input line is a rectangle "on the bottom". Line
> 1: A, B, and N, space separated (1 <= A,B <= 10,000)
> Lines 2-N+1: Five integers: llx, lly, urx, ury, color: the lower left
> coordinates and upper right coordinates of the rectangle whose color
> is `color' (1 <= color <= 2500) to be placed on the white sheet. The
> color 1 is the same color of white as the sheet upon which the
> rectangles are placed.
>
>
> SAMPLE INPUT (file rect1.in)
> 20 20 3
> 2 2 18 18 2
> 0 8 19 19 3
> 8 0 10 19 4
>
> OUTPUT FORMAT
> The output file should contain a list of all the colors that can be
> seen along with the total area of each color that can be seen (even if
> the regions of color are disjoint), ordered by increasing color. Do
> not display colors with no area.
> SAMPLE OUTPUT (file rect1.out)
> 1 91
> 2 84
> 3 187
> 4 38
>
> Thanks in advance for any help,
> Bhaskara Aditya.

What about the following:

an array A of 10k x 10k integers to indicate colours - big, but if your
computer has plenty of RAM this shouldn't be a problem. 16 bit colour
values would make this array take up 200MB. Also an array C of 2500
integers (large enough to hold up to 1e8 so probably 32 bit) to indicate
the number of squares of each colour that are visible.

Initialise A to white(1), and set number of white squares (C[1]) visible
to 1e8. Initialise all other colour counters (C[2]~C[2500]) to zero.
This represents what you can see at the start (i.e. after reading the
first line) - a massive expanse of white, and 1e8 white squares visible.

For each entry in the list, loop over the entries in A that represent
the squares covered by that rectangle. (So if you're looping over a 2x2
rectangle placed at (1,0) you might look at entries A[1][0], A[2][0],
A[1][1], A[2][1])

Inside that loop, see what colour is displayed, decrease the counter
for that colour by one, and increase the colour counter for the
rectangle being placed. (So if you're looking at A[1][1], and it is
already red, and the current rectangle being placed is blue, decrement
C[RED] and increment C[BLUE].)

And that's it. To get the final result just read off the contents of C,
and discard A.

Dave.

Relevant Pages

  • Re: Divide a rectangle (with cartesian coordinates) into equal
    ... squares and I need back each coordinates of this squares! ... whose are is half that of a given rectangle is pretty straightforward. ... If the question is to divide a given rectangle in half so it becomes to ... be no larger than delta. ...
    (comp.soft-sys.matlab)
  • Re: Shape Alignment Question
    ... When yo move a rectangle near anothe one it is magnetize to one of it edge ... Visio and are of various sizes. ... rectangle (area equals the total area of the squares) and then draw ... I overlay the squares on the rectangle one at a time. ...
    (microsoft.public.visio)
  • Re: Selecting and merging rectangles
    ... Say you have a grid of squares, ... Just compute the sum of the areas of the rectangles. ... are forming a new rectangle just exactly wide and tall enough to cover ...
    (comp.programming)
  • Re: Selecting and merging rectangles
    ... Say you have a grid of squares, ... selection forms a rectangle? ... rectilinear rectangle. ... Find the left most, top most, right most, and bottom most pixel ...
    (comp.programming)
  • Re: help with a contest problem..
    ... "Bhaskara Aditya" wrote in message ... I've tried to solve the foll problem.. ... so it makes more sense to work in 'rectangle world'. ... The only complication comes when there's only a partial overlap with a ...
    (comp.programming)