tmaddy's blog

Digit Sum DP Iterative — Doubt in solution
By tmaddy, history, 4 years ago, In English

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 ?

Problem: https://atcoder.jp/contests/dp/tasks/dp_s

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;
	--answer;
 
	if(answer == -1)
		answer = mod - 1;

	cout << answer << "\n";

}

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

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

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

Errichto's YouTube channel Stream link: https://youtu.be/FAQxdm0bTaw?t=11154

Also wanna mention that I like this iterative solution than the recursive ones that exist out there on the internet.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When you do dynamic programming, you need to pass through all the states in topological sort order. Every transition needs to go from previous states to further states.

In this solution all transitions go from one layer to the next layer (by layers I mean each new dp array, we go through layers in the where-loop). Then the sum-loop and the smaller_taken-loop just go through every state on the current layer and it does not matter in which order you put this two loops.

The digit-loop goes through every transition from the current state. And ultimately when we write DP our goal is just to handle every transition in the order of topsort. So normally you could shuffle all those loops, however, here we have break that suppresses the invalid transitions. If you make the smaller_taken-loop the innermost, break will work incorrectly.

→ Reply