The starting position can be anywhere with a footprint. The footprints can be categorized into 3 types.
- only L s
- only R s
- R s followed by L s
In case 1, we end in the left of all footprints. In case 2, we end in the right of all footprints. In case 3, we either end in the rightmost R or the leftmost L
We can simply move by greedy method — only moves when it takes the boat closer to the destination.
Obv 1: If a has odd parity, we can apply operation 1 to increase its number of 1s by 1.
Obv 2: If a has even parity, its number of 1s cannot increase anymore.
Claim: If the number of 1s in a is not fewer than those in b, we can always turn a to b
The idea is to make a copy of b at the right of a. Lets assume a starts with even parity. If we need a 0, simply apply operation 1. If we need a 1, keep remove from the head until we removed an 1. Notice that we never remove digits from 'new part' of a. Now the parity of a will be odd and we can apply operation 1. After that, the parity of a becomes even again, the number of 1 in the 'old part' of a decrease by 1 and we handle a 1 in b. Finally, remove the remaining old part of a and we get b.
Combine all those facts, we can conclude that we can turn a into b if and only if
First we sort a and b in non-increasing order. We claim that the answer is YES if and only if exists a is lexicographically larger than b.
If a is not lexicographcally larger than b, that means for every i, ai ≤ bi. That implies for every fish Alice has, there is a corresponding fish Bob has and is as heavy as Alice's.
Let i be the smallest index such that ai > bi. We can amplify the gap between wai and wbi as large as we want to make Alice wins.
297C - Splitting the Uniqueness
An equivalent definition for almost unique, is an array with at least ⌊ 2n / 3⌋ different elements. The idea is to split s into three parts: In the first part, we give uniqueness to a. In the second part, we give uniqueness to b. In the third part, we give uniqueness to both.
Lets assume s is sorted. Since s is an unique array, we know si ≥ i for all i (0-based). The image below will give some intuition on how we are going to split it. a is red, b is blue, the length of the bar represent the magnitude of the number. In the first and second part, we do not care about the array that we are not giving uniqueness to.
For exampmle, if n = 30:
i = 0... 9: assign ai = i (do not care values of b)
i = 10... 19: assign bi = i (do not care values of a)
i = 20... 29: assign bi = 29 - i and set ai = si - bi. From i = 20, a will have strictly increasing values starting from at least 11.
For k = 1 there is only one coloring so we just need to check the number of = constraints. When k ≥ 2, it turns out that using only 2 colors is always sufficient to satisfy at least 3 / 4 of the constraints.
Lets assume w ≥ h (rotate if not). We will call the constraints that involves cells in different row "vertical constraints", and similar for "horizontal constraints".
First we color the first row such that all horizontal constraints in row 1 are satisfied. We will color the remaining rows one by one.
To color row i, first we color it such that all horizontal constraints in row i are satisfied. Then consider the vertical constraints between row i and row i - 1. Count the number of satisfied and unsatisfied vertical constraints. If there are more unsatisfied constraints than satisfied constraints, flip the coloring of row i. Flipping a row means turning 2211212 → 1122121, for example.
If we flip the coloring of row i, all horizontal constraints in row i are still satisfied, but for the vertical constraints between row i and row i - 1, satisfied will turn to unsatisfied, unsatisfied will turn to satisfied. Therefore, we can always satisfy at least half the vertical constraints between row i and row i - 1.
The number of unsatisfied constraints is at most (h - 1) × ⌊ w / 2⌋, which is at most 1 / 4 of the total number of constraints (recall w ≥ h).
Problem and editorial written by AEtheReal. Link to editorial.
