1567.md (3217B)
1 Source: https://codeforces.com/blog/entry/94581 2 3 Thank you for participating in our contest! We hope you enjoyed it. **UPD:** Implementations have been added. 4 5 [1567A - Domino Disaster](/contest/1567/problem/A "Codeforces Round 742 (Div. 2)") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Implementation (C++)** 12 13 [127991325](/contest/1567/submission/127991325 "Submission 127991325 by flamestorm") 14 15 **Video Solution** 16 17 [Link to Video](https://www.youtube.com/watch?v=czwX-f9ifvk) 18 19 [1567B - MEXor Mixup](/contest/1567/problem/B "Codeforces Round 742 (Div. 2)") 20 21 **Solution** 22 23 Tutorial is loading... 24 25 **Implementation (C++)** 26 27 [127991329](/contest/1567/submission/127991329 "Submission 127991329 by flamestorm") 28 29 **Video Solution** 30 31 [Link to Video](https://www.youtube.com/watch?v=8h5loLSCkyQ) 32 33 [1567C - Carrying Conundrum](/contest/1567/problem/C "Codeforces Round 742 (Div. 2)") 34 35 **Solution (Observation)** 36 37 Tutorial is loading... 38 39 **Implementation (C++)** 40 41 [127991331](/contest/1567/submission/127991331 "Submission 127991331 by flamestorm") 42 43 **Video Solution** 44 45 [Link to Video](https://www.youtube.com/watch?v=7ou1zqT55LQ) 46 47 **Solution (DP)** 48 49 There exists a dynamic programming solution to this problem. Let $x$ be the length (number of digits) of $n$, and $dp_{i,j,k}$ be the number of pairs of integers $(x,y)$ that add up to the digits from position $i$ to $x-1$ ($0$-indexed), with $j$ carried over from the addition one place to the right, and $k$ carried over from the addition at position $i$. Notice that $0 \le j,k \le 1$, as the maximum addition value with carry in a single digit's place is $19$, and thus the maximum carry value is $\lfloor \frac{19}{10} \rfloor = 1$. 50 51 Now, we can iterate from rightmost digit to leftmost, i.e. from digit $x-1$ to $0$. We can further iterate over all pairs of digits in the addition for the current column, as well as the carry values from both one and two columns to the right, and thus, we can find the number of states that contribute to our current state. 52 53 Our answer can be found in $dp_{0,0,0}$, however, we must subtract $2$ from this as it includes the invalid pairs $(0,n)$ and $(n,0)$. 54 55 **Implementation (C++)** 56 57 [127990386](/contest/1567/submission/127990386 "Submission 127990386 by ScarletS") 58 59 [1567D - Expression Evaluation Error](/contest/1567/problem/D "Codeforces Round 742 (Div. 2)") 60 61 **Solution** 62 63 Tutorial is loading... 64 65 **Implementation (C++)** 66 67 [127991334](/contest/1567/submission/127991334 "Submission 127991334 by flamestorm") 68 69 **Video Solution** 70 71 [Link to Video](https://www.youtube.com/watch?v=6dAotrkoVCU) 72 73 [1567E - Non-Decreasing Dilemma](/contest/1567/problem/E "Codeforces Round 742 (Div. 2)") 74 75 **Solution** 76 77 Tutorial is loading... 78 79 **Implementation (C++)** 80 81 [127990755](/contest/1567/submission/127990755 "Submission 127990755 by ScarletS") 82 83 **Video Solution** 84 85 [Link to Video](https://www.youtube.com/watch?v=CIgm0HMJj3M) 86 87 [1567F - One-Four Overload](/contest/1567/problem/F "Codeforces Round 742 (Div. 2)") 88 89 **Solution** 90 91 Tutorial is loading... 92 93 **Implementation (C++)** 94 95 [127991337](/contest/1567/submission/127991337 "Submission 127991337 by flamestorm") 96 97 **Video Solution** 98 99 [Link to Video](https://www.youtube.com/watch?v=-9ydFKDIKMM)