Keyence Programming Contest 2020
Updated:
Source codesPermalink
SolutionsPermalink
A - PaintingPermalink
Flush (N+X−1)/X, where X=max(H,W).
B - Robot ArmsPermalink
Set Ii=[Xi−Li,Xi+Li). Then, this problem is typical. We sort {Ii} by the end of the interval and then the greedy algorithm works.
C - Subarray SumPermalink
Assume 0-indexed.
SolutionPermalink
Let d=S+1 if S<109 and d=1 if S=109. Then we set Ai as follows to get K sub-arrays whose sum is equal to S. Ai={Si<K,di≥K.
Further questionPermalink
We cannot construct {Ai} if K>N since all Ai are positive.
D - Swap and FlipPermalink
Assume 0-indexed.
ObservationPermalink
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],…. 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 1Permalink
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(2NN+(N N/2)NlogN).
Solution 2Permalink
We can solve this problem by simple brute-force method in O(N!)-time. This solution can be converted into DP.
DefinitionPermalink
For mask∈2N, for 0≤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∈mask and we have used V[index] last time, not having broken the ascending-order constraints.
AnswerPermalink
The answer is
A=mini∈NDP[2N−1][i].
If A=∞, flush -1
.
Initial StatePermalink
Instead of presenting empty ‘last-used’ index, we adopt N. Therefore the initial state is DP[0][N]=0; otherwise ∞.
TransitionPermalink
For all valid (mask,i), We want to execute the following form. DP[mask′][j]←min(DP[mask′][j],DP[mask][i]+d). Here j∉mask, mask′=mask∪{j} and d is the inversion number regarding j and mask. This is executed if and only if V[i]≤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 |mask|’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=∅ with i=N.
The time complexity will be O(2NN2), which is a little slower than Solution 1.