atcoder_official's blog

UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372) Announcement
By atcoder_official, history, 3 months ago, In English

We will hold UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372).

We are looking forward to your participation!

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

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Anyone else feel it is much harder to gain rating in ABC 372? F is not an easy problem and over 800+ participants pass?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It's 581, not 800+, default standings include non-rated participants too. Seems fine for F + if you get the idea it's pretty easy to implement.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey can anyone explain how to solve problem F.

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

    https://atcoder.jp/contests/abc372/editorial

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

      hey thanks but I wasn't able to understand it completely.

      I understand that dp[i][v] can be computed from dp[i-1][v-1], where i is the number of moves and v is the vertex but what about the other m edges and how to compute it efficiently.

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

        M is rather small, you can straight up calculate dp on top of small subgraph where vertices are only ones that are present in M edges.

        → Reply