### nrg_aceu's blog

By nrg_aceu, history, 4 weeks ago,

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

• +23

 » 4 weeks ago, # |   0 pls someone explain
 » 4 weeks ago, # | ← 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.
•  » » 4 weeks ago, # ^ |   0 why is dp[i][j]=1 when j=ai
•  » » » 4 weeks ago, # ^ |   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.
•  » » » » 4 weeks ago, # ^ |   0 im sorry i dont really understand.what do u mean to get a1 we need a1 in the previous?
•  » » » » » 4 weeks ago, # ^ |   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.
•  » » » » » » 4 weeks ago, # ^ |   0 ok i dont understand.its really hard to visualize it.thanks for ur effort tho.dp truly sucks.
•  » » » » » » » 4 weeks ago, # ^ | ← 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] = 1For 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, # ^ |   0 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, # |   0 do you know what the shift key does?
•  » » 4 weeks ago, # ^ |   0 to walk in valorant so i dont reveal my position.
•  » » » 4 weeks ago, # ^ |   +3 At this point I can't even tell if you're trolling.