372

Revision en3, by meeeep, 2016-09-17 20:37:25

For what it's worth, here is a possible way of solving the questions of CF 372 Div 2, possibly with mistakes (since I only coded 3/5).

A - From the last timing, keep proceeding until you hit a gap of more than c seconds. Count how many steps you took. (and possibly +1)

B - For each substring of length 26, it is valid if and only if it does not already contain 2 of the same letter.

So firstly, we loop through all such substrings and using a boolean array of size 26 check which letters have been used. If no letter that has been used appears again, then the substring is fine, and we have found a place where we can insert a nice substring.

For those 26 positions, insert in place of the ?s any letter that has not yet been used.

For anything else, insert your favourite letter.

If the initial string has length <26 or you could not find a substring position that could possibly be nice, print -1 and exit. Else, print out the string with the ?s filled in.

C - One way of doing it is to add until the number is (L*(L+1))^2 before taking the squareroot. We can verify that for level 1 this takes 2 moves and otherwise it takes L*(L*L+L)-1 moves.

D - Since we are only interested whether a path of length L exists between s and t, an edge of weight L+1 is as good as infinity.

Consider the case where all erased edges are 1. Find the pairwise distance of any two points a and b. Call this d1(_a_, b). This can be accomplished using Dijkstra, for example.

Consider the case where all erased edges are L+1. Find the pairwise distance of any two points a and b. Call this d2(_a_, b).

If d1(_s_, t)>L, then there is no solution. Similarly, if d2(_s_, t)<L, there is no solution. Otherwise, if we hypothetically increased random erased edges' costs by 1, one edge at a time, then each step increases d1(_s_, t) by either 0 or 1, so we will definitely pass by L at some point, and it is possible.

So we just need to increase the weights of erased edges not on the path giving d1(_s_, t) to L+1 and increase the weights of those that are until the length of the path is exactly L, subject to not increasing costs of erased edges by more than d2(start, end) of the edge.

E - Let the multiplicative inverse of 10 mod M be N. If we head towards the node, read the number in base 10. Else read it base N. It can be proven that a path is valid if and only if the left and right paths are negatives modulo M.

Consider the center of the tree. Say we wish to count the number of paths passing through it. Find all residue classes modulo M of paths that lead towards it and those that lead away from it. In total, there are at most 200k such classes. For each pair of classes (1 towards and 1 away) with correspondingly negative values mod M, add the product of their sizes. This counts all legitimate paths, but overcounts those which double back on themselves. For each branch, we simply have to subtract those away.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English meeeep 2016-09-18 01:56:35 254
en3 English meeeep 2016-09-17 20:37:25 6 Tiny change: ' of CF 372, possibl' -> ' of CF 372 Div 2, possibl'
en2 English meeeep 2016-09-17 20:26:38 723
en1 English meeeep 2016-09-17 20:17:10 2263 Initial revision (published)