Codeforces Round 349

Codeforces Round 349 screen cast by eddy1021

First of all, the statements in this contest confusing me a lot. Thankfully, it didn't affect much.

A is a normal dp problem. Given a string, after canceling out first 5 character, divide the string remained into several substring such that each substring has 2 or 3 characters. For those substring, if there aren't any identical substring in a row , all of them are good. Find out all the good substring. We can solve it by dp. For dp[n] representing whether the suffix starting from n is good. Then, for each i, we can first check whether dp[i+2] is good and whether s[i,i+1] and s[i+2,i+3] are identical and check dp[i+5]. Similar process for length 3.

B is another normal graph problem. Given a directed graph with 3000 vertexs and 5000 edges, find all 4 different vertex a, b, c, d such that the sum of shortest path from a to b, then to c, then to d is maximum. We can BFS from all the vertex then obtain the shortest path for each vertex pair(Actually, I use dijkstra during the contest, which also passed). Then, for each b, c pair, we are going to find the best a and d to maximize the value. In order not to make a equivalent to c or d and also d, we should and only need to store the first 3 longest path ending at b and starting from c. Then, for each b, c pair, we can iterate all possible combination of a and d.

C is a good problem which I can't handle during the contest. Given a string S, there are 100000 query. For type 1 query, it will give another string to replace S. For type 2 query, given integer N up to 100000, you should count the number of string with length N which has S as a subsequence. The total length of input S will be up to 100000. First of all, the actually look of S doesn't matter. The answer only depends on N and length of S. Then, for fixed length M, we can construct following dp: dp[n] represent the number of distinct string with length n having S as subsequence. Then, dp[i]=0,for all i<M, dp[i]=C(i-1,M-1) * (25^(i-M))+26*dp[i-1]. First term is for the subsequence obtained until i-th character, while another one is that the subsequence is alreay obtained for first i-1 characters. Then, we can first compute all M<=some fixed K which cost O(K*maxN). For those given S which has length more than K, we directly recompute its dp value. Because total input length will be up to 100000, we only need to recompute at most O(100000/K) times. Thus, choose K=O(sqrt(N)), Then, we can solve it in O(N sqrt(N)).

D is just a case handling problem but only 9 solution passed the final test! Given 4 robots on XY coordinate, you should decide the direction(up, down, left, right) and the length of each robot to go such that the end points will be four corners of a square with non-zero area. The most important property is that both X-coordinate or both Y-coordinate of the resulting square will be the same as some of the given points. Thus, for each robots, we can iterate whether it's going to change its x-coordinate or y. Then, we can find some fixed x-coordinate or y's. If there are two fixed x's and two fixed y's, we directly get the resulting square and check whether it can actually be obtained. WLOG, If there are two fixed x's and one fixed y's, there may be two possible square, we can check both. WLOG, If there are two fixed x's, we iterate which two are going to be lower. Then, binary search the answer, we can obtain a range of possible lower y-coordinate of the square and take the intersection of two lower one's and also for higher. Then, we can fixed the side length D of square by the difference of fixed x-coordinate. Thus, we check whether the intersection of lower one shifted D and higher one is non-empty. Finally, choose the best answer among all the cases.

E is quite beautiful and difficult. Can't come up with a idea so far...

Wasting lots of time solving A,B because didn't notice the important information(in bold above), and thus, get a WA on B. And choose to solve D which take lots of time coding. But, at least pass all of them :).

rank 25 on final standing. Hope to achieve 2600 on the next one!