#	User	Rating
1	tourist	3882
2	maroonrk	3539
3	Benq	3513
4	MiracleFaFa	3466
5	ksun48	3462
6	ecnerwala	3446
7	slime	3428
8	Um_nik	3426
9	jiangly	3401
10	greenheadstrange	3393

#	User	Contrib.
1	awoo	192
2	-is-this-fft-	191
3	Monogon	184
4	YouKn0wWho	182
4	Um_nik	182
6	antontrygubO_o	170
7	maroonrk	169
8	kostka	165
9	SecondThread	164
9	errorgorn	164

I'm using bottom-up implementations and pull dp when possible. Pull dp is when we calculate each dp entry as a function of previously calculated dp entries. This is the way used in recursion / memoization. The other alternative would be push dp, where we update future dp entries using the current dp entry.

I think CSES is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES.

Feel free to point out mistakes.

Dice Combinations (1633)

dp[x] = number of ways to make sum x using numbers from 1 to 6.

Sum over the last number used to create x, it was some number between 1 and 6. For example, the number of ways to make sum x ending with a 3 is dp[x-3]. Summing over the possibilities gives dp[x] = dp[x-1] + dp[x-2] + dp[x-3] + dp[x-4] + dp[x-5] + dp[x-6].

We initialize by dp[0] = 1, saying there is one way with sum zero (the empty set).

The complexity is $$$O(n)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n;
  cin >> n;
  vector<int> dp(n+1,0);
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 6 && i-j >= 0; j++) {
      (dp[i] += dp[i-j]) %= mod;
    }
  }
  cout << dp[n] << endl;
}

Minimizing Coins (1634)

This is a classical problem called the unbounded knapsack problem.

dp[x] = minimum number of coins with sum x.

We look at the last coin added to get sum x, say it has value v. We need dp[x-v] coins to get value x-v, and 1 coin for value v. Therefore we need dp[x-v]+1 coins if we are to use a coin with value v. Checking all possibilities for v must include the optimal choice of last coin.

As an implementation detail, we use dp[x] = 1e9 = $$$10^9 \approx \infty$$$ to signify that it is not possible to make value x with the given coins.

The complexity is $$$O(n\cdot target)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, target;
  cin >> n >> target;
  vector<int> c(n);
  for (int&v : c) cin >> v;

  vector<int> dp(target+1,1e9);
  dp[0] = 0;
  for (int i = 1; i <= target; i++) {
    for (int j = 0; j < n; j++) {
      if (i-c[j] >= 0) {
	dp[i] = min(dp[i], dp[i-c[j]]+1);
      }
    }
  }
  cout << (dp[target] == 1e9 ? -1 : dp[target]) << endl;
}

Coin Combinations I (1635)

This problem has a very similar implementation to the previous problem.

dp[x] = number of ways to make value x.

We initialize dp[0] = 1, saying the empty set is the only way to make 0.

Like in "Minimizing Coins", we loop over the possibilities for last coin added. There are dp[x-v] ways to make x, when adding a coin with value v last. This is since we can choose any combination for the first coins to sum to x-v, but need to choose v as the last coin. Summing over all the possibilities for v gives dp[x].

The complexity is $$$O(n\cdot target)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n, target;
  cin >> n >> target;
  vector<int> c(n);
  for (int&v : c) cin >> v;

  vector<int> dp(target+1,0);
  dp[0] = 1;
  for (int i = 1; i <= target; i++) {
    for (int j = 0; j < n; j++) {
      if (i-c[j] >= 0) {
	(dp[i] += dp[i-c[j]]) %= mod;
      }
    }
  }
  cout << dp[target] << endl;
}

Coin Combinations II (1636)

dp[i][x] = number of ways to pick coins with sum x, using the first i coins.

Initially, we say we have dp[0][0] = 1, i.e we have the empty set with sum zero.

When calculating dp[i][x], we consider the i'th coin. Either we didn't pick the coin, then there are dp[i-1][x] possibilities. Otherwise, we picked the coin. Since we are allowed to pick it again, there are dp[i][x — <value of i'th coin>] possibilities (not dp[i-1][x — <value of i'th coin>] possibilities).

Because we consider the coins in order, we will only count one order of coins. This is unlike the previous task, where we considered every coin at all times.

The complexity is $$$O(n\cdot target)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n, target;
  cin >> n >> target;
  vector<int> x(n);
  for (int&v : x) cin >> v;

  vector<vector<int>> dp(n+1,vector<int>(target+1,0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= target; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-x[i-1];
      if (left >= 0) {
	(dp[i][j] += dp[i][left]) %= mod;
      }
    }
  }
  cout << dp[n][target] << endl;
}

Removing Digits (1637)

dp[x] = minimum number of operations to go from x to zero.

When considering a number x, for each digit in the decimal representation of x, we can try to remove it. The transition is therefore: dp[x] = $$$\min_{d \in digits(x)}$$$ dp[x-d].

We initialize dp[0] = 0.

The complexity is $$$O(n)$$$.

Note that the greedy solution of always subtracting the maximum digit is also correct, but we are practicing DP :)

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> dp(n+1,1e9);
  dp[0] = 0;
  for (int i = 0; i <= n; i++) {
    for (char c : to_string(i)) {
      dp[i] = min(dp[i], dp[i-(c-'0')]+1);
    }
  }
  cout << dp[n] << endl;
}

Grid Paths (1638)

dp[r][c] = number of ways to reach row r, column c.

We say there is one way to reach (0,0), dp[0][0] = 1.

When we are at some position with a ., we came either from the left or top. So the number of ways to get to there is the number of ways to get to the position above, plus the number of ways to get to the position to the left. We also need to make sure that the number of ways to get to any position with a # is 0.

The complexity is $$$O(n^2)$$$, so linear in the number of cells of input.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n;
  cin >> n;
  vector<vector<int>> dp(n, vector<int>(n, 0));
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    string row;
    cin >> row;
    for (int j = 0; j < n; j++) {
      if (row[j] == '.') {
	if (i > 0) {
	  (dp[i][j] += dp[i-1][j]) %= mod;
	}
	if (j > 0) {
	  (dp[i][j] += dp[i][j-1]) %= mod;
	}
      } else {
	dp[i][j] = 0;
      }
    }
  }
  cout << dp[n-1][n-1] << endl;
}

Book Shop (1158)

This is a case of the classical problem called 0-1 knapsack.

dp[i][x] = maximum number of pages we can get for price at most x, only buying among the first i books.

Initially dp[0][x] = 0 for all x, as we can't get any pages without any books.

When calculating dp[i][x], we look at the last considered book, the i'th book. We either didn't buy it, leaving x money for the first i-1 books, giving dp[i-1][x] pages. Or we bought it, leaving x-price[i-1] money for the other i-1 books, and giving pages[i-1] extra pages from the bought book. Thus, buying the i'th book gives dp[i-1][x-price[i-1]] + pages[i-1] pages.

The complexity is $$$O(n\cdot x)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> price(n), pages(n);
  for (int&v : price) cin >> v;
  for (int&v : pages) cin >> v;
  vector<vector<int>> dp(n+1,vector<int>(x+1,0));
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= x; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-price[i-1];
      if (left >= 0) {
	dp[i][j] = max(dp[i][j], dp[i-1][left]+pages[i-1]);
      }
    }
  }
  cout << dp[n][x] << endl;
}

Array Description (1746)

dp[i][v] = number of ways to fill the array up to index i, if x[i] = v.

We treat i = 0 separately. Either x[0] = 0, so we can replace it by anything (i.e dp[0][v] = 1 for all v). Otherwise x[0] = v $$$\ne$$$ 0, so that dp[0][v] = 1 is the only allowed value.

Now to the other indices i > 0. If x[i] = 0, we can replace it by any value. However, if we replace it by v, the previous value must be either v-1, v or v+1. Thus the number of ways to fill the array up to i, is the sum of the previous value being v-1, v and v+1. If x[i] = v from the input, only dp[i][v] is allowed (i.e dp[i][j] = 0 if j $$$\ne$$$ v). Still dp[i][v] = dp[i-1][v-1] + dp[i-1][v] + dp[i-1][v+1].

The complexity is $$$O(n\cdot m)$$$ with worst-case when x is all zeros.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n, m;
  cin >> n >> m;
  vector<vector<int>> dp(n,vector<int>(m+1,0));
  int x0;
  cin >> x0;
  if (x0 == 0) {
    fill(dp[0].begin(), dp[0].end(), 1);
  } else {
    dp[0][x0] = 1;
  }
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    if (x == 0) {
      for (int j = 1; j <= m; j++) {
	for (int k : {j-1,j,j+1}) {
	  if (k >= 1 && k <= m) {
	    (dp[i][j] += dp[i-1][k]) %= mod;
	  }
	}
      }
    } else {
      for (int k : {x-1,x,x+1}) {
	if (k >= 1 && k <= m) {
	  (dp[i][x] += dp[i-1][k]) %= mod;
	}
      }
    }
  }
  int ans = 0;
  for (int j = 1; j <= m; j++) {
    (ans += dp[n-1][j]) %= mod;
  }
  cout << ans << endl;
}

Edit Distance (1639)

This is a classic problem called edit distance.

We call the input strings a and b, and refer to the first i characters of a by a[:i].

dp[i][k] = minimum number of moves to change a[:i] to b[:k].

When we calculate dp[i][k], there are four possibilities to consider for the rightmost operation. We check all of them and take the cheapest one.

1. We deleted character a[i-1]. This took one operation, and we still need to change a[:i-1] to b[:k]. So this costs 1 + dp[i-1][k] operations.

2. We added character b[k-1] to the end of a[:i]. This took one operation, and we still need to change a[:i] to b[:k-1]. So this costs 1 + dp[i][k-1] operations.

3. We replaced a[i-1] with b[k-1]. This took one operation, and we still need to change a[:i-1] to b[:k-1]. So this costs 1 + dp[i-1][k-1] operations.

4. a[i-1] was already equal to b[k-1], so we just need to change a[:i-1] to b[:k-1]. That takes dp[i-1][k-1] operations. This possibility can be viewed as a replace operation where we don't actually need to replace a[i-1].

