G - 01Sequence Editorial by en_translator
Define a sequence \(B=(B_0,B_1,\dots,B_N)\).
\(B_i\) is the number of 0’s contained in \(A_1,A_2,\dots,A_i\).
The conditions is rephrased as follows.
\(K_i\) or more
1’s are contained in \(A_{L_i},A_{L_i+1},\dots,A_{R_i}\)
\(R_i-L_i+1-X_i\) or less0’s are contained in \(\Leftrightarrow A_{L_i},A_{L_i+1},\dots,A_{R_i}\) に0が \(R_i-L_i+1-X_i\)
\(\Leftrightarrow B_{R_i}-B_{L_i-1} \leq R_i-L_i+1-X_i. \cdots (1)\)
Also, it holds that
\(B_i \leq B_{i+1}\cdots (2)\)
\(B_{i+1} \leq B_i +1 \cdots (3)\)
\(B_0=0. \cdots (4)\)
It is trivial to reconstruct \(A\) from \(B\) satisfying all \((1),(2),(3),(4)\), and \(A\) satisfies all the given conditions (except that we have to minimize the number of 1).
Therefore, the problem is boiled down to the problem to find \(B\) that satisfies all \((1),(2),(3),(4)\) that maximizes \(B_N\).
This is so-called a “cow game”.
What is a “cow game”?
Given are some number of constraints of the form \(d_j-d_i \leq w_{ij}\).
Find the maximum \(d_T-d_S\).
This problem can be boiled down to a shortest path problem. This technique is called “cow game” in Japan.
(Translator’s note: the term “cow game” originates to POJ 3169 - Layout, in which you are asked to line up cows under given constraints and maximize the distance between the first and the last cows. The problem is introduced in Japanese competitive programming’s bible “Programming Contest Challenging Book”, and that is why many people refer to it like this.)
Specifically, define a graph with \(N+1\) vertices numbered Vertex \(0\), Vertex \(1\), \(dotes\), Vertex \(N\); add the following edges:
\((1)\): edges from Vertex \(L_i-1\) to \(R_i\) with cost \(R_i-L_i+1-X_i \)
\((2)\): edges from Vertex \(i-1\) to \(i\) with cost \(0\)
\((3)\): edges from Vertex \(i\) to \(i+1\) with cost \(1\)
finally, find the shortest distance from Vertex \(0\), then \(B\) is obtained.
Since all edges have non-negative cost, we can use Dijkstra’s algorithm, which is fast enough.
posted:
last update: