Programming challenges

[bugzpodder]

right, and by moves you want the number of exhanges

2
2
1
3
3
3
2
3
1

exchange the first two 2s with 1s

1
1
2
3
3
3
2
3
2
then exchange the first two 3s with the last two 2s to get 4 moves

[Martin]

So just quicksort....

[Martin]

Oh nevermind. I get stuff...I'm just slow.

[czar]

The closed fences problem seems to be a real pain. I can verify whether a fence is valid. I am just not sure how to verify whether an edge is visible or not.

[thegoose]

Here is a one that I found somewhere (I really don't recall where, I might just have made it up):

You have N (1<N<1,000,000) rectangles on the plane defined by their lower left and upper right cordinates (sides of the rectangle are parallel to the x and y axis). Calculate the total area they cover (count overlaps only once).

Input Details
Line 1: number of rectangles
Line 2~N+1: 4 numberes per line, the x,y values for the lower left and upper right points.

Output Details:
One number, on a line by itself, the total area that the rectangles cover.

Sample Input
2
0 0 4 4
2 2 6 6

Sample Output:
28

NOTICE THE LARGE NUMBER FOR THE MAX VALUE OF N

[zylum]

what are the largest inputs for the coordinates?

[thegoose]

The solving algorithm works for real numbers of any size(as long as you can store them), but to make it a bit less tedious in the coding, make the cordinates integers from 0 to 1,000,000. (you should not use more than 16MB of memory)

[wtd]

Martin wrote:

I'm not getting the IOI one.

They just want you to sort the list in the least number of moves, and give them that number?

Sounds like it.

It wouldn't appear to limit the amount of work you do, just the number of exchanges.