Codeforces Round 319 took place on Thursday (
problems,
results, top 5 on the left,
solution analysis). I did not take part, but I heard that the problems were somewhat different in style from
the last round - and yet the people in the first two places are the same. Huge congratulations to Marcin_smu and mnbvmar!
TopCoder SRM 667 happened one day later (
problems,
results, top 5 on the left,
my screencast). The round was very tricky, with
250 inviting a lot of incorrect greedy solutions, the
500 requiring a lot of careful mathematical reasoning, and
1000 being a "constructive" problem which was hard to even approach.
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 k
2 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 :)
Open Cup 2015-16 Grand Prix of Ukraine has ignited the new season of the Open Cup on Sunday (
results, top 5 on the left). Quite a few veteran teams participated, but the first place still went to a team that will participate in ACM ICPC this year - great job, NNSU!
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(N
3).
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 :)
Finally, let me come back to the 4x4 problem from
last week,
counting the number of AxB rectangles of 0s and 1s such that each CxD subrectangle contains the same number of 1s. C and D are up to 4, so the subrectangle is very small, but A and B are up to a billion.
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.
Now it's quite easy to make the next step: we can notice that the two situations (two constant rows and two constant colums) are mutually exclusive: if there's at least one constant row, then there can be no two constant columns with different values, and vice versa. This, in turn, simply means that there are just two possibilities for the entire subgrid: either all rows are constant (we will call such subgrids "horizontal"), or all columns are constant (we will call such subgrids "vertical"). Of course, a subgrid can be both horizonal and vertical at the same time, in case all values are equal.
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.
And finally, we can see that the remaining problem is not hard anymore. We have a group of n <= D vertical subgrids, and we need the sum in each column to be the same. If this sum is m, then there are C(n,m) ways to pick one column, and thus C(n,m)t ways to pick all subgrids, where t is the number of columns (which is equal either to A/D or A/D+1, depending on the offset of the subgrid). Summing this over all values of m, we get the total number of ways to fill these n vertical subgrids.
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!