The complexity is $$$O(|a|\cdot |b|)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  string a, b;
  cin >> a >> b;
  int na = a.size(), nb = b.size();
  vector<vector<int>> dp(na+1, vector<int>(nb+1,1e9));
  dp[0][0] = 0;
  for (int i = 0; i <= na; i++) {
    for (int j = 0; j <= nb; j++) {
      if (i) {
	dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
      }
      if (j) {
	dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
      }
      if (i && j) {
	dp[i][j] = min(dp[i][j], dp[i-1][j-1]+(a[i-1] != b[j-1]));
      }
    }
  }
  cout << dp[na][nb] << endl;
}

Rectangle Cutting (1744)

dp[w][h] = minimum number of cuts needed to cut a w x h piece into squares.

Consider a $$$w \times h$$$ piece. If it is already square (w = h), we need 0 cuts. Otherwise, we need to make the first cut either horizontally or vertically. Say we make it horizontally, then we can cut at any position 1,2,..,h-1. If we cut at position k, then we are left with two pieces of sizes $$$w \times k$$$ and $$$w \times h-k$$$. We can look up the number of moves to reduce these to squares in the dp array. We loop over all possibilities k and take the best one. Similarly for vertical cuts.

The complexity is $$$O(a^2\cdot b + a\cdot b^2)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int w, h;
  cin >> w >> h;
  vector<vector<int>> dp(w+1,vector<int>(h+1));
  for (int i = 0; i <= w; i++) {
    for (int j = 0; j <= h; j++) {
      if (i == j) {
	dp[i][j] = 0;
      } else {
	dp[i][j] = 1e9;
	for (int k = 1; k < i; k++) {
	  dp[i][j] = min(dp[i][j], dp[k][j]+dp[i-k][j]+1);
	}
	for (int k = 1; k < j; k++) {
	  dp[i][j] = min(dp[i][j], dp[i][k]+dp[i][j-k]+1);
	}
      }
    }
  }
  cout << dp[w][h] << endl;
}

Money Sums (1745)

This is a case of the classical problem called 0-1 knapsack.

dp[i][x] = true if it is possible to make x using the first i coins, false otherwise.

It is possible to make x with the first i coins, if either it was possible with the first i-1 coins, or we chose the i'th coin, and it was possible to make x — <value of i'th coin> using the first i-1 coins.

Note that we only need to consider sums up to 1000 $$$\cdot$$$ n, since we can't make more than that using n coins of value $$$\le$$$ 1000.

The complexity is $$$O(n^2\cdot \max x_i)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int max_sum = n*1000;
  vector<int> x(n);
  for (int&v : x) cin >> v;
  vector<vector<bool>> dp(n+1,vector<bool>(max_sum+1,false));
  dp[0][0] = true;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= max_sum; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-x[i-1];
      if (left >= 0 && dp[i-1][left]) {
	dp[i][j] = true;
      }
    }
  }

  vector<int> possible;
  for (int j = 1; j <= max_sum; j++) {
    if (dp[n][j]) {
      possible.push_back(j);
    }
  }
  cout << possible.size() << endl;
  for (int v : possible) {
    cout << v << ' ';
  }
  cout << endl;
}

Removal Game (1097)

The trick here is to see that since the sum of the two players' scores is the sum of the input list, player 1 tries to maximize $$$score_1-score_2$$$, while player 2 tries to minimize it.

dp[l][r] = difference$$$score_1-score_2$$$if considering the game played only on interval [l, r].

If the interval contains only one element (l = r), then the first player must take that element. So dp[i][i] = x[i].

Otherwise, player 1 can choose to take the first element or the last element. If he takes the first element, he gets x[l] points, and we are left with the interval [l+1,r], but with player 2 starting. $$$score_1-score_2$$$ on interval [l+1,r] is just dp[l+1][r] if player 1 starts. Since player 2 starts, it is -dp[l+1][r]. Thus, the difference of scores will be x[l]-dp[l+1][r] if player 1 chooses the first element. Similarly, it will be x[r]-dp[l][r-1] if he chooses the last element. He always chooses the maximum of those, so dp[l][r] = max(x[l]-dp[l+1][r], x[r]-dp[l][r-1]).

In this problem dp[l][r] depends on dp[l+1][r], and therefore we need to compute larger l before smaller l. We do it by looping through l from high to low. r still needs to go from low to high, since we depend only on smaller r (dp[l][r] depends on dp[l][r-1]). Note that in all the other problems in this editorial, dp only depends on smaller indices (like dp[x] depending on dp[x-v], or dp[i][x] depending on dp[i-1][x]), which means looping through indices in increasing order is correct.

We can reconstruct the score of player 1 as the mean of, the sum of all input values, and $$$score_1-score_2$$$.

The complexity is $$$O(n^2)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> x(n);
  long long sum = 0;
  for (int&v : x) {
    cin >> v;
    sum += v;
  }

  vector<vector<long long>> dp(n,vector<long long>(n));
  for (int l = n-1; l >= 0; l--) {
    for (int r = l; r < n; r++) {
      if (l == r) {
	dp[l][r] = x[l];
      } else {
	dp[l][r] = max(x[l]-dp[l+1][r],
		       x[r]-dp[l][r-1]);
      }
    }
  }
  cout << (sum+dp[0][n-1])/2 << endl;
}

Two Sets II (1093)

This is a 0-1 knapsack in disguise. If we are to have two subsets of equal sum, they must sum to half the total sum each. This means if the total sum $$$\frac{n(n+1)}{2}$$$ is odd, the answer is zero (no possibilities). Otherwise we run 0-1 knapsack to get the number of ways to reach $$$\frac{n(n+1)}{4}$$$ using subsets of the numbers 1..n-1. Why n-1? Because by only considering numbers up to n-1, we always put n in the second set, and therefore only count each pair of sets once (otherwise we count every pair of sets twice).

dp[i][x] = number of ways to make sum x using subsets of the numbers 1..i .

We say there is one way (the empty set) to make sum 0, so dp[0][0] = 1;

For counting number of ways to make sum x using values up to i, we consider the number i. Either we didn't include it, then there are dp[i-1][x] possibilities, or we included it, and there are dp[i-1][x-i] possibilities. So dp[i][x] = dp[i-1][x] + dp[i-1][x-i].

The complexity is $$$O(n^3)$$$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n;
  cin >> n;
  int target = n*(n+1)/2;
  if (target%2) {
    cout << 0 << endl;
    return 0;
  }
  target /= 2;

  vector<vector<int>> dp(n,vector<int>(target+1,0));
  dp[0][0] = 1;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j <= target; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-i;
      if (left >= 0) {
	(dp[i][j] += dp[i-1][left]) %= mod;
      }
    }
  }
  cout << dp[n-1][target] << endl;
}

Increasing Subsequence (1145)

This is a classical problem called Longest Increasing Subsequence or LIS for short.

dp[x] = minimum ending value of an increasing subsequence of length x+1, using the elements considered so far.

We add elements one by one from left to right. Say we want to add a new value v. For this to be part of an increasing subsequence, the previous value in the subsequence must be lower than v. We might as well take the maximum length subsequence leading up to v, as the values don't matter for the continuation to the right of v. Therefore we need to extend the current longest increasing subsequence ending in a value less than v. This means we want to find the rightmost element in the dp array (as the position corresponds to the length of the subsequence), with value less than v. Say it is at position x. We can put v as a new candidate for ending value at position x+1 (since we have an increasing subsequence of length x+1 + 1, which ends on v). Note that since x was the rightmost position with value less than v, changing dp[x+1] to v can only make the value smaller (better), so we can always set dp[x+1] = v without checking if it is an improvement first.

Naively locating the position x with a for loop gives complexity $$$O(n^2)$$$. However, dp is always an increasing array. So we can locate x position by binary search (std::lower_bound in C++ directly gives position x+1).

The final answer is the length of the dp array after considering all elements.

The complexity is $$$O(n\cdot \log n)$$$.

In this task we were asked to find the longest strictly increasing subsequence. To find the longest increasing subsequence where we allow consecutive equal values (for example 1,2,2,3), change lower_bound to upper_bound.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> dp;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    auto it = lower_bound(dp.begin(), dp.end(), x);
    if (it == dp.end()) {
      dp.push_back(x);
    } else {
      *it = x;
    }
  }
  cout << dp.size() << endl;
}

Projects (1140)

Even though days can go up to $$$10^9$$$, we only care about days where we either start or just finished a project. So before doing anything else, we compress all days to their index among all interesting days (i.e days corresponding to $$$a_i$$$ or $$$b_i+1$$$ for some i). This way, days range from 0 to less than $$$2 n \le 4\cdot 10^5$$$.

dp[i] = maximum amount of money we can earn before day i.

On day i, maybe we just did nothing, so we earn what we earned on day i-1, i.e dp[i-1]. Otherwise, we just finished some project. We earned some money doing the project, and use dp[start of project] to know how much money we could have earned before starting the project. Loop through all projects finishing just before day i, and take the best one.

The complexity is $$$O(n\cdot \log n)$$$, log comes from day compression.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  map<int,int> compress;
  vector<int> a(n),b(n),p(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> p[i];
    b[i]++;
    compress[a[i]], compress[b[i]];
  }

  int coords = 0;
  for (auto&v : compress) {
    v.second = coords++;
  }

  vector<vector<pair<int,int>>> project(coords);
  for (int i = 0; i < n; i++) {
    project[ compress[b[i]] ].emplace_back( compress[a[i]], p[i] );
  }

  vector<long long> dp(coords, 0);
  for (int i = 0; i < coords; i++) {
    if (i > 0) {
      dp[i] = dp[i-1];
    }
    for (auto p : project[i]) {
      dp[i] = max(dp[i], dp[p.first]+p.second);
    }
  }
  cout << dp[coords-1] << endl;
}

Comments (201)

Write comment?

fanof300iq

3 years ago, # |

