Educational CF Round 8

Educational CF Round 8 screen cast by eddy1021

Finish A,B, and C in about 11 mins.

D is a trivial dp problem. Call a number d-magic when all its even-th digits are d and others are not. Given two equal length decimal integer a and b. You should find the number of integers within [a,b] which is d-magic and also a multiple of a given m. We can first calculate (0,b] then subtract by the answer of (0,a] and check a whether satisfy the condition. For calculating the answer of (0,n], the dp state is that dp[2][x][y] is the number of d-magic number with first x digits which module m is y and whether it is now bounded. Bounded is that whether we can freely choose next digit such that the resulting integer will not exceed n.

E is a very interesting problem. Given a n x m table containing only 'z' and '.', you should find there are now many "Z-pattern". When a k x k subtable with the cells of first and last row and anti-diagonal are all 'z', we call it is a "Z-pattern". Checking a anti-diagonal isn't a easy way. Thus, we maintain first and last row of that "Z-pattern" and calculate the answer by sliding through the anti-diagonal. When sliding through the anti-diagonal from up to down, we are wondering how many row are suitable for this row as last row. Thus, we first dp how many continuous 'z' for each cell in left and right hand side which denoting as dpl[i][j] and dpr[i][j]. Then, for the cell we are concerning call (a,b), we know those cell with the column number withn [b,b+dpr[a][b]-1] will take effect. And for those cell denoted as (x,y), they will actually take effect if and only if y-dpl[x][y]+1<=b. Therefore, we can use a set to maintain those cell would take effect so far and use a segment tree to find how many cells are still existing within [b,b+dpr[a][b]-1]. Time complexity will be O(NM log M).

F isn't a easy problem. I just handle some cases. Although accepted during contest time, hacked after just several hours. The solution is flow which will be clear if take a deep look at each condition. The condition is a from of that you can just pick exactly k numbers from interval [a,b].

Rank 6 on final standing. Not bad but F is solvable if I take a more look.