This blog is my personal reflection on what I have learned in Dp Digit

Theory

Note : Problem that mention Standard / Easy means repeating ideas.

• Dp digit template is something like this:

ll dfs(pos, tight, [some conditions], target)
    if pos == target:
        return something

    if (current_state != -1) return current_state
    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. 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

• 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

• This problem is a little bit complicated, because we must store (current sum, total number)
• Formula:

Codeforces 1036C

• Chill problem standard easy

Codeforces 628D

• Problem require 2 requirment:
• A mutiple of M
• appear D ONLY ON even position

• for the mod requirement just store mod of 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

• standard no comment

CodeChef 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:

• This is clear inclusion exclusion. So we must run through every mask (complexity

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

Codeforces 1073E

• standard store mask of all the one that has appeared

USACO 1307

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

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

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

• 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:

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