Codeforces Round 405

Codeforces Round 405 screen cast by eddy1021

A is an interesting implementation problem. Given n, k and (n-k+1)s Yes/No, you should construct a sequence of string s.t if i-th one is Yes, strings among [i,i+k-1] should be pairwise distince. Otherwise, strings among [i,i+k-1] should at least exist a identical string pair.
We just put k-1 distinct strings for first k-1 strings. If i-th one is Yes, set (i+k-1)-th string distinct with previous k-1 ones. If i-th one is No, set (i+k-1)-th string same with (i-2)-th one.
During contest, I stuck with some index problem for about 3 or 4 mins...

B is a classical problem. Given a tree, you should find the sum of distance among all pair of vertices. Specially, distance here is the ceiling of their actual distance divided by k on the tree.
We just need group up all the distance with the same remainder respect to k. Then, merge two subtree can be done in O(k^2). Actually, just store sum of floor of distance and deal with the extra 1 when merging or adding to answer.

C is an very interesting problem. Given a string composed of uppercase letter, you should find the minimum number of swap between adjacent character s.t. there's no substring as "VK".
There are only three type of characters 'V', 'K', other. Then, we can come up with a DP as dp[n][v][k][3] denoting that for first n characters with have put vs 'V' and ks 'K' as the last character is 'V' or 'K' or others. Then, the cost of next character will be the number of inversion when it's put into n+1 character. The cost can be calculated out in O(N) or O(\lg N). Thus, time complexity can be O(N^3 \lg N)

Still can't get D...

E is a geometry problem. Given N vertices on 2D-plane, you should find the area of region where first vertex can be moved to s.t. the sign of cross value before and after moved for every three vertices remains the same.
If first vertex is collinear with any other two vertices, the area 0. Otherwise, for every other two vertices, first vertex should be in the same half plane. Thus, we need to find out the area bounded by all the half plane. Actually, for each vertex we just need to find the other most close to first vertex in its direction. This can be done by sorting all the vertices respect to the angular to first vertex. And the closest one may also be the next vertex in the sorted array. Thus, total number of useful half plane is O(N).
During contest, I almost solved it. Wasting too much time on C....

rank 43 on final standing. Need to improve more!