Preamble
Have you ever come across a problem that you couldn't solve, and that even after many people explaining it to you, you still couldn't understand?
Ever since I participated in the Round 923 Div 3 contest, I have kept the problem G — Paint Charges in the back of my mind. I have tried to understand how to solve it reading the editorial quite a few times, also how other people solved it in completely different ways. At a certain point, I couldn't help but feel quite frustrated that there were several ways to solve the problem, but all of them felt alien to me: "How on earth would I figure out that I want to use i,j and k meaning x,y and z, and that they are enough to describe the DP state for this problem? How am I supposed to find out that the transitions between the states are done like this?"
So I just had to come to terms with the fact that dynamic programming was a very weak point of mine, and to decide to put some work on finding the answers to my questions. I started solving some variations of coin change problems, 0-1 knapsack, longest increasing sequence (all of which I had done before, but feeling uncomfortable revisiting them after a while). Every now and then I would think "hey, let me check that Paint Charges again, maybe I have learned something now that could help me design a DP solution for it. No dice. OK, I'll keep solving some more problems and reading what some algorithms/competitive programming books authors have to say about DP",
I eventually came across this thread on CS StackExchange, where the answer was "a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way", complemented by Jeff Erickson's comment: "I claim that's the only strategy." Intrigued, I also went on to read Jeff Erickson's Algorithms, where I found this gem: "Many algorithms students ... make the mistake of focusing on the table ... instead of the much more important (and difficult) task of finding a correct recurrence."
That made a lot of sense. I needed to find the correct recurrence, otherwise even if I read the editorial and it said that I could solve it using i, j and k representing x, y and z, I would still have no idea how I could come up with those parameters meaning what they mean, or how they are related.
I also kept this insight in the back of my mind. However... that was still not enough for me to figure out how to solve the Paint Charges problem.
The road to ACC
Some weeks and some contests ahead, I was still thinking every now and then about how to solve the problem, and after solving a few other DP problems, during my daily walk with my dog, I kind of had an epiphany: what if I just try to solve it as a regular 0-1 knapsack problem?
Take 1: 0-1-knapsack-like DP solution (TLE)
In one typical 0-1 knapsack problem, we have the knapsack capacity, a set of objects with their respective weights and values, and we want to find the maximum value that we can get from the objects we choose to put in the knapsack not going over its capacity. The DP solution goes like: "for any of the objects in the set, an optimum solution either puts it in the knapsack or not. If we choose to put it, then the remaining capacity decreases, and then we need to find the optimum solution with the new decreased capacity and the remaining objects; if we choose not to put it, then we need to find the optimum solution with the full capacity and the remaining objects. Then, between the two options, we pick the one that gives the maximum value."
Not much different, the high level description for the solution I first came up with for the Paint Charges problem was: "For any one charge, an optimum solution either: ignores it, uses it to the right, or uses it to the left. If I choose to ignore the charge, then I need to find the optimum solution for the strip untouched and the remaining charges; if I choose to use the charge to the right, then I'll get the defined amount of cells to the right painted, and then I need to find the optimum solution with the new strip and the remaining charges; all the same to the left. Then, between the three options, I pick the one that uses less charges."
To represent the strip painting state, I used a BitSet (that, at least in Java, I can use to simulate the painting of a range of cells in an efficient manner). My guess was that this solution wouldn't be able to solve all the test cases fast enough, but even so, it was some progress, and seeing it being able to solve some test cases until it hit the expected TLE was quite a shot of adrenaline: submission.
This made me feel that I was on the right track, and all I needed was to find a way to optimize the solution. What was making it too slow? I knew that using BitSet instead of just a few indexes that other accepted solutions used to represent a state couldn't be as performant, but recreating the strip states and simulating the use of charges shouldn't be more than adding some constant times the number of states to the run time. Having already added memoization, I guessed the issue with my solution must be that it was exploring way too many states, maybe close to the exponential possible number of states, so I needed to think how I could trim down that number down.
Take 2: Trimming down states painting to the right (TLE)
Alright, let's say my solution choose to leave all the charges at the right end of the strip unused, and then at a certain i cell it will explore the option of painting it to the right. From the i-th cell, my solution could see that it needed to paint all the way to the end of the strip. Is its charge enough to cover all the way down to the end? If it is, then it's worth a shot at it, but if it's not, why bother? Some other charge after it would still be needed to cover all the way to the end. So let's just skip exploring this possibility: submission.
At this point I felt I was on the verge of finding the correct parameters, because I knew from the editorial that the parameters were something about the closest unpainted cell, farthest unpainted cell, etc. I trimmed down some states that wouldn't be worth exploring by using charges to the right, there should also be some way to trim states that would use charges to the left.
Take 3: Trimming down states painting to the left; lucky guess of recurrence (shameful ACC)
So far my solution was going from the right to the left end of the strip, keeping track of the last unpainted cell to the right to make a decision of whether it was worth using a charge to the right. But is it always worth it using a charge to the left? If my first cell on the right end painted the whole strip to the left, it would be useless to use the charge of my second cell to the left, as it wouldn't make any progress. So it would make sense to avoid exploring the case of using the charge of cell i to the left whenever we were in a state where the strip was already painted further to the left than could be reached by using the charge of cell i.
At this point I thought, well, I have three parameters kind of keeping track of my progress, i, last unpainted cell to the right and first painted cell to the left, and the editorial also has three parameters, so maybe I can just get rid of the BitSet and memoize everything? submission.
Worked! Why?
Final take (for now): a clear recurrence (proud ACC)
Why are the first painted cell and the last unpainted cell be enough to keep track of the whole strip state? What about all the different states that might or might not be painted in between? Surely there are an exponential number of different states in between. Well, this was one key realization: they are enough to keep track of the whole strip state for the problem we need to solve, i.e., in the context of finding the minimum number of charges to paint the whole strip. My explicit intent for adding the parameter last unpainted cell to the right was to trim the solution from exploring states that I knew weren't worth exploring, but in fact, I finally realized that it also determines that it doesn't matter the configuration of painted/not painted cells in between the current cell the algorithm is processing and the last cell it needs to paint to the right. The number of charges between cell 0 and cell i to paint the strip all the way to the last unpainted cell to the right will be the same no matter how the cells are painted in between, because what we need to ensure in any case is that we can paint all the way to the last unpainted cell. Even if all cells are painted but the last cell of the strip. A similar argument can be used about the first painted cell to the left: it doesn't matter how the cells are painted in between wherever we are and the first painted cell, the number of charges that is needed won't change.
Some takeaways and comments:
- Start from what I know: in this problem, start solving it as a good old 0-1 Knapsack problem allowed me to feel like I finally made progress, even if it wasn't still good enough to solve everything, and allowed me to think further on how to improve the solution instead of how to just get started.
- Understanding bottom-up DP solutions is hard (for me). Jeff Erickson's quote coming again: "Many algorithms students ... make the mistake of focusing on the table ... instead of the much more important (and difficult) task of finding a correct recurrence." When reading DP solutions by others, I find it close to impossible to understand statements like "we can use dp[i][j][k], i,j,k meaning x,y,z" from bottom-up solutions to DP problems. People are different, and for me (at least at this point where I am not completely familiar if DP), bottom-up implementations can only come as a possible optimization. The takeaway is that: my first task in any problem involving DP is to find the recurrence, and once I have the recurrence, the top-down solution with memoization writes by itself, with no concerns about the correct order that the states must be solved. Only with the correct recurrence at hand, I can see how the states depend on each other and then I can think in what order the states must be solved for a bottom-up solution.
- In my last submission I made a bunch of (unfinished) comments that I thought would be the "right" way to arrive at the solution and those comments were actually meant to be the contents of this blog post. Now that I'm about to finish writing this one, I think of it as a kind of "How I wish I had solved the Paint Charges problem", but I don't know whether this would be useful to anyone other than myself. However, I thought it would still be valuable to some newbies like myself, who sometimes get stuck in a problem for a long time, to see how I actually managed to make progress in this problem, instead of a hypothetical process that I wish I had followed. But in any case, if you made it this far in this wall of text and think my comments would be useful as a blog post, let me know!
Happy learning to you all!
