PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
MEDIUM
PREREQUISITES:
Prefix sums, Dynamic programming
EXPLANATION:
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
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),
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)
Hence, we get
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
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).
SOLUTION:
The author’s solution can be found here .