Application of difference array for overlapping glass-tint problem

Question

For this problem, I heard that using a difference array can solve the problem but I can't seem to figure out how to solve this problem. Could anyone give me some advice? Please keep it simple since I am only a high school student preparing for the national infomatics Olympiad.

Given an array of numbers, we can construct a new array by replacing each element by the difference between itself and the previous element, except for the first element, which we simply ignore. This is called the difference array, because it contains the first differences of the original array. We will denote the difference array of array A by D(A). For example, the difference array of A = [9, 2, 6, 3, 1, 5, 0, 7] is D(A) = [2-9, 6-2, 3-6, 1-3, 5-1, 0-5, 7-0], or [-7, 4, -3, -2, 4, -5, 7]. Source

I've found a solution in Python , but I can't understand it.

Canadian Computing Competition: 2014 Stage 1, Senior #4:

You are laying N rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.

You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the x-axis or the y-axis (that is, there are no "diagonal" pieces of glass).

You would like to know the total area of the finished stained glass window with a tint-factor of at least T.

Input Specification:

The first line of input is the integer $N$ ($1\leq N\leq 10^3$), the number of pieces of glass. The second line of input is the integer $T$ ($1\leq T\leq 10^9$), the threshold for the tint-factor. Each of the next $N$ lines contain five integers, representing the position of the top-left and bottom-right corners of the $i$-th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order $x_1$ $y_1$ $x_2$ $y_2$ $t$, where the top-left corner is at $(x_1,y_1)$ and the bottom-right corner is at $(x_2,y_2)$, and tint-factor is $t$. You can assume that $1\leq t\leq 10^6$. The top-most, left-most coordinate where glass can be placed is $(0,0)$ and you may assume $0\leq x_1<x_2\leq K$ and $0<y_1<y_2\leq K$, and ...

Output Specification: Output the total area of the finished stained glass window which has a tint-factor of at least $T$.

I have an implementation but I'm not quite sure how it works. Any explanation would be greatly appreciated.

Answer 1

First, I will look at this problem from a more (high-level) theoretical perspective and then go through the details required in an implementation, based on the solution you linked to.

---

Given all the rectangles, we can divide the area in rectangular portions such that every portion is rectangular and all points in the same portion intersect the same set of rectangles. An division of the example input in rectangular portions can be seen below:

Our task is to identify the rectangular portions of glass that have at least the required tint $T$. To do this, it is necessary that we iterate in some manner over all these rectangular portions to determine their tint. It is also sufficient: the portions are determined by considering all rectangles they intersect, at which point we can inspect their tint. So, we can create an algorithm that solves this problem in $O(R)$, where $R$ is the number rectangular portions and this is (asymptotically) the best we can do.

But how big can $R$ become? If we have some collection of rectangular portions of the intersection of $i$ rectangles and add a new rectangle, we create one new portions for each portion that is intersected by one of the four edges of the new rectangle. So how many portions can intersect the same horizontal line? At most $2i-1$, since the same horizontal line can be intersected by at most $2$ vertical lines for every rectangle added (apart from the first). So, after adding all rectangles, we get $R\leq \sum_{i=1}^N 4\cdot (2i-1) = O(N^2)$.

So, our algorithm will run in $O(N^2)$. Given that $N\leq 10^3$, it should be fast enough if we implement it efficiently.

---

But implementing this efficiently could be rather tricky. Sure, it's easy to say that you can just add rectangles and create new portions as a result of their intersection, but that would be pretty cumbersome to implement and possibly inefficient.

This is where the 'difference array' approach comes in. The principle is slightly easier to explain with a 1D-array, so we will restrict the problem to that for now. Suppose we have input

x1 x2 t
11 20 1
13 14 2
17 18 1
12 19 1

So, we can draw it like this:

The array $A$ contains the tint values over all contiguous 'rectangles' in 1d, which is what we need. The array $dA$ is the difference array of $A$. Observe that this difference array can be easily found: after sorting the endpoints of our 'rectangles', we add the tint-value of the rectangle on the left side (when 'entering' the rectangle) and subtract it on the right side (when we 'leave' the rectangle). After we found are difference array $dA$, we can compute $A$ by noting that $A[i] = \sum_{j=1}^n dA[j]$. Then, we scan $A$ to find the areas that have tint $\geq T$ and add the area to our final value and we're done.

For 2D arrays, we do exactly the same thing, but now with an extra dimension to keep track of.

---

Let me make a final remark: it is in general very hard to 1. reconstruct an algorithm from an implementation and 2. understand an implementation of an algorithm without understanding the algorithm. Therefore, just inspecting source code to understand an algorithm is generally a hopeless task. In this case, I could only understand the implementation in this source after I understood the explanation.