icecuber's blog

By icecuber, 3 months ago, In English,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
 
 
 
 
  • Vote: I like it
  • +192
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it +46 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +37 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                shoya right. exactly right.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Next Graph theory, please...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.