### Romok007's blog

By Romok007, history, 6 months ago, ,

Hello everyone. I am really stuck at this problem, can you please provide a solution? Problem Link : Overlapping Boxes. Thanks in advance :).

Problem Source : TCS Mockvita 2

• -9

 » 6 months ago, # | ← Rev. 2 →   +3 SolutionLet's move across the x-axis from 0 to $MAX_X = 1e4$ and maintain the values of the $x$-th coloumn from the grid. We need to recalculate it efficiently using the $x-1$-th coloumn somehow. If there is no rectangle having $x$ as a leftmost or rightmost point, its clear that $x$-th coloumn is equal to the $x-1$-th one. Otherwise there are two possible types of actions for $x$: - $x$ is the rightmost coordinate of the rectangle - $x$ is the leftmost coordinate of the rectange For each action of the first type we need to decrease values in the appropriate range by the appropriate cost value. And for the second type actions we need to increase the values in the same way. To do in efficiently you can construct a preffix array for that values and then add it to the $x-1$-th coloumn and that is — you've got an $x$-th coloumn. Then just update the maximum and its count. Complexity is $O(MAX_X * MAX_Y + N)$ Here is my brief implementation https://ideone.com/82XDr3 . There might be some bugs, but anyway it can help you understand the idea.
•  » » 6 months ago, # ^ |   0 Thank you so much for helping out with such an elaborate solution :).