Educational CF Round 11

Educational CF Round 11 screen cast by eddy1021

Finish A,B,C in about 14 mins.

D is a tricky problem(in my opinion) with short description. Given 2000 points on the plane, count the number of parallelograms with the vertices at the given points. guarantee that no three of them lie on the same line. My solution was hacked during the open hacking phase. My solution is that take all segment from any two given points. Sort them with slope and length. For those with the same slope and length, choose two of them can form a parallelograms. For each parallelograms, it will be counted twice. My missing point is that when sort the slope, we should carefully take care of those with infiinite slope and those with negative delta x.

E is a nice problem. Define f(S) be the distinct subsequence of S, for all sequence S with length N consisting of number between 1 and M. Calculate the summation of f(S). The idea is that to calculate a subsequence occur in how many sequences. This can be done by dp. dp[i][j] is that for first i numbers already match j-th number of the concerned subsequence. Thus, we can directly compute the dp. Then, sum up all the subsequence with the same length at the same time.

F is also a good problem. Given a sequence with length 200000, you should choose a segment from it such that 1 times first element + 2 time second element ... is maximum. We can first compute out suffix sum s. Then make another suffix sum of suffix sum as u. Then, if we choose segment a[i..j) the answer will be u[i]-u[j]-(j-i)*s[j] = -u[j]-j*s[j] + i*s[j]+u[i]. Thus, we can iterate j from 1 to N with convex hull trick to maintain best i. Then, for each j, binary search the best i.

Didn't take good care of D. Lose the chance to gain the first place. Finally rank 21 on final standing.