F - Domination Editorial by evima


We consider just the red stones that have no other red stones to the upper right. Without loss of generality, we assume \(RX_1<RX_2<\cdots<RX_N\) and \(RY_1>RY_2>\cdots>RY_N\).

First, for a given placement of blue stones, the following two conditions are equivalent.

  • There are \(K\) or more blue stones to the upper right of each red stone.

  • It is possible to divide the blue stones into \(K\) groups so that every group has a blue stone to the upper right of each red stone.

It is obvious that the latter implies the former. We can prove that the former implies the latter by induction, considering the fact that the set of red stones covered by each blue stone forms an interval.

Next, we consider the way to solve the problem for the case \(K=1\).

Let us first consider the cost to cover the red stones \([l,r]\) for some given \(1\leq l \leq r \leq N\). We will reduce it to the following problem:

  • Consider a token that can move along the \(X\)- and \(Y\)-axes. Along the \(X\)-axis, the cost of moving by \(1\) in the positive/negative direction is \(1/0\). Along the \(Y\)-axis, the cost of moving by \(1\) in the positive/negative direction is \(0/1\). Additionally, for each blue stone \(j\), it can jump from the point \((0, BY_j)\) along the \(Y\) axis to the point \((BX_j, 0)\) along the \(X\) axis, for no cost. Then, the smallest cost needed to get from \((0, RY_l)\) to \((RX_r, 0)\) is the cost to cover the red stones \([l,r]\).

It is obvious that this reduction is valid.

Here, for each \(1 \leq i \leq N-1\), let us span an edge of cost \(0\) from \((RX_i, 0)\) to \((0, RY_{i+1})\). We can see that the shortest route from \(RY_1\) to \(RX_N\) will then answer the problem for the case \(K=1\).

For a general \(K\), we can simply find the minimum cost to send a flow of amount \(K\) in the same graph. Here, only the edges corresponding to the blue stones have the capacity of \(1\). The validity of this follows from the equivalent condition we stated in the beginning.

The total complexity of our solution is \(O(K(N+M)\log (N+M))\).

posted:
last update: