### nskybytskyi's blog

By nskybytskyi, 3 years ago,

CF seems to be the most reasonable place to post about AtCoder, as there are no blogs on AtCoder itself, so here we go.

Short text editorial:

A. If $10^N = A \cdot M^2 + B \cdot M + C$ then answer is $B$, and it remains to compute $10^N \pmod{M^2}$ with binary exponentiation.

B. Cards form a graph. Connected components can be optimized independently. We can take all vertices from a component iff it is not the tree. Otherwise, we can take all vertices but one.

C. Every permutation is a product of cycles. Process people in the increasing order of weight. Every cycle (and hence the entire permutation) will be resolved optimally unless you ran into smth that makes overall permutation impossible.

D. If c[u] > c[v] then we must have u -> v as all vertices reachable from v are also reachable from u. The rest of the graph can be oriented arbitrarily, as long as each connected component of the remaining graph stays strongly connected. One way to do it is to run a series of DFSs.

• +43

 » 3 years ago, # |   -8 In A why can we write ${10^N}$ = ${A * M^2 + B*M + C}$?
•  » » 3 years ago, # ^ |   +15 First, dividing $10^N$ by $M^2$ with a remainder, we get $10^N = A \cdot M^2 + D$. Then dividing $D$ by $M$ with a remainder, we get $D = B \cdot M + C$. Combining, we get $10^N = A \cdot M^2 + B \cdot M + C$.
•  » » » 3 years ago, # ^ |   +13 got it...I think you have basically represented it in base M
•  » » » » 3 years ago, # ^ |   0 Yes, but without higher powers than $M^2$, as these do not matter.
•  » » » » 3 years ago, # ^ |   0 That's a nice way to look at it