Hello. Thanks for editorial. Do you have links to above problems or where I can submit them. I want to try all of them as they look good from IPOV.

→ Reply

arknave

3 years ago, # ^ |

https://cses.fi/problemset/

Thanks a lot.

Errichto

+46

Cool, thanks. I already recommend CSES problem set to some people and I will now link to this blog for dp. Just next time consider using names like ways or best_score in the future instead of dp in every single problem — if you want to then publish your codes to help others.

Harry__9522

9 months ago, # ^ |

very nice

brooklyn_

7 months ago, # ^ |

Why this code gives RTE for minimizing coins while it gives correct ans in codeblocks?

corredor10

6 months ago, # ^ |

← Rev. 2 →

Because of extra memory.Actually,you are using O(1000005*105) space.Try it in O(1000005)

meooow

+21

In my opinion, open editorials to CSES problems (with code!) goes against the spirit of the platform. Not providing solutions or access to accepted submissions must have been a conscious decision by the maintainers.

icecuber

+37

I thought about that, and therefore asked pllk for permission before writing the editorial. He encourages editorials for the problems. However, he mentioned that it might cause some people to read the editorial without thinking about the problem.

meooow I think you are wrong here. I agree one should think before rushing to editorials but having no editorials forces one to leave the question without any further learning and development.

Thanks to icecuber who invested his precious time in writing some editorials and pllk for allowing it.

+20

Having no editorial is not enough reason to leave a problem. There are many avenues to ask for help once you have truly exhausted all approaches you can think of.

However, since pllk approves of this, my point of complaint isn't valid.

shoya

Can you kindly suggest some of the many avenues you mention of? And are they more effective and efficient than having the editorial at your disposal?

Asking for help FAQ

Is the answer you get by asking for help going to be better than an editorial? Maybe not.
Is the absence of an editorial going to make you work harder to solve the problem? Absolutely yes.

Please do not think that I am preaching for a world with no editorials. It is just that the design of the CSES problemset implies that it is meant to solved by putting in maximum individual effort.

Well, I believe that every problem should have an editorial. Let's say I put in 2 days worth of effort solving a problem without making any real progress then an editorial guarantees me closure for my efforts. On the other hand, asking help from others doesn't provide me that certainty. Especially for the guys like me who don't have coding circles where we can ask for help from friends. Cyans(or lower rating) people asking for help from a random person usually gets ignored. That's just what I have observed and my opinion.

mokoto

shoya right. exactly right.

tfg

Idk, I usually answer people that ask nicely. Show the problem source and more people might help.

CAdBUrY21

14 months ago, # ^ |

thanks icecuber for this amazing editorial,very helpful,very informative.Grateful for ur efforts into preparing this elegant editorial,as far as some arrogant coders like meoow are concerned who dont like the publishing of editorials just because they simply dont care about learners like us,with that dominating chaacter of dominating others on the battlefield,coders like you i.e icecuber are really helping beginners like us a lot in this regard of learning.Many many thanks

nchn27

+12

Thanks for this. I love the work here. CSES needs more editorials like this; sometimes even just stalking people's code isn't enough to understand what's going on. I hope you keep going with this too.

msf_sheet

22 months ago, # ^ |

How to see other peoples submission in CSES.fi ?

I meant looking at people’s GitHubs or something like that since you can’t view other solutions until you solve it yourself

Loser_

18 months ago, # ^ |

msf_sheet you can see others submission after you solved the problem in hacking tab.

Hd7

Thanks to this blog, I go back to my account on CSES problem set. I found out that I didn't solve 2 problems in DP section (Got TLE several testcases). I solved it and AC in first submit, but the logic is the same as I have solved it before. Lmao =)))

I've gotten two more questions about TLE in Coin Combinations II, so I guess it deserves a comment. Since we are doing $$$10^8$$$ operations in one second, we need those operations to be efficient. This means we can't have many cache misses.

You get cache misses by accessing array entries that are far away from each other. My implementation loops through i, then j. It accesses dp[i][j], dp[i-1][j] and dp[i][j-x[i-1]].

If you order your loops differently (j, then i), or use dp[j][i] instead of dp[i][j] (so you swapped the meaning of the dimensions), you will likely get TLE.

In terms of rules of thumb, we see that the dimension containing j-x[i-1] varies most, and therefore put it as the inner dimension of the dp array. And we loop through the dimensions the same order as the dimensions of the array. Below are some more detailed explanations.

If we loop through i, j-x[i-1] varies a lot, this means cache misses. Therefore we need to loop through i in the outer loop. Looping through j gives contiguous memory accesses, so we get few cache misses by having j as the inner loop.

If you define your array as dp[j][i] instead of dp[i][j], then dp[j-x[i-1]][i] goes far from dp[j][i], compared to dp[i][j] and dp[i][j-x[i-1]]. This is because the outer dimension gives smaller distance in memory than the inner dimension (you can think of dp[i][j] as accessing index $$$10^6 i + j$$$ in a linear array, if the second dimension has size $$$10^6$$$).

nilesh8757

2 years ago, # ^ |

Is it the same reason (that O(n * sum) solution requires 10⁸ ops, in worst case) and hence top-down is not feasible due to extra overhead of recursion ?

_punk

actually if u notice then in case of top down we dont visit each and every cell of n*sum dp table... but in bottom up we also go to the states which wont be occuring if we use the TOP down method..so some how Top down is better .Thats my logic behind it.. Any new logics are highly appreciated!! Do comment if u feel something wrong in it!

Ihtemadul

23 months ago, # ^ |

Thanks,i didn't think caching might be a problem in a program although it makes quite a sense now. however, we can do the program in O(x) space complexity,right? That could avoid the problem of caching.

BluBeer

21 month(s) ago, # ^ |

" If you order your loops differently (j, then i), or use dp[j][i] instead of dp[i][j] (so you swapped the meaning of the dimensions), you will likely get TLE." this was reason i was getting TLE, thanks for your comment

include<bits/stdc++.h>

using namespace std;

define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

define pb push_back

define ll long long int

ll mod = 1e9+7; const int N = 1e5+7;

int dp[101][1000001];

int main(){ fast; int n , val;

cin >> n >> val;
int arr[n];

for(int i = 0 ; i < n ;i++)
    cin >> arr[i];

for(int i = 0;i <= n; i++)
    dp[i][0] = 1;

for(int i = 1;i <= n ;i++)
    for(int j = 1 ; j<= val ; j++){
       if(arr[i-1] <= j)
         dp[i][j] = (dp[i][j - arr[i-1]] + dp[i-1][j])%mod;
       else
         dp[i][j] = dp[i-1][j];
    }

    cout << dp[n][val];

}

This Code is still giving TLE ..Can you please let me know where its going wrong? Its the same code as yours!!

prayutsu

15 months ago, # ^ |

use int instead of long long

_Bigil_

12 months ago, # ^ |

May i know what difference will it make please.

wOoDeN_sPoOn

11 months ago, # ^ |

blog

RegoNoShi

I solved the problem in a different way: https://cses.fi/paste/592407cb546d6d442325ac/

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
array<int, 1000001> A;
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, X, c;
    cin >> N >> X;
    A[0] = 1;
    for (int _ = 0; _ < N; _++) {
        cin >> c;
        for (int i = c; i <= X; i++)
            A[i] = (A[i] + A[i - c]) % MOD;
    }
    cout << A[X] << endl;
}

It passes all the test cases but I'm still confused why it works, since everyone it's using 2d dp...

This is a solution of Coin Combinations I while others are talking about Coin Combination II.

No, it works for Coin Combination II. You can try it. Maybe the problem was changed over the years

SD0313

I think the difference is that the solution to Coin Combinations 1 would process all the coin values at the beginning. However, the solution proposed here is different because it does the updating process while looking at only ONE coin at each step, not all the coins.

Solution to Coin Combinations 1:

dp[0] = 1;
for (int i = 0; i < x+1; i++) {
    for (int c : coins) {
        if (i-c >= 0) {
            dp[i] += dp[i-c]%MOD;
        }
    }
}

Solution to Coin Combination 2:

dp[0] = 1;
for (int c : coins) {
    for (int i = 0; i < x+1; i++) {
        if (i-c >= 0) {
            dp[i] += dp[i-c]%MOD;
        }
    }
}

Both problems have very similar solutions except with different orders for the loops. Thanks for the solution RegoNoShi!

Glydon

2 months ago, # ^ |

I can't believe this cache miss concept has only 8 upvotes! It's amazing!

Drom

What's essentialy the difference between coins combinations I and II, why the added dimension and why we reversed the order of loops?

knakul_853

Next Graph theory, please...

Thanks, Due to no editorial novice programmers couldn't try those problems or either leave it after sometime. Please make next one on graph and tree. icecuber

steelarm

In Book Shop , if I buy the i'th book then shouldn't x-price[i] money be left for the remaining i-1 books , so I can't see why x-price[i-1] money is left for the remaining i-1 books as that would imply that the money left is after buying the (i-1)'th book. So if icecuber or anyone else could please explain this it would be a great help. Thanks.

The array "price" is 0-indexed, so the price of the i'th book is price[i-1].

I feel so dumb for asking such a question as now it is obvious what you were trying to say. And I am sorry for asking something like this. I am thankful to you for answering and also for the editorial. Thanks icecuber.

2 years ago, # |

For Coin Combinations II (1636), my solution getting TLE in 3 TCs. Unlike editorial, I'm trying top-down approach. Can someone help please?

Nur47

TLE on 100 1000000? I don't know but I think top-down will be slower when the table is filled-up

nine.nine

I think there might be 2 reasons for that :

If you are using a 2D vector for dp like 'vector<vector> dp(n+1,vector(sum+1,0));'(ll -> long long), then you might want to change the data type from long long int to int like 'vector<vector> dp(n+1,vector(sum+1,0));'
while doing the MOD operation like '_dp[i][j] = ((dp[i][j-v[i-1]]%MOD) + (dp[i-1][j]%MOD))%MOD;_', you might want to do something like '(dp[i][j] += dp[i][left]) %= MOD;

This worked for me.

ahmad322297

