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?

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | Um_nik | 197 |

3 | YouKn0wWho | 192 |

4 | Errichto | 182 |

5 | sus | 181 |

6 | awoo | 180 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

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?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/25/2021 20:49:54 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

pls someone explain

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.

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

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.

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

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.

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

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:

You've got first number 2 so we start with this

onelike this: dp[0][2] = 1For 7 there is only

one2: (7+2)%10 = 9; (7*2)%10 = 4 => dp[1][9] = 1; dp[1][4] = 1.Now for 6 there is

one9 andone4: (6+9)%10 = 5; (6*9)%10 = 4; (6+4)%10 = 0; (6*4)%10 = 4 => so we've gotone5,two4s andone0 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).

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

do you know what the shift key does?

to walk in valorant so i dont reveal my position.

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