SPyofgame's blog

Can someone hint me on this problem
By SPyofgame, history, 5 years ago, In English

There is an empty rectangle of size

$$$n \times m$$$

where

$$$1 \leq n, m \leq 10^6$$$

We cover the rectangles k times from (u1, v1) to (u2, v2), where

$$$1 \leq k \leq 400$$$
$$$1 \leq u1 \leq u2 \leq n$$$
$$$1 \leq v1 \leq v2 \leq m$$$

The question is: How many squares of that rectangle have been covered ?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't try to find the state of the rectangle at the end, but rather count how many more squares have been covered after every operation considering all previous operations.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The 400 implies that it is a $$$O(n^3)$$$ solution, we should do something whith each one of the rects $$$n^2$$$ times.

How to find the contribution for the third rect?

Let $$$cells(r_i)$$$ be number of cells in ith rect. Then contribution of first rect equals $$$cells(r_1)$$$. Second is $$$cells(r_2)-cells(intersection(r_1, r_2))$$$

Then it gets interesting. Third is $$$cells(r_3) - cells(intersection(r_3, r_1)) - cells(intersection(r_2, r_1)) + cells(intersection(r_3, r_2))$$$

So, it turns out adding a next rect is adding an intersection of the new rect and all previusly existing rects (and the intersections of them).

Be careful to give every rect a proper sign to know if the number of intersection cells must be added or subtracted.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I accidentally read the title of this blog as can someone hit me with this problem

→ Reply