8 months ago, # ^ |

I'm getting TLE in 6 TCs for the same problem, can you help me ?

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define endl "\n"
typedef long long ll;
using namespace std;
int mod=1e9+7,n,x,memo[101][int(1e6+10)],idx[int(1e6+10)];
vector<int> a;
int dp(int sum=x,int prev=0)
{
    if(sum<0)
        return INT_MAX;
    else if(sum==0)
        return 1;
    int &ans=memo[prev][sum];
    if(ans!=-1)
        return ans;
    ans=0;
    for(int i=prev;i<a.size();i++)
    {
        int tmp=dp(sum-a[i],i);
        if(tmp==INT_MAX)
            break;
        if(tmp>=mod)
            tmp-=mod;
        ans+=tmp;
        if(ans>=mod)
            ans-=mod;
    }
    return ans;
}
int main()
{
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
    #endif
    ios::sync_with_stdio(false);
    cin>>n>>x;
    for(int i=0;i<n;i++)
    {
        int b;
        cin>>b;
        idx[b]++;
    }
    for(int i=1;i<1e6+1;i++)
        if(idx[i])
            a.pb(i);
    memset(memo,-1,sizeof memo);
    cout<<dp();
    return 0;
}

tautology

In Two Sets II problem,
Because by only considering numbers up to n-1, we always put n in the second set, and therefore only count each pair of sets once (otherwise we count every pair of sets twice).
Why putting n always in second set gurantees unique sets? How to prove above statement.

victor142

Since you aren't having 'n' in your first set, you'll never have a first set that consists of a combination involving 'n' i.e. all the times a combination requires 'n' you are simply not counting it... thus you end up counting things only once.

VaibhavAgarwala

Please do the same for "Graph Algorithms" section. Thanks.

Paaaaain

please provide editorial for graphs problem. Thanks:)

SuperJ6

It takes a long time to write up an editorial like this, and the graph section has like a billion problems. If icecuber provides an editorial that's great, but there exists code on github for all the problems so if you're stuck you shouldn't rely on him making an editorial, as he may not want to. Notice how people asked 7 months ago (comment) and he still has not, so I doubt it'll happen smh. No need for people to keep asking.

kaiyu

← Rev. 3 →

+13

Check out the AC codes for all CSES dp problems here:

https://github.com/pratikkundnani/cses-dp-solutions/tree/master

I will keep updating the repository! I will be solving graph problems too.

Star it if you liked it.

Thank you!

QuiGon

Can you write an editorial for the graph section too...it will be a great help..

I am not sure about the editorials but I will be solving the graph section and I will upload all AC codes of the graph section on my Github. I will update you all!

shah_entrance

Why my code for Minimizing Coins gives TLE for some test cases, even it's complexity is also O(n*target)?

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[1000005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,target,i,j;
    cin>>n>>target;
    ll arr[n];
    for(i=0;i<n;i++)
        cin>>arr[i];
    for(i=0;i<=target;i++)
        dp[i]=INT_MAX;
    for(i=0;i<=target;i++){
        for(j=0;j<n;j++){
            if(i<arr[j])
                continue;
            else{
                if(i%arr[j]==0)
                    dp[i]=min({dp[i],i/arr[j],1+dp[i-arr[j]]});
                else
                    dp[i]=min(dp[i],1+dp[i-arr[j]]);
            }
        }
    }
    if(dp[target]==INT_MAX)
        cout<<-1<<endl;
    else
        cout<<dp[target]<<endl;
    return 0;
}

lohit_97

The i%arr[j] is causing the TLE I believe. I removed it, since it isn't required as dp[i-arr[j]] will handle it.

This is because the constraints are already too tight and modulo operation is time costly operation. Also, sorting arr also improved the time a bit, but major contribution was made by remove the module operation.

Hope this helps.

#include "bits/stdc++.h"

using namespace std;

typedef long long int ll;
ll dp[1000005];
ll arr[101];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,target,i,j;
    cin>>n>>target;
    for(i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    for(i=0;i<=target;i++)
        dp[i]=INT_MAX;
    dp[0] = 0;
    for(i=0;i<=target;i++){
        for(j=0;j<n;j++){
            if(i<arr[j])
                continue;
            else{
                dp[i]=min(dp[i],1+dp[i-arr[j]]);
            }
        }
    }
    if(dp[target]==INT_MAX)
        cout<<-1<<endl;
    else
        cout<<dp[target]<<endl;
    return 0;
}

Sorry for the poor formatting, I am not able to figure out a better way.

Yeah, Got it!!

_MSH_

You can also use something like this:

if (value >= MOD) value -= MOD;

This is much much faster than the costly operation of modulus operator!

TargaryenWolf

20 months ago, # ^ |

what about values twice or thrice bigger than mod

In case of addition, the biggest possible result would be MOD — 1 + MOD — 1 = 2*MOD — 2. Otherwise, it has already been drawn down.

Phantom2611

can you also provide editorials for the graph section as well

Shwetank

You can also refer this competitive programming book by cses

code_episky

Hello coders!! I'm listing out my AC solutions of CSES DP questions. It's not fully updated. I'm working on it. you can have a visit to look into the AC codes. Do star it if you like it. Thank you. Suggestions are welcome.

https://github.com/noob-hu-yaar/CSES-Problem-set-solutions-DP-?files=1

sigma_g

Can anyone explain the matrix expo solution to Dice Combinations? It has much lower complexity ($$$6^3 \log n$$$ afaict). This is the code, for example, which used the matrix

1 1 1 1 1 1
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0

raises it to the power $$$n$$$, and then prints dp[0][0] as the answer. Can someone explain how do we come up with this matrix in the first place?

Check CP handbook's matrix chapter's linear recurrences section.

_o_o_

13 months ago, # ^ |

Please give the link of CP handbook , you mentioned above.

prodipdatta7

CP Handbook

wuf

Why does this code give a runtime error? It works fine on my computer for the same inputs.

#include <bits/stdc++.h>
using namespace std;

#define __ ios_base::sync_with_stdio(cin.tie(0) && 0);
typedef long long ll;

const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
 
ll dp[101][maxn];
int c[101];
int main() {
  __;
 
  int n, x;
  cin >> n >> x;
  for(int i = 1; i <= n; i++) cin >> c[i];

  dp[0][0] = 1;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= x; j++) {
      dp[i][j] = dp[i - 1][j];
      if(j >= c[i]) (dp[i][j] += dp[i][j - c[i]]) %= MOD; 
    }
  }
  cout << dp[n][x] << '\n';
 
  return 0;
}

I figured it out myself, the problem with the code was that I was using long long for dp array which was exceeding the memory limit, changing it to int passed all the test cases. I just wrote it here in case someone faces the same problem.

iamvinayvk

17 months ago, # ^ |

Thanks

ikr

Thanks a lot icecuber! I found your editorial super useful.

It was hard for me to understand the Removal Game (1097) solution at first. I even found another version here, and struggled comprehending it as well :-) Like, I saw how the code could possibly work, of course, but the trail of thought leading to that code was eluding me. So I found my own trail then, which may be somewhat more beginner-friendly. So, here it is:

Given the input numbers xs, I started with two arrays: A[l][r], B[l][r] -- the scores for each player, when they have the first move on the range of [l, r]. Now, say, I'm the player A, and I pull from the front of the range -- the xs[l]. Let t be the range_sum(l, r). Then, t = xs[l] + B[l + 1][r] + alpha, which leads to alpha = t - xs[l] - B[l + 1][r]. Thus, A[l][r] = xs[l] + alpha = t - B[l + 1][r]. Similarly, if I pull from the back of the range, A[l][r] = t - B[l][r - 1]. The optimal strategy is to take the largest of the two numbers.

Next, we make an observation, that the A will be identical to B, and we only need one DP matrix.

The code

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

ll max_a_score(const vll &xs) {
    const int sz = xs.size();
    
    vll psums(sz, 0);
    partial_sum(xs.cbegin(), xs.cend(), psums.begin());
    const auto range_sum = [&psums](const int l, const int r) {
        const ll b = psums[r];
        const ll a = l > 0 ? psums[l - 1] : 0;
        return b - a;
    };
    
    // score when playing [from index l] [to index r]
    vvll score(sz, vll(sz, 0));
    
    for (int r = 0; r != sz; ++r) {
        score[r][r] = xs[r];
        
        for (int l = r - 1; l >= 0; --l) {
            score[l][r] = range_sum(l, r) - min(score[l + 1][r], score[l][r - 1]);
        }
    }
    
    return score.front().back();
}

Kofta

What is the alpha here?

and can u explain how A and B and identical?

Oh, right. I didn't explain that alpha, did I? alpha is whatever remains from A[l][r] after xs[l] is taken: alpha := A[l][r] - xs[l]. It's just a temporary variable that helps in deriving the recurrence.

Now, regarding the sameness of A and B. As defined, A[l][r] is the top score for a player, when they have the first move on the range of [l, r]. And, whether that player 1st or 2nd is, is fully determined by the parity (even/odd) of the interval's length: r - l + 1. Thus, designating the A from the B is actually superfluous.

That's clear now

thanks

arvindr9

In the edit distance problem, it says -- "When we calculate dp[i][k], there are four possibilities to consider for the rightmost operation. We check all of them and take the cheapest one."

Why do we only need to consider the rightmost operation? I feel this is worth discussing (either in the post or as a reply to my comment).

rupav

23 months ago, # |

← Rev. 4 →

In Coin Combinations 2, you don't need extra dimension/state. dp[x + 1] = {0} would work fine. dp[0] = 1. dp[i] represents no. of ways to reach value 'i' with coins considered so far. So loop through coins in any order, and update values of future states of dp by looping through previous states of dp from left to right i.e. from 0 to x. That is dp[current_coin + state] += dp[state];

Spoiler - Code


#include<bits/stdc++.h>
using namespace std;
 
#define watch(x) cout << (#x) << " is " << (x) << endl
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i, st, en) for(int i=st; i<=en; i++)
#define repn(i, st, en) for(int i=st; i>=en; i--)
#define sq(a) (a) * (a)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll mod = 1e9+7;
 
