W4yneb0t would be a clear winner thanks to his correct solution for the 1000 - if not for the challenge phase, where K.A.D.R found 10 incorrect solutions for the 250 and managed to climb to the first place despite solving only the easiest problem - great job!
Coming up with a good challenge case wasn't easy at all. Here's what the problem was about: you have 20 skills to learn and 50 exercises, each exercise will give you a certain subset of skills (the subset for each exercise is fixed, but can be different for different exercises). If there are k skills you don't have yet among the skills that the exercise gives you, then you spend k2 effort on that exercise. What is the minimum total effort you must spend to learn all skills? Naturally, the greedy solutions just picked an exercise that adds the smallest number of skills at each step. Can you see how to make them fail? I'm also wondering how did people come up with such testcases during the round - was stress-testing the way to go?
The careful mathematical reasoning in the 500 was basically about finding a closed form solution to gambler's ruin. Of course, since this is a well-known task, one could replace the mathematical reasoning with Googling, which I duly did. I didn't know the term "gambler's ruin", though, so you can watch how I gradually converged to the right search terms starting from this moment of the screencast :)
Problem K, while being quite standard, allowed one to practice various dynamic programming techniques from this blog post. It went like this: you are given N numbers, and need to split them into M consecutive groups. The first number in each group is multiplied by 1, the second number in each group is multiplied by 2, and so on, and you need to minimize the sum of those products. And of course, you need a solution that's faster than O(N3).
During the contest, my teammate Ilya got the divide and conquer approach accepted, after the contest I've solved it using something similar to Knuth's optimization in upsolving, and the post-match discussion mentions that convex hull optimization also worked well :)
The solution is a classical case of gradually simplifying the problem until it becomes tractable. The first step is: let's try to gather some more knowledge from the fact that each CxD subrectangle has the same sum. More specifically, let's shift a CxD subrectangle to the right by 1. Now we can see that two 1xD columns that are C apart horizontally must also have the same sum.
Now let's shift those two 1xD columns down by 1. We can see that the differences between the corners are the same: a[x+C][y+D]-a[x+C][y]=a[x][y+D]-a[x][y]. Note that if this difference is not zero, then we can uniquely determine the values in the corners: for example, if the difference is 1, then a[x+C][y+D]=a[x][y+D]=1, and a[x+C][y]=a[x][y]=0. This, in turn, simply means that: if we have a[x][y] not equal to a[x][y+D], then all values in corresponding rows with step C are equal: a[x][y]=a[x+C][y]=a[x+2*C][y]=...=a[x-C][y]=a[x-2*C][y]=..., and the same for row y+D; a similar statement is true for columns.
At this point we can see that we've learned a lot about relations between cells that differ by a multiple of C horizontally and by a multiple of D vertically. In order to dissect the problem further, let's look at each such subgrid independently: take some offsets 0 <= c < C and 0 <= d < D, and consider all cells with coordinates (c+p*C,d+q*D). The above observation has a very concise meaning for this subgrid: whenever two horizontally adjacent cells in the subgrid have different values, the columns containing them are constant; and whenever two vertically adjacent cells in the subgrid have different values, the rows containing them are constant.
Having learned the exact structure of each subgrid, it's time to go back to the full grid. It consists of C*D subgrids, each in the form described above. Let's look at the fact that two 1xD subrectangles that are C apart horizontally: they must have the same sum. They include cells from D different subgrids. The corresponding cells in horizontal subgrids are equal, so we can simply disregard them. The corresponding cells in vertical subgrids might not be equal, so we have some constraints on the vertical subgrids now. In a similar manner, looking at Cx1 subrectangles that are D apart vertically helps us get some constraints on the horizontal subgrids. Moreover, it's not hard to see that those constraints are not just necessary, but sufficient: if every two 1xD subrectangles that are C apart horizontally have the same sum, and every two Cx1 subrectangles that are D apart vertically have the same sum, then it's not hard to see that all CxD subrectangles have the same sum, too.
So we have reduced the original problem to making sense of the constraints induced on the horizontal/vertical subgrids. We can note that horizontal and vertical subgrids have independent constraints, so we can analyze them separately. Moreover, the vertical subgrids, for example, have constraints in groups of at most D, and each such group of at most D vertical subgrids is constrained independently, so it suffices just to analyze one of them.
All that's left is to multiply the answers for the independent problems we've solved to get the answer for the problem. Well, almost all :) In the above solution we relied on knowing which subgrids are vertical and which are horizontal. In reality, we don't know that, but we have just C*D <= 16 subgrids, so we can iterate over all 2C*D ways, compute the answer for each case, and add those up.
This solution, will, however, count some grids twice: when a certain subgrid is constant, it is both vertical and horizontal, so we will count a grid containing such subgrid several times. In order to avoid that, we should remove constant subgrids from one of the sides, let's say from horizontal subgrids, and that will allow us to count each grid exactly once. In order to count the number of ways to fill a group of horizontal-but-not-constant subgrids, we have to use the inclusion-exclusion principle: start with the above computation that allows constant subgrids, subtract the number of ways to fill the grids such that one subgrid is constant, add the number of ways to fill the grids such that two subgrids are constant, and so on.
Finally, all loose ends are tied and we have a solution. Despite the length of the explanation, the code itself ends up being quite short. And the key idea, again, is to continue to simplify the problem in many small steps, and not give up early.
Thanks for reading (has anybody read this far?), and check back next week!
No comments:
Post a Comment