# This blog is my personal reflection on what I have learned in Dp Digit↵
==================↵
↵
↵
## Theory:↵
+↵
- Dp digit template is something like this:↵
↵
```cpp↵
void dfs(pos, tight, [some conditions], target)↵
if pos == target:↵
return something↵
↵
limit = if tight = true — --> target[pos] else 9 (may vary depending on problem)↵
↵
for i : 0 — --> limit:↵
update_tight()↵
answ += do something() ↵
↵
dp[pos][tight][some condition] = answ↵
return answ↵
↵
```↵
↵
## Trick:↵
↵
1. $$\text{Answ}(L, R) = =\text{Answ}(0,R) — -\text{Answ}(0, L)$$↵
↵
-2. If you dp digit allow the numbers to move around, fix the segment `l - r` its goona be in making it much easier↵
↵
## Ideas:↵
+ ↵
### [Gym 100886 G](https://codeforces.me/gym/100886/problem/G)↵
+↵
- this problem mentioned max, which mean you can't use trick 1↵
+- so we must keep a `low_tight` for keeping the number `>= L`, and a `high_tight` to keep a number `<= R`↵
+- and then you just keep max number for each state simple↵
+- Be careful on the limit because you might be off by one ↵
↵
+ ### [SPOJ PR003004](https://www.spoj.com/problems/PR003004/en/)↵
+↵
- This problem is a little bit complicated, because we must store `(current sum, total number)`↵
+- Formula : :↵
↵
$$↵
\text{answ.sum} += i* \cdot \text{total\_number} + \text{current\_sum}↵
+ $$↵
↵
$$↵
\text{answ.number} += \text{total\_number }↵
↵
+$$↵
↵
### [Codeforces 1036C](https://vjudge.net/problem/CodeForces-1036C/origin)↵
+↵
- Chill problem standard easy↵
↵
+ ### [Codeforces 628D](https://vjudge.net/problem/CodeForces-628D/origin)↵
+↵
- Problem require 2 requirment:↵
+ - A mutiple of M↵
+`M`↵
- appearD`D` ONLY ON even position↵
↵
+- for the mod requirement just store mod of M`M` very simple↵
+- The even requirement is a bit hard but it is possible, just store the current parity of the position (stays odd until started)↵
↵
+ ### [CSES 2220](https://vjudge.net/problem/CSES-2220/origin)↵
+↵
- standard no comment↵
↵
+ ### [CodeChef DGTCNT](https://www.codechef.com/problems/DGTCNT )↵
+↵
- Not really dp digit because contain a lot of combinatorics but it contain dp digit idea↵
+- so first we have a bunch of requiremnt, which require :↵
↵
$$↵
cnt[0] == a_0 \text{ OR } cnt[1] == a_1 OR ...\text{ OR } \dots \text{ OR } cnt[9] == a[9]↵
+_9↵
$$↵
↵
- This is clear inclusion exclusion. So we must run through every mask (complexity $$2^{10}$$)↵
+- the idea for this problem is to walk on tight↵
+- the moment tight turn off it never turns on again which mean the moment the tight turn off we use combinatorics to count (ways to shuffle the numbers in mask * number of ways to shuffle the number not in mask)↵
↵
+ Precaculate Combinatoric also be careful with 0 it will mess your program up.↵
↵
+ https://vjudge.net/problem/CodeForces-1073E↵
↵
↵
↵
- Precaculate Combinatoric also be careful with `0` it will mess your program up.↵
↵
### [Codeforces 1073E](https://vjudge.net/problem/CodeForces-1073E)↵
↵
- standard store mask of all the one that has appeared↵
↵
### [USACO 1307](https://usaco.org/index.php?page=viewproblem2&cpid=1307&lang=en)↵
↵
- very fun problem indeed, instead of normal dp digit, we use the tight logic again↵
- consider `dp[l][r][cmp]` where a segment cover `l -> r` of digit `B`↵
↵
- why can we do this? : Because when fix the position we add the number to then the number wont get moved and we dont need to worry about position anymore (**GREAT TRICK**)↵
- so now we can consider the boolean expression when add `a_i` to left or right of a segment `l - r`↵
↵
- consider a general formula↵
↵
- function `g(x,y)` definition: (this function is used in order to mark the number much easier)↵
↵
```cpp↵
if (x > y) return 2;↵
if (x == y) return 1;↵
if (x < y) return 0;↵
```↵
↵
- function `f(x,y)` definition: (this function is used to merge to `cmp` toghether):↵
↵
```cpp↵
if (x == 0 or (x == 1 and y == 0)) return 0;↵
if (y == 1 && x == 1) return 1;↵
else return 2;↵
```↵
↵
- So for every number we add into this each segment and max using thif function formula, and update `dp[l][r][mask]`↵
- So the answer after is `dp[0][n-1][mask : 0 -> 1] + every lower segment starting at 0`↵
- the segment must start at `0` because when we update we add to every `dp[i][i][comp(current number, target[i])]`, so therefore there would be at least 1 copy at every position `i`↵
↵
### [USACO 1115](https://usaco.org/index.php?page=viewproblem2&cpid=1115&lang=en)↵
↵
- Ideas Look Horrifying at first with the weird formula but we can rephrase the ugly formula using this↵
- THe formula means that every position in two number `x_i` and `y_i` in base-3 must have same parity↵
- we can rewrite `(x_i, y_i)` as `(x_i, x_i + some number)`↵
- Note this work because if `(x_i, y_i)` is on then `(y_i, x_i)` would also be on↵
- when we addition on bit, the `bit[x]` must not be equal to base, if the `bit[x] == 0` then every number would work↵
- when we consider `bit[x]` of the `SomeNumber` part in `(x_i, x_i + some number)`, if after we add all the smaller bit, the current:↵
↵
$$↵
(\text{bit}[x] + \text{carryover}) \bmod 3 \ne 0↵
$$↵
↵
we can fix the number and continue on with the addition so the problem become much more simpler↵
↵
- the problem now become, given `L - R` find `L <= x <= R` where `x` has some position equal to the position we just fixed above
↵
## Theory
- Dp digit template is something like this:↵
↵
```cpp↵
void dfs(pos, tight, [some conditions], target)↵
↵
↵
↵
↵
## Trick
↵
1. $$\text{Answ}(L,
↵
↵
## Ideas
### [Gym 100886 G](https://codeforces.me/gym/100886/problem/G)↵
- this problem mentioned max, which mean you can't use trick 1↵
↵
- This problem is a little bit complicated, because we must store `(current sum, total number)`↵
↵
$$↵
\text{answ.sum} += i
↵
$$↵
\text{answ.number} += \text{total\_number
+
↵
### [Codeforces 1036C](https://vjudge.net/problem/CodeForces-1036C/origin)↵
- Chill problem standard easy↵
↵
- Problem require 2 requirment:↵
+
- appear
↵
↵
- standard no comment↵
↵
- Not really dp digit because contain a lot of combinatorics but it contain dp digit idea↵
↵
$$↵
cnt[0] =
+
$$↵
↵
- This is clear inclusion exclusion. So we must run through every mask (complexity $$2^{10}$$)↵
↵
↵
+ https://vjudge.net/problem/CodeForces-1073E↵
↵
↵
↵
↵
### [Codeforces 1073E](https://vjudge.net/problem/CodeForces-1073E)↵
↵
- standard store mask of all the one that has appeared↵
↵
### [USACO 1307](https://usaco.org/index.php?page=viewproblem2&cpid=1307&lang=en)↵
↵
- very fun problem indeed, instead of normal dp digit, we use the tight logic again↵
- consider `dp[l][r][cmp]` where a segment cover `l -> r` of digit `B`↵
↵
- why can we do this? : Because when fix the position we add the number to then the number wont get moved and we dont need to worry about position anymore (**GREAT TRICK**)↵
- so now we can consider the boolean expression when add `a_i` to left or right of a segment `l - r`↵
↵
- consider a general formula↵
↵
- function `g(x,y)` definition: (this function is used in order to mark the number much easier)↵
↵
```cpp↵
if (x > y) return 2;↵
if (x == y) return 1;↵
if (x < y) return 0;↵
```↵
↵
- function `f(x,y)` definition: (this function is used to merge to `cmp` toghether):↵
↵
```cpp↵
if (x == 0 or (x == 1 and y == 0)) return 0;↵
if (y == 1 && x == 1) return 1;↵
else return 2;↵
```↵
↵
- So for every number we add into this each segment and max using thif function formula, and update `dp[l][r][mask]`↵
- So the answer after is `dp[0][n-1][mask : 0 -> 1] + every lower segment starting at 0`↵
- the segment must start at `0` because when we update we add to every `dp[i][i][comp(current number, target[i])]`, so therefore there would be at least 1 copy at every position `i`↵
↵
### [USACO 1115](https://usaco.org/index.php?page=viewproblem2&cpid=1115&lang=en)↵
↵
- Ideas Look Horrifying at first with the weird formula but we can rephrase the ugly formula using this↵
- THe formula means that every position in two number `x_i` and `y_i` in base-3 must have same parity↵
- we can rewrite `(x_i, y_i)` as `(x_i, x_i + some number)`↵
- Note this work because if `(x_i, y_i)` is on then `(y_i, x_i)` would also be on↵
- when we addition on bit, the `bit[x]` must not be equal to base, if the `bit[x] == 0` then every number would work↵
- when we consider `bit[x]` of the `SomeNumber` part in `(x_i, x_i + some number)`, if after we add all the smaller bit, the current:↵
↵
$$↵
(\text{bit}[x] + \text{carryover}) \bmod 3 \ne 0↵
$$↵
↵
we can fix the number and continue on with the addition so the problem become much more simpler↵
↵
- the problem now become, given `L - R` find `L <= x <= R` where `x` has some position equal to the position we just fixed above
