MEGAMU1 - Editorial


Contest - Division 3
Contest - Division 2
Contest - Division 1




Prefix sums, Dynamic programming


Let f(x) := [x \text{ is special}] and let us try to attack the problem for a generic f. So, we want to find the function \mu such that \sum_{y\le x} \mu(y) = f(x).
By studying the behavior of \mu for small N, one can come up with the following lemma.

Lemma: It holds the identity

\mu(x) = \sum_{0\le b_i\le 1} (-1)^{\sum b_i} f(x-b) .

Proof: We prove the identity by induction on x (for example with respect to the sum of the entries of x). By definition of \mu and using the identity for y<x (which we can take for granted in the inductive step for x),

\mu(x) = f(x) - \sum_{y\le x, y\not=x} \mu(y) = f(x) - \sum_{y\le x, y\not=x} \sum_{b\le 1} (-1)^b f(y-b)
= f(x) - \sum_{z\le x} f(z)\sum_{b\le 1,\ b\le x-z, b\not= x-z} (-1)^b .\hspace{5em}

Let us focus on the sum \sum_{b\le 1,\ b\le x-z, b\not= x-z} (-1)^b .
If x_i-z_i\ge 2 for some 1\le i\le N, then the sum is zero. Otherwise, let S=\{i: x_i-z_i = 1\}. One can check that we have (the set T contains the indexes i so that b_i=1)

\sum_{b\le 1,\ b\le x-z, b\not= x-z} (-1)^b = \sum_{T\subsetneq S} (-1)^{|T|} = [S=\emptyset] - (-1)^{|S|}
= [x=z] - (-1)^{\sum x_i-z_i}.\hspace{-5em}

Hence, we get

\mu(x) = f(x) - \sum_{x-1\le z\le x} f(z) \Big([x=z]-(-1)^{\sum x_i-z_i}\Big)
= \sum_{0\le b\le 1} (-1)^{\sum b_i} f(x-b),\hspace{6em}

which is exactly what we wanted to prove.

Now that we have a clean formula for \mu, it remains to solve the problem. Since the formula for \mu contains 2^N terms, it is unfeasible to compute all contributions.
To overcome this issue, we employ a dynamic programming approach. The idea is to iterate over 1\le n\le N and to keep track of the last nonzero value of x-b.

Given 1\le n\le N, let x^{(n)} be the n-uple (x_1, x_2,\dots, x_n).
Given an n-uple (y_1, y_2,\dots, y_n), let g(y) be the value of the last entry which is positive and 0 if y\le 0. For any 1\le n\le N and for certain values q\ge 1 (which will be clear later on), we compute

F(n, q) := \sum_{0\le b_i\le 1, g(x^{(n)}-b)=q} (-1)^b f(x^{(n)}-b) .

It is not hard to see that F(n, q)=0 for all values of q but at most 3. Moreover F(n, q) can be computed in O(1) if one knows F(n-1, q') for all q'. The precise definition of f is important only in these last steps, namely it is important that, for an n-uple y=(y_1,y_2,\dots,y_n), the value of f(y) depends only on f(y^{(n-1)}), y_n and g(y^{(n-1)}).

Overall, we will compute F(n, q) for O(N) values of n and, for each value of n, we will consider O(1) values of q; hence the total number of states is O(n). Since the transition requires O(1) operations, the overall complexity is O(n).


The author’s solution can be found here .

1 Like

@infinitepro, could you please add more details to the editorial?

1 Like