Keyence Programming Contest 2020
Updated:
Source codes
Solutions
A - Painting
Flush $(N + X - 1) / X$, where $X = \max(H, W)$.
B - Robot Arms
Set $I _ i = [X _ i - L _ i, X _ i + L _ i)$. Then, this problem is typical. We sort $\{ I _ i \}$ by the end of the interval and then the greedy algorithm works.
C - Subarray Sum
Assume $0$-indexed.
Solution
Let $d = S + 1$ if $S < 10 ^ 9$ and $d = 1$ if $S = 10 ^ 9$. Then we set $A _ i$ as follows to get $K$ sub-arrays whose sum is equal to $S$.
\[
A _ i =
\begin{cases}
S & i < K, \\
d & i \geq K.
\end{cases}
\]
Further question
We cannot construct $\{ A _ i \}$ if $K > N$ since all $A _ i$ are positive.
D - Swap and Flip
Assume $0$-indexed.
Observation
We use $V[i]$ to denote the $i$-th card. To simplify the manipulation, first we swap the red side and the blue side on each $V[1], V[3], \dots$. Then we see that our problem is equivalent to the following problem.
Suppose that we arrange the order of $V$. We adopt the number of the $i$-th card on the red side if $i$ is even and on the blue side otherwise. Are the cards in the ascending order?
Solution 1
We can separate two sequence, that is, the red sequence and the blue sequence. We try all the possibilities. First, we decide which cards are in the red sequence ($N - N / 2$ items). We sort the red sequence and the blue sequence separately and merge these sequences. If the final result is in the ascending order, this manipulation is doable. The number of the swaps is the inversion number which is easily calculated by BIT or Segment Tree.
We have to care for the same-number problem. To reach the minimum manipulation, we have to do tie breaks by the index of card if its value is same.
The time complexity will be \[ O \left(2 ^ N N + \begin{pmatrix} N \\\ N / 2 \end{pmatrix} N \log N \right). \]
Solution 2
We can solve this problem by simple brute-force method in $O(N!)$-time. This solution can be converted into DP.
Definition
For $mask \in 2 ^ N$, for $0 \leq index < N$, we define as follows.
$DP[mask][index] =$ the minimum number of manipulation where we have already put the cards $V[i]$ in $i \in mask$ and we have used $V[index]$ last time, not having broken the ascending-order constraints.
Answer
The answer is
\[
A = \min _ {i \in N} DP[2 ^ N - 1][i].
\]
If $A = \infty$, flush -1.
Initial State
Instead of presenting empty ‘last-used’ index, we adopt $N$. Therefore the initial state is $DP[0][N] = 0$; otherwise $\infty$.
Transition
For all valid $(mask, i)$, We want to execute the following form. \[ DP[mask’][j] \gets \min(DP[mask’][j], DP[mask][i] + d). \] Here $j \not \in mask$, $mask’ = mask \cup \{ j \}$ and $d$ is the inversion number regarding $j$ and $mask$. This is executed if and only if $V[i] \leq V[j]$ holds in terms of either the red side or the blue side determined by their places.
In the normal DP, we use simple for-loops. But in this problem it does not work. Then, how can we visit all valid $(mask, i)$ in valid order? We can guarantee the validness by BFS. This is because $\lvert mask \rvert$’s ascending order must be one of the valid orders as long as the answer is not -1.
Also, be careful for the case $mask = \emptyset$ with $i = N$.
The time complexity will be $O \left(2 ^ N N^2 \right)$, which is a little slower than Solution 1.