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

Автор mac_n_cheese_pog, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
              Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

do you know what the shift key does?