#define INF INT_MAX
 
void add_self(int &a, int b){
    a += b;
    if(a >= mod) a -= mod;
}
 
void solve(){
    int n, x;
    cin>>n>>x;
    int c[n];
    fr(i, n) cin>>c[i];
    vector<int> dp(x + 1, 0);  /// dp[i] = no. of ordered ways to have value i
    dp[0] = 1;
    for(int coin: c){
        for(int i = 0; i + coin <= x; i++){
           add_self(dp[i + coin], dp[i]);
        }
    }
 
 
    cout<<dp[x];
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    ll t = 1;
    //  cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

Space: O(target)

Time: O(target * n)

hackerakhil

Can you please clarify your approach?

MesutOzil

Can anyone explain me the array description question? Or just explain me the output of this test case: 4 5 2 0 3 0 I thought it would be 6 but it turns out to be 2. Any help would be appreciated.

I_use_cpp

Hope it's still relevant: https://ideone.com/ATMahc

rum3r

Thanks, to icecuber for writing an amazing editorial. Without this I wouldn't have thought of even touching single dp problem and someone can explain the array description problem.

sarkarasm

In Coin Combinations II(1636) shouldn't the vector x be sorted?

Sumanto

Two Sets II (1093) problem we can also do it in normal way (that is including n too) then finally divide by 2 to avoid repetition. NOTE:- use modulo inverse while performing division.

CODE

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define F first
#define S second
#define _READ freopen("input.txt", "r", stdin);
#define _FAST                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
const int mod=1e9+7;
void add(int &a,int b)
{
    a=(a+b)%mod;
}
int power(int a,int b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a;
    int x=power(a,b/2);
    if(b%2==0)
        return (x*x)%mod;
    return (x*x*a)%mod;
}
int32_t main()
{
    _FAST
    int n;
    cin>>n;
    //dp[i]--> number of ways to form i using all available number from 1 to n
    int sum=n*(n+1)/2;
    if(sum%2==1)
    {
        cout<<"0";
        return 0;
    }
    sum/=2;
    vector<int> dp(sum+1,0);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=sum;j>=i;j--)
            add(dp[j],dp[j-i]);
        // cout<<i<<"-->  ";
        // for(int j=1;j<=sum;j++)
        //     cout<<dp[j]<<" ";
        // cout<<"\n";
    }
    //cout<<sum<<"\n";
    cout<<(dp[sum]*power(2,mod-2))%mod;
    return 0;
}

bhuvnesh97

In the problem two set (1093) u said that if we count subset till the last element than we end up repeating the same set twice.so we can get our desired answer by just dividing it by 2. but here it fails .

AdnanShamsi

you cant divide it by two because you did mod operation ,all you can do is multiply it by multiplicative inverse of 2 and mod .

you can watch this https://www.youtube.com/watch?v=TOsD3BkIKoQ&feature=youtu.be he was having the same problem as yours

TheLogiqueViper

please consider making one editorial on graph section also icecuber

YGBoss007

In problem Projects(1140), I'm not able to get the compressing the days part. Can anyone explain with an example?

kartik8800

22 months ago, # |

I am making detailed video explanations for some of the problems of this section, I will keep updating this comment whenever I add a new video. Along with the explanation I live code the solution at the end of the video and submit the code on the platform.

Interested may check the following videos.
Dice Combinations: https://youtu.be/5gd5jptXWAM
Coin Combinations: https://youtu.be/-pXjopzMVrE
Grid Paths: https://youtu.be/V64F4wlodUM
Book Shop: https://youtu.be/qpNy2nuSuaI
Also added on my channel videos for coin combinations 2, array Description, removing digits, edit distance, Rectangle cutting and projects.

Hopefully people will find this helfpul.

Links to Video solution for all problems can be found here: https://codeforces.com/blog/entry/80064

code_warrior

Editorials like this should be appreciated!

cmlivb

Thanks for this :p

Priyansh31dec

I have been trying the problem Book Shop for a very long time now. I am using the same logic as given by you. Still, it is giving me TLE. Is there any other approach for this question or some optimization that I can do on my code:

Here is my code:


/* Priyansh Agarwal*/
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define nline "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define debug(x) cout << #x << " " << x <<endl;
#define set_bits __builtin_popcount
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
int main()
{
	fastio();
	int n; ll x;
	cin >> n >> x;
	int value[n];
	int weight[n];
	for (int i = 0; i < n; i++)
		cin >> weight[i];
	for (int i = 0; i < n; i++)
		cin >> value[i];
	int **dp = new int*[n];
	for (int i = 0; i < n; i++)
		dp[i] = new int[x + 1];
	for (ll i = 0; i <= x; i++)
	{
		for (ll j = 0; j < n; j++)
		{
			dp[j][i] = j - 1 >= 0 ? dp[j - 1][i] : 0;
			if (weight[j] <= i)
				dp[j][i] = max(dp[j][i], (j - 1 >= 0 ? dp[j - 1][i - weight[j]] : 0) + value[j]);
		}
	}
	cout << dp[n - 1][x];
	return 0;
}

Incase you missed it, I have replied to your comment on my youtube video: "Honestly it's sad that the time limit on the platform is very tight. Try changing the loops, make outer loop for n and inner loop for x and it should pass. Try it and tell me if it works. I'll give you a plausible explanation why this works."

Yes, I just did that and it worked. But, I have no idea why this happened. The time complexity for both of them is same but just interchanging the loops is reducing the time it is taking for the program to run. Looking forward to your explanation on this. And yes, Thanks a lot.

I am no expert but here is what I can tell you, There is something known as locality of reference, if your program uses a part of the memory which is located in contiguous memory addresses(or nearby memory addresses) it will execute faster.

Why is that so?
Caching. The OS(again I am no expert, but hopefully someone will put more light on this) will cache some of the regions of the data stored in main memory, accessing cache is much faster than accessing main memory.

Ever Thought why iterating an array is much faster than iterating a link list of same size even though asymptotically both of them are O(N) operations.

Try laying out your 2d array and think which of two approaches will make more compact memory region accesses.
Hope this helps!

Thanks for the reply again but correct me if I am wrong, If I have 2D array of N*X and another of X*N and in both of them I iterate wouldnt it take the same time. I understood the part that contiguous memory will be faster to iterate on but aren't both the loops doing the same thing. In both cases we are iterating on contiguous memory locations. In the first case, we will do like X iterations N times and in the second we will do N itetations X times. So, does it affect the running tume considering X is greater than N. Sorry for the trouble but it would really help me if you van explain a little by taking an example. How about you explain this when N is 2 and X is 5. This will really clear the doubt.

keeping in mind caching and locality of reference think which of the two recurrences will likely evaluate faster:
1. dp[i] = f(dp[i-1])
2. dp[i] = f(dp[i-some_random_number(1,i)])

In main memory 2d, 3d, 4d all arrays are flattened and stored as 1d arrays. So flatten N.X array into N arrays of size X each and X.N array into X arrays of size N each.

Take 5mins and then check if this pic helps you a bit:
Even I would appreciate a response from someone who is an intermediate or expert at COA and OS concepts but till then this is the best explanation I can come up with.

Ohhh I think now I am having a much better understanding of this thing. The picture was quite explanatory. I looked at both of my codes and realised this is actually quite sensible. When I am doing dp[i-1][j- some random number] it is like going 1 time back in 10^3 array and then it is about 10^5 places to move in the end to reach j-some random number. But in case I do dp[j-some random number][i-1] it will go back in 10^5 array which has 10^3 size sub array and this will happen arbitrary number of times so it becomes 10^8. I guess this is only what you are trying to say. Thanks for the wonderful explanation, really appreciate your effort to explain this. I have understood it.

Yes that is what I was trying to say, I am glad it helped :)

viyaaat

bro,can you send solution for elavator rides question

sumeet_4275

19 months ago, # ^ |

Bro, could you please share your code, i am kinda stuck here i thought the correct way yet it gives TLE due to tight limits, i even tried kartik's way maybe i didnt do it rightly

confusedman

Another way is to just do a 1D dp, which is possible since the transitions only ever access [j-1].

1001001

Sharing a 1D dp approach

code

