CROC 2016 Elimination Round

CROC 2016 Elimination Round screen cast by eddy1021

A wrong try on A. Push me one step away from rank 4.

B is just a greedy problem. For a list from 1 to N, you can perform at most k swap to make most inversions. Just greedy swap 1st and last one, then second and second last one, and so on. Then, we can calculate the inversion with BIT or segment tree in O(N lg N). Another solution is to calculate the expression of the answer since the outlook of sequence is simple.

C is a normal problem. Given a string consisting of '0' and '1', you should pick exactly (k+1)'s '0' and choose one of them such that the maximum distance from those '0' to the chosen one is minimum. We will only pick consecutive (k+1)'s '0'. And then, we can binary search that we are going to choose. Or just take the one(or check two of them) most near the middle.

D is a interesting problem. Given a list of results of matches, you should determine until which match we can know the rank for each one. Just binary search the answer, and check whether we can know each one's rank by topological sort.

E is a nice problem. Given a string of length N consisting of first k letters, you should append M characters from first k letters such that the numebr of distinct subsequence is most. Considering the dp of calculating distince subsequence, dp state is that dp[i] is the number of distinct subsequence ended exactly at i-th character. Then, dp[i] will equal dp[i-1]+dp[i-2]+...+dp[k] where k is the last one character equivalent to i-th or 0(if i-th character appears first time). Then, we can compute psum[i] as the prefix sum of dp value. Thus, this dp transition can be done in O(N). Therefore, we want to maximize the number of distinct subsequence is equal to maximize psum[N+M] or to maximize each dp[i]. Hence, from dp[N+1] to dp[N+M], we always choose the one appear earlier or the one never appears.

F is a beautiful problem. Given n numbers, k and q numbers, you should add those q numbers one by one into the multiset of n and compute the summation of g.c.d. of each subset with cardinalty equals to k. The idea is that we always consider the influence of the one we are adding. Then, we can iterate each divisor of it and count how many number is its multiplier. And, we can calculate the number of such subset by C(#,k-1). Then, with inclusion and exclusion method, we can find exact number of each divisor.

Solving first five problems in about 40 mins, and finish F in also about 40 mins. With 2 hacks on B, rank 5 on final standing. Best performance so far and get a big jump on rating! Hope to keep enhancing myself!