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. L
2. R
3. R s followed by L

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

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)

​​D - Fish Weight​​

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 a_i > b_i

 If for every i, a_i ≤ b_i, 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 a_i > b_i. We can amplify the gap between w_ai and w_bi

​​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, s_i ≥ 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 a_i = i (do not care values of b)

i = 10... 19:  assign b_i = i (do not care values of a)

i = 20... 29:  assign b_i = 29 - i. a takes the remains. From i = 20, a will have strictly increasing values starting from at least 11.