dragoon's blog

Atcoder: ARC 61 Problem F
By dragoon, history, 8 years ago, In English

Can anyone please explain the analysis to problem F? Unfortunately this time the editorial is in japanese.

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

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Consider the sequence of cards that will be taken until the end of the game. For example, if n = 5, m = 4, k = 6 then it can look like:

           V these cards weren't revealed, so they could be chosen arbitrarly
bcaabacccaaXXXX
          ^ after this card Alice wins

Alice wins if the sequence consists of exactly n a's, no more than m b's and no more than k c's. Let's say there are s b's and c's totally. The rest of cards may be chosen with 3m + k - s ways, and the revealed cards may be chosen with ways where f(s) is the number of strings consisting of s characters a and b in total from which no more than m are a's and no more than k are b's.

It's easy to see that

If we draw a Pascal Triangle, this is a section of rectangle (0, 0) — (m, k) with a diagonal line that looks like a segment consisting of binomial coefficients with fixed first argument. There is no closed form for such sum, but it's easy to see thath f(s + 1) is almost equal to 2f(s), you only need to carefully consider O(1) binomial coefficients at the border. So, the solution is: calculate using DP the function f(s + 1) = 2f(s) + [O(1) binomial, 2016 - 09 - 12 coefficients], and then output the answer . Binomial coefficients may be calculated in O(1) if we precompute all factorials. Overall complexity is O(n + m + k).

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain problem E also..

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

    I have not solved the problem but it seems plain dijkstra. The state is: (node, color). Even though there may be many node's and many color's but, number of interesting (node, color) pair is not more than number of edges.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Not Dijkstra but BFS, actually, since all edge lengths are 0/1.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Can you please elaborate the solution a little..

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          First, find connected components of railway lines. Two railway lines are in the same connected components if they belong to the same company and they are connected through rails of this company.

          Then, construct a bipartite graph. The vertices on the left correspond to stations. The vertices on the right correspond to connected components. Add an edge between a left vertex and a right vertex if the station is incident to one of the rails in the connected component.

          The solution is (the shortest path in this bipartite graph) / 2.

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

            Can you please explain how finding the shortest path in the constructed bipartite graph would be equivalent to finding shortest path between nodes 1 to n.

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

              All the vertices of the original graph are on the left and components of the edges on the right. Moving from 1 vertex to another (on the left side) passes over two edges in the bipartite graph but is of actual cost 1 in the original graph (hence we divide by 2). Also each such movement (left->right->left) is equivalent to changing the edge-component (or rather changing the company whose edge you are travelling on in the original graph which incurs a cost of 1). This is precisely what you are asked to minimize.

              → Reply