nskybytskyi's blog

By nskybytskyi, 4 years ago, In English

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.

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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$$$.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      got it...I think you have basically represented it in base M

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, but without higher powers than $$$M^2$$$, as these do not matter.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's a nice way to look at it