Codeforces #418 Div2

Finally, another China Round 😛 Solved A to C during the contest, and fail to submit problem D

A. An abandoned sentiment from past

We are required to use elements from B to replace zeros in A, to form an array that is not increasing. First, since all elements are unique, if the zero number is more than 2, there must be a solution. If we can form an increasing array but replace more or equal than 2 zeros. We can exchange them to form a valid one. So, what we need do is check if there are only one zero if it is valid.

 

B. An express train to reveries

You are given two different arrays which are both an element different from a permutation.  You are asked to compute the original permutation. Since there are only one element different, so if there are different in the same position, we can just check which number is missing. Otherwise, we are choosing a number from two in each two positions. I used next_permutation and check to solve this problem.

 

C. An impassioned circulation of affection

You are required to compute the longest segment of the array, after modify at most k numbers. There are  2*10^5 queries and the max number of the array is less than 27.  So we can use a prefix array to store how much steps we need to do to make the array from 1 to i are all the same. Then we use a binary search to find the answer.  The overall complexity is O(NQlogN+N*color)

 

D. An overnight dance in discotheque

Give you N circles, and you need to divide them into two categories. And you are asked to calculate the maximum sum of xor-sum of these circles. Since there are only 2000 circles, so we can easily build the tree with brute force. Then the greedy strategy is that divide all the son of root to another category, and others remain the same. The complexity is O(N^2). It is noticeable that we can do this problem in O(NlogN) complexity with scanning lines and use a balanced tree to maintain them.

 

E. An unavoidable detour for home

This problem is rather interesting to think, but boring to code. I think the original editorial is clearly enough. Carefully classification, and then do the normal DP. There are total 10 situations.