Блог пользователя nskybytskyi

Автор nskybytskyi, 4 года назад, По-английски

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

Problems, my solutions, YT video.

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In A why can we write $$${10^N}$$$ = $$${A * M^2 + B*M + C}$$$?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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$$$.