/*
Dynamic Programming - Book Shop
https://cses.fi/problemset/task/1158
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

double EPS=1e-9;
int INF=1000000005;
long long INFF=1000000000000000005ll;
double PI=acos(-1);
int dirx[8]={ -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8]={ 0, 1, -1, 0, -1, 1, -1, 1 };
const ll MOD = 1000000007;

#define DEBUG fprintf(stderr, "====TESTING====\n")
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
#define OUT(x) cout << x << endl
#define OUTH(x) cout << x << " "
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define READ(x) for(auto &(z):x) cin >> z;
#define FOR(a, b, c) for (int(a)=(b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a)=(b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (int(a)=(b); (a) >= (c); --(a))
#define FORSQ(a, b, c) for (int(a)=(b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a)=(b); (a) <= (c); ++(a))
#define EACH(a, b) for (auto&(a) : (b))
#define REP(i, n) FOR(i, 0, n)
#define REPN(i, n) FORN(i, 1, n)
#define MAX(a, b) a=max(a, b)
#define MIN(a, b) a=min(a, b)
#define SQR(x) ((ll)(x) * (x))
#define RESET(a, b) memset(a, b, sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)


void solve() {

}

int main()
{
    FAST_INP;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r", stdin);
    // freopen("output.txt","w", stdout);
    // #endif

//    int tc; cin >> tc;
//    TC(tc) solve();
	int n, x;
	cin >> n >> x;
	vi h(n), s(n), dp(x+1,0);
	READ(h);
	READ(s);
	REP(i,n) FORD(j,x,h[i]) MAX(dp[j], dp[j-h[i]]+s[i]);
	OUT(dp[x]);
    return 0;
}

My code is simillar to yours except the inner loop is from h[i] to x but it's not working, do you know why ?

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define endl "\n"
typedef long long ll;
using namespace std;
int dp[int(1e6+10)];
int main()
{
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
    #endif
    ios::sync_with_stdio(false);
    int n,x,price[1010],page[1010];
    cin>>n>>x;
    for(int i=0;i<n;i++)
        cin>>price[i];
    for(int i=0;i<n;i++)
        cin>>page[i];
    for(int i=0;i<n;i++)
        for(int money=price[i];money<=x;money++)
            dp[money]=max(dp[money],dp[money-price[i]]+page[i]);
    cout<<dp[x];
    return 0;
}

zukonit14

Thanks a lot for this! Best problems for beginner in DP and editorial is perfect for beginner to understand dp!

NeutralMilkHotel

https://pastebin.com/mVN1rXrz Can Someone tell me the issue with my code of edit distance .It passes all the test cases but fails in one and I have been trying to debug for over an hour but couldn't find the bug.

NiteshSharma5

No you can't because there is no option to see other's code.

BYE_BYE2020

You can go to hacking section after submitting your code and you can hack other's code where you can see others code This is only the way to see other's code Hope this help

Punisher

21 month(s) ago, # |

This is my code for (Two sets II) problem. My approach:- dp[i]= number of ways to make sum using subset 1..i.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	ll mod=1e9+7;
	int sum=(n*(n+1))/2;
	if(sum%2){
		cout<<0;exit(0);
	}
	sum/=2;
	vector<ll> dp(sum+1);
	dp[0]=1;
	for(int i=1;i<=n/2;i++){
		for(int j=sum;j>=0;j--){
			if(j-i<0)continue;
			dp[j]+=dp[j-i];
			dp[j]%=mod;
		}

	}
        //total number of ways would be double since i am counting for both the sets.
	dp[sum]/=2;
	dp[sum]=(dp[sum]%mod+mod)%mod;
	cout<<dp[sum];

}

Can anyone help me find my mistake?

you can't make dp[sum]/=2 after module

you need to use modular inverse for the divison problem

kuldeepsingh00

Can we go for Removing Digits like this. Errichto and icecuber sir give me some shine

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

// n = 27, 27->20->18->10->9->0

int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    vector<int> v;

    while(1){
        int x = n;
        while(x)
        {
            int rem = x%10;
            x = x/10;
            v.push_back(rem);
        }

        int m = *max_element(v.begin(), v.end());
        n = n-m;
        if(n>=1){
            cnt++;
            v.clear();
        }else {
            if(n == 0){
                break;
            }
        }
    }
    cout << cnt+1 << endl;
    return 0;
}

i'm just giving my openion. Thankyou

Hisham_hates_graphs

in minimizing coins: O(n.target)->could be 1e8 operation

how it works in 1 second

bever209

hey did anyone else get a runtime error (like heap space error or something) on coin combination 2 or is it just my code?

Can someone explain why the solution for increasing subsequence works? Specifically I am confused about how we can replace an element in the dp array with an element later found. Doesn't this not make dp a subsequence?

__SON-GOKU__

i know its not a big thing you we don't need a two state dp for problem combinations2 one is enough.

vegManchow

Figured it.

for array description can anyone tell me where i have gone wrong https://ideone.com/FsF43S

i didn't get about removal game can anyone make me understand why we have to take the mean at the end

moli2398

As stated, score1 + score2 = sum. With our dp, we calculate max(score1 — score2).

Add both of these, sum + (score1-score2). = score1 + score2 + score1 — score2 = 2 * score1

Divide by 2 to get max score1.

aneee

20 months ago, # |

Hey! Can someone give the formal proof for the Greedy Solution of 'Removing Digits'?

I tried to formulate a proof, but no luck :(

cwd_fan

using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define mp(a,b) make_pair(a,b)
#define pb(x) push_back(x)
const ll mod = 1e9 + 7;
ll inf = 1e16;
struct mys{
	ll s,e,m;
};

bool comp(mys &x, mys &y){
	return x.e <= y.e;
}

void solve()
{
  ll n;
  cin>>n;
  mys arr[n];
  for(ll i=0;i<n;++i){
  	cin>>arr[i].s>>arr[i].e>>arr[i].m;
  }
  sort(arr,arr+n,comp);
   
  ll pre[n];
  ll i,j;
  i = n-1;
  j = n-1;
  while(j>=0){
  	j = i-1;
  	while( j >=0 && arr[j].e>= arr[i].s){
  		--j;
	  }
  	 if(j!=-1){
  	 	pre[i] = j;
  	 	i-=1;
	   }
  }
  while(i>=0){
  	pre[i]=-1;
  	--i;
  }
  // ** upto the getting pre array
  ll dp[n+1];
  dp[0]=0;
  for(ll i=1;i<=n;++i){
  	dp[i] = max(dp[i-1], arr[i-1].m + dp[pre[i-1]+1]);
  }
  cout<<dp[n]<<endl;
}

int main()
{
	ll test=1;
	while(test--)
	{
		solve();
	}
	return 0;
}

for projects problem can anyone check it is giving wrong verdict only for 2 cases even though code looks correct can anyone check?

AbdullaNurFaisal

19 months ago, # |

Can someone give a top down recursive dp implementation of problem** Array description**? It does not have to pass in the given TL due to being recursion but the recursive dp should be accurate.

ChitreshApte

Thanks for the great editorial. I solved some problems on my own. If I didn't got the logic for some, I read the editorial and got the idea. Some problems involved some good tricks which I learnt. Thanks a lot.

Why does taking the mean like this for problem "removal game" work?

18 months ago, # |

what is the top-down approach for coin combination I and II?

UPD: got it.

Newton_01

Thanks for the editorial.

let_the_game_begin

for this problem why the recursive solution works, even if we take n instead of n-1.

vector<vector<int>>dp;
int n;
int solve(int current , int sum)
{
   if(current<1) return 0;
  
   if(sum==0)
   return 1;
 
   if(sum<0) 
   return 0;

   if(dp[current][sum]!=-1) return dp[current][sum];

    int ans = 0;

    ans = (ans + solve(current-1,sum-current))%MOD;
    ans = (ans + solve(current-1,sum))%MOD;

   return dp[current][sum] = ans;
}
int main(){

cin>>n;
    int  sum = ((n)*(n+1))/2;
    if(sum&1)
    {
      cout<<0;
      return;
    }
   int  req = sum/2;

    dp.resize(n+1,vector<int>(req+1,-1));
    cout<<solve(n , req);

}

When current = 1 and sum = 1 when you go to solve(0,0) you returns 0 because of condition current<1 returns 0

your code is not taking 1 in the first set instead of n

cjchirag7

The problem Projects — 1140 can also be solved without using the compression technique.

Approach

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;
struct event {
  int start, end, profit;
};

bool comp(event e1, event e2) { return (e1.start < e2.start); }

vector<event> events;
vector<int> dp;

int solve(int i) {
  if (i == n) return 0;
  if (dp[i] != -1) return dp[i];
  int p = events[i].profit;
  int ans = solve(i + 1);
  event e = {events[i].end + 1, events[i].end + 1, 0};
  int ind = lower_bound(events.begin(), events.end(), e, comp) - events.begin();
  if (ind != n) {
    ans = max(ans, p + solve(ind));
  } else
    ans = max(ans, p);
  return dp[i] = ans;
}

int32_t main() {
  cin >> n;
  events.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> events[i].start >> events[i].end >> events[i].profit;
  }
  sort(events.begin(), events.end(), comp);
  dp.assign(n + 1, -1);
  cout << solve(0);
  return 0;
}

Vik

16 months ago, # ^ |

Beautiful code! Thanks for sharing cjchirag7!

tiasmondal

17 months ago, # |

Why does CSES problem Set give TLE in some problems (in one or two test cases), even if my asymptotic time complexity is the same as that of the intended solution?

rishi

In Rectangle cutting, one can exploit symmetry and stop both the innermost loops at i/2 and j/2 respectively.

hetp111

yes, you can.

pratikb2805

For the problem Removing Digits, I found another solution that works in almost the same time.


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int maxdig(int n)
{
    int ans = 0;
    while (n)
    {
        ans = max(ans, n % 10);
        n /= 10;
    };
    return ans;
}
int ans(int n)
{
    if (n < 1)
        return 0;
    return 1 + ans(n - maxdig(n));
}
int main()
{
    int n;
    cin >> n;
    cout << ans(n);
}

gwhiz

I'll just add a space optimized DP solution for Money Sums (Can be used for most knapsack problems)

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // int MOD = 1e9+7;
	int n;
	cin >> n;
	vector<int> coins(n);
	int sum = 0;
	for (int i = 0; i < n; i++) { cin >> coins[i]; sum += coins[i];}
	
	vector<bool> dp(sum+1);
	dp[0] = true;
	for (int coin : coins) {
		for (int v = sum; v >= coin; v--) {
		      dp[v] = dp[v] | dp[v - coin];
		}
	}
	
	vector<int> ans;
	for (int i = 1; i <= sum; i++) {
		if (dp[i]) {ans.push_back(i);}
	}
	
	cout << (int) ans.size() << endl;
	for (int i = 0; i < (int) ans.size(); i++) {
		cout << ans[i] << " ";
	}
	cout << "\n";
	return 0;
}

BidoTeima

Thank you so much! This is really useful :D

devol

Hey I am stuck in problem of Counting towers of DP section CSES problem set can someone plz help !! Thanks in advance..

palak987

i found this useful: youtube video solution

MK6

For Two Sets 2 Problem , I have used a similar approach as editorial.However I I have counted every pair of sets twice as I have considered numbers till n and returned dp[n][sum/2]. However my solution still got accepted.Any help in why this is so?

Makdi

A different approach using vector of pairs, sorting and binary search (nlogn) https://ide.geeksforgeeks.org/hCuD7Po9XT

Karansoni158

16 months ago, # |

Code for new problem counting towers.

long long dp[10000005][2]
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int test_case = 1;
    cin >> test_case;
    while (test_case--)
    {
        long long n;
        cin >> n;
        dp[1][0] = 1;
        dp[1][1] = 1;
        for(int i = 2;i<=n;i++){
            dp[i][0] = (4*dp[i-1][0] + dp[i-1][1])%mod;
            dp[i][1] = (dp[i-1][0] + 2*dp[i-1][1])%mod;
        }
        cout << (dp[n][0] + dp[n][1] )%mod<< endl;
    }
}

ShmilyTY

10 months ago, # ^ |

Thank you for your useful comment, but I'm too foolish to understand the code. :<

So could you please explain it a bit?

It would mean a lot if you could help me by taking some time off from your busy schedule.

elit_altum

Basically dp[i] means the number of ways to build a tower of height i. The next index means if the tile at the ith place is split or not. That is, if 0 the tile is split (2 tiles of 1 x 1) and if 1 we have a single tile of 2 x 1.

Finally, dp[i][0] means the number of ways to build a tower of height i such that the top tile is split ( 2 tiles of 1x1) and dp[i][1] means number of ways to build a tower of height i such that the top tile is continuous (1 tile of 2 x 1)

Now for the recursive function:

If the last tile is split (dp[i][0]), it can have the following options:

It can extend both the split tiles at (i — 1): dp[i - 1][0]
It can extend on the left split tile at (i — 1): dp[i - 1][0]
It can extend on the right split tile at (i — 1): dp[i - 1][0]
It can extend none of the split tiles at (i — 1) but add it's own: dp[i - 1][0]

This means 4*dp[i -1][0]

And the last case, it can add split tiles over the continuous tile of i - 1th height: dp[i - 1][1]

dp[i][0] = 4 * dp[i - 1][0] + dp[i - 1][1]

Similarly if the last tile is continuous (dp[i][1]):

It can extend the continuous tile at (i — 1): dp[i - 1][1]
It can not extend the continuous tile at (i — 1): dp[i - 1][1]
It can add a continuous tile over split tiles of (i — 1): dp[i - 1][0]

dp[i][1] = 2 * dp[i - 1][1] + dp[i - 1][0]

Hope this helps!

PS: Use an int array instead of vector in the code otherwise you'd get a TLE

fatal_vish

If someone is looking for memoization based solution for Removing Digits, then this might help.

#include<bits/stdc++.h>
using namespace std;

// function to find digits(not equal to 0) in a number
vector<int> findDigits(int n){
  vector<int> digits;

  while(n){
    if(n%10)
      digits.push_back(n%10);
    n /= 10;
  }

  return digits;
}

vector<int> memo(1000000);

int solve(int n){
  if(n == 0) return 0;

  // avoid recomputing by taking value
  // already present in memo
  if(memo[n] != 0) return memo[n];
  
  int min_operations = INT_MAX;

  vector<int> digits = findDigits(n);

  // this loop is responsible for chosing optimal
  // choice from all choices
  for(int digit : digits){
    min_operations = min(min_operations, 1+solve(n-digit));
  }

  memo[n] = min_operations;
  
  return memo[n];
}

int main(){
    int n; cin>>n;

    cout<<solve(n)<<endl;

    return 0;
}

kaons

It would be great if everyone could enclose their code into a spoiler, it creates unnecessary mess sometimes while navigating.

AmishM

I was trying to solve these problems using recursive dp, I was facing an issue in the Book Shop problem, I was getting runtime error on large test cases though I feel I am using the same space as required in iterative dp. Link to my solution.

Saransh_30

-9

Thanks for the solution.

icecuber For Two Sets II, why won't taking it all and dividing my 2 work?

My code: https://cses.fi/paste/1ea2ecdcdcc46e54190a53/

Is it because of mod?

yes, it's because of the mod. However for odd mod, you can divide by 2 by multiplying with 1/2 which is just (mod+1)/2.

Wow! Thank you so much :-)

hackerbhaiya

Just for information if mod is prime and you have to divide it by x, then multiply the numerator by pow(x,mod-2). Do not use predefined pow function. Create your own pow function to handle mod.

abdude824

15 months ago, # |

Can someone explain me this:

vector<vector<int>> dp(n+1,vector<int>(x+1,0));

in book shop problem in code given by author.

I was also implementing 0-1 Knapsack but it is giving me Runtime Error on both iterative and recursive solutions.

Link to Recursive: https://cses.fi/paste/f6b687511890d6331a4ea4/

Link to iterative: https://cses.fi/paste/3fbfe3cdf25c866d1a4e16/

UPD: When I just replaced int dp[n+1][x+1] with this code, the code worked. Please tell me what does this do?

rahulsharmaah

please add editorial for counting towers problem https://cses.fi/problemset/task/2413

lunchbox

See OEIS A034999

thanx man

spookywooky

Consider the top row of a rect filled with n rows. There are two cases. The both cells of the top row can belong to one element, or to two elements.

In both cases we can formulate how the numbers are calculated for n+1 rows.

Spoiler

* dp[i][j]=number of towers with hight i and 
 *   j=0: top row single elemnt; 
 *   j=1: top row two elements
 *
 * dp[1][0]=1;
 * dp[1][1]=1;
 * dp[i][0]=1+dp[i-1][0]+dp[i-1][1];
 * dp[i][1]=0+dp[i-1][0]+dp[i-1][1];

Pranav.exe

Bookmarked this blog. Thanks a lot :)

What about the Elevator Rides?

A hint would help. It seems to be some form of bitmask dp, but anything I implemented goes TLE :/

Here one of my

not working brute force solution

#include <bits/stdc++.h>
using namespace std;
 
const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();
 
const double PI = acos(-1);
using ll= long long;
//#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)
 
#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }
 
using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;
 
//#define endl "\n"
 
/* Since N=20 there are only 1e6 different
 * possibilities to choose some persons.
 * Each such combination has weight.
 * Use the ones with weight <=limit.
 *
 * Observations:
 * It never makes sense to send the elevator
 * while there could fit another person into it.
 * So, if we find a combination where
 * the weight is so heigh that we cannot put another
 * person into the elevator, then we can remove
 * all subsets of this set from possibilities, since
 * the would not make sense.
 *
 * step 1: find all subsets with weight<=max weight
 * step 2: remove all subsets of other sets from that list
 *      (iterating the numbers sorted by number of set bits desc???)
 * step 3: kind of dijkstra:
 *  sort the sets by included heaviest person first
 *  then use edges only from i to j if i<j
 *  and if heaviest person of i is not included in j
 * shortest path including all bits is ans.
 */
