By tmaddy, history, 5 weeks ago,

So I was watching Errichto stream if At Coder Educational DP contest. I understood the transition and the base case but not the filling order. I tried messing with the order of the 3 nested for loops to fill up the table. Some permutations work and some don't .I was just wondering if anyone can help me understand why is that when you make the smaller_taken : {false, true} as the innermost loop we get wrong answer but when it is the second or the outer loop we get correct answer ?

Also I have another question in general to you all. Do you guys just test all orders, see which one passes test cases and then submit that or do you like spend time figuring out the details.

Now I do understand when the transition expression is something like dp[l] = l * dp[l-1] then clearly you need to fill from left to right but that's not always the case. So how do you go about it ?

Solution (from the video lecture):

#include <bits/stdc++.h>

#define forn(i, n) for(int i=0; i<n; ++i)

using ll = long long;

using namespace std;

const int mod = 1e9 + 7;

void add_self(int &a, int b) {
a += b;
if(a >= mod)
a -= mod;
}

void solve() {

string k;
cin >> k;

int D;
cin >> D;

int len = k.size();

vector<vector<int>>dp(D, vector<int>(2));

dp[0][0] = 1;

for(int where = 0; where < len; ++where) {
vector<vector<int>> new_dp(D, vector<int>(2));

for(int sum = 0; sum < D; ++sum) {
for(bool smaller_taken: { false, true }) {	// this cannot be made innermost for loop why?
for(int digit = 0; digit < 10; ++digit) {

if(digit > (k[where] - '0') && !smaller_taken) {
break;
}

add_self(new_dp[(sum+digit) % D][smaller_taken || digit < (k[where] - '0')],
dp[sum][smaller_taken]);
}
}
}

dp = new_dp;
}

int answer = (dp[0][false] + dp[0][true]) % mod;

}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

// int t;
// cin >> t;

// while(t--)
solve();

}