mac_n_cheese_pog's blog

can someone explain this editorial
By mac_n_cheese_pog, history, 3 years ago, In English

https://atcoder.jp/contests/abc220/editorial/2703

on the recent atcoder round,i find problem D not very intuitive.can someone explain the editorial even more?

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

Comments Comments (10)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

First, we can show that the dp state encapsulates all necessary information by noting that any operation can only change the beginning of the array (we remove from the beginning, and add to the beginning). So if we know how many elements have been removed, and what the number added was, we can infer that the elements after will just be the rest of the array.

Now you can think of the problem as follows: at each step, there are 10 possible arrays (where the first element is anything from 0 to 9). So for each of these 10 arrays, we can simulate the two operations to effectively reach an array in the next step. For example, if there are 12 ways to reach the array 4 5 6, then that contributes 12 ways to reach 9 6 and 12 ways to reach 0 6. Hopefully the editorial's explanation of the dp transition from there makes sense.

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

    why is dp[i][j]=1 when j=ai

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

      When you start, you only have one element, namely $$$A_1$$$. The number of ways to get $$$A_1$$$ with the last element being $$$j$$$ is $$$1$$$ if $$$j=A_1$$$ (because then the last element is $$$A_1$$$) and $$$0$$$ otherwise.

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

        im sorry i dont really understand.what do u mean to get a1 we need a1 in the previous?

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

          If you understand the DP relation, then the initial values immediately follow. Since dp[i][j] is the number of ways to perform i steps and reach a first element equal to j, then dp[0][j] can only be 1 if the first element is already equal to j (since you've performed 0 steps). So dp[0][a1] = 1, and the rest of dp[0][j] is set to 0. The editorial changes the definition of the dp state slightly so that the initial state has index 1, but the idea is the same.

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

            ok i dont understand.its really hard to visualize it.thanks for ur effort tho.dp truly sucks.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              ← Rev. 4   Vote: I like it 0 Vote: I do not like it

              Nope, this is easy to visualize dp. It's just you, thinking that everybody here solve problems in their mind, and then code. Nope, it's often hard to solve first problem on topics. So we use pan and paper a lot. I too thought everybody solve in their minds, before I saw top solvers during streams stumble upon some unknown problem, and took out their pen and paper.

              For the testcase in poblem dp-table looks like this:

              i\j 01234567890
---------------
2   00100000000 
7   00001000001 
6   10002100000
...

              You've got first number 2 so we start with this one like this: dp[0][2] = 1

              For 7 there is only one 2: (7+2)%10 = 9; (7*2)%10 = 4 => dp[1][9] = 1; dp[1][4] = 1.

              Now for 6 there is one 9 and one 4: (6+9)%10 = 5; (6*9)%10 = 4; (6+4)%10 = 0; (6*4)%10 = 4 => so we've got one 5, two 4s and one 0 after 6. => dp[2][0] = 1; dp[2][4] = 1+1; dp[2][5] = 1.

              With every new number quantity dobles, but every i-th number is compared (with * and +) only to 10 previous dp[i-1][0...9] (of which nine are zero at begining, so we skip them on paper, but algorithm check them anyway).

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

do you know what the shift key does?

→ Reply