const int INF=1e9;
void solve() {
    cini(n);
    cini(x);
    cinai(w,n);
    sort(all(w));//, greater<int>());
 
    cerr<<"start"<<endl;
    const int N=1<<n;
    vb wok(N);
    for(size_t i=1; i<N; i++) {
        int aux=0;
        for(int j=0; aux<=x && j<n; j++) 
            if(i&(1<<j))
                aux+=w[j];
        if(aux<=x)
            wok[i]=true;
    }
    cerr<<"created wok"<<endl;
 
    for(size_t i=1; i<N; i++) {
        if(!wok[i])
            continue;
 
        for(int s=(i-1)&i; s; s=(s-1)&i)
            wok[s]=false;
    }
    cerr<<"optimized wok"<<endl;
 
    vi dp(N, INF);
    queue<pii> q;   /* q[cntBits]=vector<wokidx> */
    vi wok2;
    for(size_t i=1; i<N; i++) {
        if(wok[i]) {
            dp[i]=1;
            q.emplace(i,wok2.size());
            wok2.push_back(i);
            //cerr<<bitset<20>(i)<<endl;
        }
    }
 
    cerr<<"created wok2, size="<<wok2.size()<<endl;
 
    while(q.size()) {
        auto [mask,i]=q.front();
        q.pop();
 
        for(int j=i+1; j<wok2.size(); j++) {
            const int next=mask|wok2[j];
            if(dp[next]>dp[mask]+1) {
                dp[next]=dp[mask]+1;
                q.emplace(next,j);
                if(next==N-1) {
                    cout<<dp[next]<<endl;
                    return;
                }
            }
        }
    }
    cout<<dp[N-1]<<endl;
}
 
signed main() {
    solve();
}

nmnsharma007

My bitmask dp state was dp[mask] = minimum elevator rides possible for people in the mask and the weight less than x . Its a pair of the form {minimum elevator rides, weight}. For every mask, the people are fixed, so we try finding the minimum elevator rides for them by adding each person to the mask individually and check if the elevator rides were enough(by checking that weight of people stays less than x) or we need to add another ride to accommodate the new person.

akashtadwai

I tried to do it as a variant of Travelling Salesman Problem with dp[sum][msk] as min number of rides for people who are set in msk with their sum of weights as sum. I was using a map to cache the results. But it was giving TLE. I didn't understand why this is the case :( Any help would be appreciated.

C++ Code

#include <bits/stdc++.h>
using namespace std;
typedef std::pair<int, int> ipair;
#define int long long 
#define mod 1000000007
#define IOS                           \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);

int n, sum, x;
vector<int> a;
map<pair<int, int>, int> dp;
const int inf = mod;

int minRides(int sum, int msk)
{ // cur weight is sum of weights of people in msk.
    if (msk == (1 << n) &mdash; 1)
        return 1; // if all people are filled it takes one ride to finish
    if (dp.count({sum, msk}))
        return dp[{sum, msk}];
    int ans = inf;
    for (int i = 0; i < n; i++)
    {
        if (msk & (1 << i))
            continue;
        int n_mask = msk | (1 << i);
        if (a[i] + sum > x) // if we can't accomodate we make a new ride 
            ans = min(ans, 1 + minRides(a[i], n_mask));
        else
            ans = min(ans, minRides(sum + a[i], n_mask));
    }
    return dp[{sum, msk}] = ans;
}
void init()
{
    cin >> n >> x;
    a.resize(n);
    for (int &i : a)
        cin >> i, sum += i;
    cout << minRides(0, 0);
}
int32_t main()
{
    IOS;
    init();
    return 0;
}

pranav.vinchurkar

Check pages 103-104 of the CP Handbook.

bloomer

14 months ago, # |

How does changing the order of loops for Coin Combination I, II problems take care of the order property in the above solution?

agarwal_keshav

13 months ago, # |

