nrg_aceu's blog

By nrg_aceu, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

pls someone explain

»
4 weeks 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.

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

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

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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?

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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).

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

                why does it feel like bruteforce.i know dp is similar to bruteforce but i feel like dp is overkilling(based on what i read from ur solution).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

do you know what the shift key does?

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

    to walk in valorant so i dont reveal my position.

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

      At this point I can't even tell if you're trolling.