题目链接
The starting position can be anywhere with a footprint. The footprints can be categorized into 3 types.
- L
- R
- R s followed by L
R or the leftmost L
We can simply move by greedy method — only moves when it takes the boat closer to the destination.
Fact 0: If a has odd parity, we can apply operation 1 to increase its number of 1 by 1.
Fact 1: If a has a even parity, its number of 1
a has parity 0, unless we pop a 1, otherwise we cannot write a new 1 into a.
Fact 2: If the number of 1 in a is not less than the one in b, we can always turn a to b
b at the right of a. Lets assume a has even parity now. If we need a 0, simply apply operation 1. If we need a 1, keep remove from head until we remove a 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.
a. Now we get b.
a into b
countOnes(a) + parity(countOnes(a)) ≥ countOnes(b)
n > m, set every weight to 1 and done. Otherwise, lets sort a and b in non-increasing order, and trim the last part of b such that its length equals a.
Claim: answer is YES if and only if exists i such that ai > bi
If for every i, ai ≤ bi, that means for every Alice's fish, there is a correspond Bob's fish which is as heavy as Alice's.
Let i be the smallest one such that ai > bi. We can amplify the gap between wai and wbi
E - Splitting the Uniqueness
An equivalent definition for almost unique, is arrays 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.
s is sorted. Since s is an unique array, si ≥ i for all i (0-based). The image below will give some intuition on how to split it. ais red, b
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. a takes the remains. From i = 20, a will have strictly increasing values starting from at least 11.