-8

can anyone tell me why my code is giving runtime error on some of the test cases for problem Coin Combinations II

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int mod = 1e9+7;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin); 
        freopen("output.txt", "w", stdout); 
    #endif 
    ll n,x;
    cin>>n>>x;
    ll a[n+1];
    for(int i=1;i<=n;i++)
    cin>>a[i];
    ll dp[n+1][x+1];
    for(int i=1;i<=n;i++)
    dp[i][0] = 1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=x;j++)
        {
            ll option1 = (a[i] > j) ? 0 : dp[i][j-a[i]];
            ll option2 = (i==1) ? 0 : dp[i-1][j];
            dp[i][j] = (option1 + option2)%mod;
        }
    }
    cout<<dp[n][x];
    return 0;
}

Thanks in advance.

update: I found my mistake.changing the type of array dp from ll to int worked.

immadmohit

Thanks Alot Man, This will help alot!!

where_i_code_par

12 months ago, # |

Problem — Removal game Please someone help why this solution is getting wrong on some test cases?

include
using namespace std;
long long int dp[1000][1000];
int rec(long long int a[],long long int i,long long int j){
if(i>j) return 0;
if(dp[i][j]!=-1)
{
return dp[i][j];
}
//if(dp[i][j]!=0) return dp[i][j];
return dp[i][j]=max(a[i]+min(rec(a,i+2,j),rec(a,i+1,j-1)),a[j]+min(rec(a,i+1,j-1),rec(a,i,j-2)));
}
int main() {
long long int n;
cin>>n;
long long int a[n];
for(long long int i=0;i<n;i++){
cin>>a[i];
}
for(long long int i=0;i<=n;i++)
{
for(long long int j=0;j<=n;j++)
{
dp[i][j]=-1;
}
}
cout<<rec(a,0,n-1);
return 0;
} 1.

beast_sid

why my code is giving runtime error in CSES 7th problem (book shop)??.Please help me. link to code-https://cses.fi/paste/31a10089630000cd20d9fe/

tharadhemant259

Change ll to int and try again, I think it will work

Evil_Hunter

Can anyone tell me how to solve this dp problem https://cses.fi/problemset/task/1080

old._.monk

icecuber In problem Two sets II, I tried to find the number of ways to generate the sum n(n+1)/4 from the set, and my answer was its half.

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;

//------------------------------------------------------------

void solve(){
    int n;
    cin >> n;
    int sum = n*(n+1)/2;

    if (sum&1) {
        cout << 0 << endl;
        return;
    }
    sum /= 2;

    vector<int> dp(sum+1, 0);
    dp[0] = 1;

    for (int num = 1; num <= n; ++num){
        for (int i = sum; i >= num; --i){
            dp[i] = dp[i]%mod + dp[i - num]%mod;
        }
    }
    dp[sum] /= 2;

    cout << dp[sum] << endl;
}

// ------------------------------------------------------------

int32_t main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int t = 1;

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

This passed all the tests on CSES, but is this approach correct?

ND_

Coin Change 2 give TLE with O(n*target) time complexity

solution link: https://cses.fi/paste/c0e3ad19fd184ec3227a11/

rehsrug__27

While defining your dp vector just change it from vll dp(amount+1,0) to vi dp(amount+1,0). Using 'long long' instead of 'int' is probably why you're getting TLE

I tried it and got TLE again:https://cses.fi/paste/04b6ac464bf1ec0b228547/

Here have a look at this : https://cses.fi/paste/262b104a22044a1a22864a/ Just changed the way you applied your mod operation and the code got AC!

Yes got AC. Thanx. But why my code gave TLE even changing after vector to vi

DontLookBack

Can someone please tell me what is wrong with my recursive solution of Removal Game ?

It passes all the small cases but gives WA on large. I have applied minimax dp.

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 1e5+1;
const ll mod = 1e9+7;
const ll INF = 1e18;

ll dp[5005][5005][2];
vector<ll> a(5005);

int solve(int l,int r,int turn){
	if(dp[l][r][turn]!=INF)
		return dp[l][r][turn];
	ll ans;
	if(turn==0){
		ans = -1e17;
		if(l+1<=r)
			ans = solve(l+1,r,turn^1)+a[l];
		if(r-1>=l){
			ans = max(ans,solve(l,r-1,turn^1)+a[r]);
		}
		if(l==r)
			ans = a[l];
	}
	else{
		ans = 1e17;
		if(l+1<=r)
			ans = solve(l+1,r,turn^1)-a[l];
		if(r-1>=l)
			ans = min(ans,solve(l,r-1,turn^1)-a[r]);
		if(l==r)
			return -a[l];
	}
	return dp[l][r][turn] = ans;
}

void run_case(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++)
		cin >> a[i];
	ll s = accumulate(all(a),0LL);
	REP(i,5005)
		REP(j,5000)
			REP(k,2)
				dp[i][j][k] = INF;
	cout<<(s + solve(0,n-1,0))/2;

}

 
int main(){
	fast;
	int tt=1;
	while(tt--){
		run_case();
	}
	
	
}

nskybytskyi I learned this minimax technique from your recent videos on YT maybe you could help ? Thanks!

11 months ago, # |

Can anyone give me some hints or kind of editorial to solve the problem, Counting Towers?
Thanks in advance.

CrazyDave53

There are some youtube video explaining the approach, you can check it out. It helped me understand how to approach these kind of problem.

Mortal_code

Is there any way to do Coin Combinations I (1635) https://cses.fi/problemset/task/1635 with 2d dp

anushh23

In the book shop question ,I used the same approach but got Runtime error when I used long long int and with int ,my solution got accepted. Why is this so?

vbhar

I am submitting the following code for Coin Combinations 1 and getting TLE for the longer test cases.

Any suggestions ? Language : Python


N_MODULO = (10 ** 9) + 7


def main():
    count, amount = [int(i) for i in input().split()]
    coins = sorted([int(i) for i in input().split()])

    coin_counts = [0] * (amount + 1)
    coin_counts[0] = 1
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                coin_counts[i] = (
                    coin_counts[i] + coin_counts[i - coin]) % N_MODULO

    print(coin_counts[-1])


main()

satya.hyd11

I don't know why but the recursive approach is giving me TLE for some of the problems.

CSES grader is slower than CF, and recursive approach has higher constant factor than bottom-up.

minhi1

10 months ago, # |

I have a question for problem Projects. I wonder why when you compress, it has to be b[i]+1 instead of b[i]

n00brekt

i dont know DP, but when i will learn it i will sure prefer ur blog if i get stuck

who asked?

CrocHold

9 months ago, # |

A doubt Regarding that edit distance problem, would it not be fine if we just do it like. dp[i][nb,nb-1]... i goes all the way from 0 to na, but k takes only either nb or nb-1. i dont see any point of storing for all the k from 0 to nb...when we are just trying to make a equal to b and using only k and k-1. let me know if it makes any sense....thanks!

CodingPussyCat

8 months ago, # |

Nice and helpful problems

User7

Can anyone write recursive code of Coin Combinations II ?

s_arka

7 months ago, # |

any one please suggest a good you tube channel that will give me the wack through from recursion to DP approach

wpn10

Thanks for one of the best editorials!!

cprsd4

For Two Sets II (1093), the article above says the time complexity is O(n^3), isn't it supposed to be O(n^2)? Am I missing something?

Also, the solution seems to get accepted even if you include the nth element and not divide the final count by 2? See https://cses.fi/paste/c3ec33b10e14f1392ddcb6/

Blood_Lad

13 minutes ago, # ^ |

Target = n *(n + 1) / 4; for(i...n) for(j...target) => n * n * (n + 1)/4 => O(n^3);

_fire_fly_

I don't know why but when I declared 'MOD' globally its giving TLE int CSES but when it has been declared inside main Accepted. Can any one explain why this is happening?

tonymontaro

I made a YouTube playlist where I solved all the problems. Check it out here: https://www.youtube.com/watch?v=vuEWTjqf9Wo&list=PLC6tU0n3mgCL-WyIIxzNt5BEgPpquufeB&ab_channel=AnthonyNgene

Good luck.

Noelle-s-Stupidsta

great job

topcoder41

3 months ago, # |

counting tower ?? please provide counting tower solution as well.

3 months ago, # ^ |

Ohk

yashme7125

Thanks for giving editorials really it's helpful

PremUkkoji

7 weeks ago, # |

While doing Book Shop Problem, creating 2D vector of long long gives RE and creating 2D vector of int give AC. Does anyone know why this happens ?

2D vector may take up space complexity upto 10^8.

RE Code

        ll n, x;
	cin >> n >> x;
 
	vll price(n + 1), pages(n + 1);
	rep(i, 1, n + 1) {
		cin >> price[i];
	}
	rep(i, 1, n + 1) {
		cin >> pages[i];
	}
 
	vvll dp(n + 1, vll(x + 1, 0));
	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j <= x; j++) {
			if (j >= price[i]) {
				dp[i][j] = max(dp[i - 1][j], pages[i] + dp[i - 1][j - price[i]]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[n][x];

link to full code: https://cses.fi/problemset/result/3791349/

AC Code

        int n, x;
	cin >> n >> x;
 
	vi price(n + 1), pages(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> price[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> pages[i];
	}
 
	vector<vi> dp(n + 1, vi(x + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= x; j++) {
			if (j >= price[i]) {
				dp[i][j] = max(dp[i - 1][j], pages[i] + dp[i - 1][j - price[i]]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[n][x];

link to full code: https://cses.fi/problemset/result/3791442/

icecuber's blog

Dice Combinations (1633)

Minimizing Coins (1634)

Coin Combinations I (1635)

Coin Combinations II (1636)

Removing Digits (1637)

Grid Paths (1638)

Book Shop (1158)

Array Description (1746)

Edit Distance (1639)

Rectangle Cutting (1744)

Money Sums (1745)

Removal Game (1097)

Two Sets II (1093)

Increasing Subsequence (1145)

Projects (1140)

include<bits/stdc++.h>

define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

define pb push_back

define ll long long int

include