Codeforces Round #180 (Div. 2) 解题报告

题目链接

A.Snow Footprints

A - Snow Footprints

The starting position can be anywhere with a footprint. The footprints can be categorized into 3 types.

1. only L s
2. only R s
3. 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

B - Sail

We can simply move by greedy method — only moves when it takes the boat closer to the destination.

C - Parity Game

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 cannot increase anymore

If 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

The idea is to make a copy of 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.

Finally, remove the remain 'old part' of a. Now we get b.

Combine all those fact, we can conclude that we can turn a into b if and only if

countOnes(a) + parity(countOnes(a)) ≥ countOnes(b)

D - Fish Weight

If 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 large enough to make Alice wins.

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.

Lets assume 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 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.

We will make an example with 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.