The past week didn't have any major competitions in the beginning, but it ended with one big contest on each of Friday, Saturday and Sunday.
On Friday, Codeforces Round 204 took place (problems, results). It featured five problems, each requiring a non-trivial insight/trick to be solved. Congratulations rng_58 for solving them all and achieving a very compelling victory! I could only solve three, and was a bit demoralized by seeing a lot of people submit problem E which I had no clue about. You can follow my lackluster performance here, although the video doesn't show the frustration:
Saturday was the day of TopCoder SRM 593 (problems, results). The problems were very technical and required careful implementation, in stark contrast to yesterday's mostly "a-ha" questions. Of course, this has also resulted in a lot of challenge opportunities. I was lucky that incorrect solutions for the easy problem in my room remained throughout the entire challenge phase, allowing myself full 15 minutes of challenging. Had there been somebody else in my room looking for the same bugs as I were, Egor would probably top the scoreboard. This is yet anothe example of the basic principle: always challenge the problem with the easiest solution first. Even if you think the solution for difficult problems are more likely to be incorrect, the time it takes to understand just one of them is much more than the time it takes to check a lot of easy solutions. Since a successful challenge is +50 no matter what the problem is, the choice is clear. You can follow my contest here:
Finally, on Sunday, the Fourteenth Open Cup has started. The final results of today's contest are still not published, so it will have to go in the next week's summary.
I also want to share an interesting similarity between this week's problems. Codeforces problem A was: you are given 2N numbers that you can round either down or up to the nearest integer, but exactly N numbers need to be rounded down, and N rounded up. What is the smallest possible difference between the sum of original numbers and the sum of the rounded numbers?
Somehow, I couldn't solve this problem. My thinking went like this: we need to make 2N choices, N one way and N the other way, so that the sum of the chosen numbers is as close as possible to the given number. That is a natural dynamic programming problem: let's calculate whether we can make A choices "the first way" from the first B numbers, yielding the sum C. But the number of possible combinations of A, B and C is ay too big - what to do?
It turned out that I was missing one simple observation. Suppose there are no exact integers in the input, so we have a full set of 2N choices. Then no matter how we choose N numbers to round up, and N numbers to round down, their sum will be the same! It's not hard to see that it will be the sum of all numbers rounded down plus N. Exact integers add some trouble, but the problem remains easily solvable after this observation is made. In the above dynamic programming terms, we can now see there will be just one feasible value of C for each (A, B) pair and thus there will be much less states (not to mention we don't need the dynamic programming at all now).
Now, TopCoder's medium problem went like this: you are given N unknowns, where each unknown lies in a given range [Li, Ri]. You want to separate the unknowns into two parts in such a way that the maximum possible different between the sums of unknowns in each part is minimized. For example, if the first part contains unknowns [2, 5] and [3, 4], and the second part contains just one unknown [5, 6], then the sought difference is 4: the sum of the first part can be any number between 5 and 9, and the sum of the second part is any number between 5 and 6. The worst case is when the first sum is 9 and the second sum is 5, for the difference of 4.
Again, it's easy to jump to dynamic programming quickly. Suppose we have processed the first K unknowns, and picked whether each unknown goes into the first part or into the second part. It's not hard to see that our state is the range of possible values for the difference between the first part and the second part. For example, suppose the three unknowns discussed above have been processed. Then the difference between the first part and the second part can be any number in range [-1, 4].
How does the dynamic programming transition look like? Suppose the current range for the difference is [P, Q], and we put unknown [A, B] into the first part. Then the new range for the difference is [P+A,Q+B]. Had we put the unknown into the second part, the range would be [P-B, Q-A].
But we aren't done yet. There are way too many combinations for K, P and Q. In order to solve this problem, you need one more observation. The difference between Q and P is always equal to the sum of lengths of ranges of the unknowns! In other words, adding an unknown [A, B] to either part increases Q-P by exactly B-A. So the parameter P is redundant, and we can only keep K and Q in our dynamic programming state, which was good enough in the TopCoder problem.
These two problems are examples of a somewhat general trick: if you come up with a dynamic programming solution that has too many states, it might well be that most states are unreachable and/or some states can be joined into one since they are handled in the same way anyway. However, as always with dynamic programming, there's no general way to come up with this reduction in size (or is there? one might try to implement the dynamic programming and see if there are many unreachable states on random inputs).
Thanks for reading, and see you next week!
Finally, on Sunday, the Fourteenth Open Cup has started. The final results of today's contest are still not published, so it will have to go in the next week's summary.
I also want to share an interesting similarity between this week's problems. Codeforces problem A was: you are given 2N numbers that you can round either down or up to the nearest integer, but exactly N numbers need to be rounded down, and N rounded up. What is the smallest possible difference between the sum of original numbers and the sum of the rounded numbers?
Somehow, I couldn't solve this problem. My thinking went like this: we need to make 2N choices, N one way and N the other way, so that the sum of the chosen numbers is as close as possible to the given number. That is a natural dynamic programming problem: let's calculate whether we can make A choices "the first way" from the first B numbers, yielding the sum C. But the number of possible combinations of A, B and C is ay too big - what to do?
It turned out that I was missing one simple observation. Suppose there are no exact integers in the input, so we have a full set of 2N choices. Then no matter how we choose N numbers to round up, and N numbers to round down, their sum will be the same! It's not hard to see that it will be the sum of all numbers rounded down plus N. Exact integers add some trouble, but the problem remains easily solvable after this observation is made. In the above dynamic programming terms, we can now see there will be just one feasible value of C for each (A, B) pair and thus there will be much less states (not to mention we don't need the dynamic programming at all now).
Now, TopCoder's medium problem went like this: you are given N unknowns, where each unknown lies in a given range [Li, Ri]. You want to separate the unknowns into two parts in such a way that the maximum possible different between the sums of unknowns in each part is minimized. For example, if the first part contains unknowns [2, 5] and [3, 4], and the second part contains just one unknown [5, 6], then the sought difference is 4: the sum of the first part can be any number between 5 and 9, and the sum of the second part is any number between 5 and 6. The worst case is when the first sum is 9 and the second sum is 5, for the difference of 4.
Again, it's easy to jump to dynamic programming quickly. Suppose we have processed the first K unknowns, and picked whether each unknown goes into the first part or into the second part. It's not hard to see that our state is the range of possible values for the difference between the first part and the second part. For example, suppose the three unknowns discussed above have been processed. Then the difference between the first part and the second part can be any number in range [-1, 4].
How does the dynamic programming transition look like? Suppose the current range for the difference is [P, Q], and we put unknown [A, B] into the first part. Then the new range for the difference is [P+A,Q+B]. Had we put the unknown into the second part, the range would be [P-B, Q-A].
But we aren't done yet. There are way too many combinations for K, P and Q. In order to solve this problem, you need one more observation. The difference between Q and P is always equal to the sum of lengths of ranges of the unknowns! In other words, adding an unknown [A, B] to either part increases Q-P by exactly B-A. So the parameter P is redundant, and we can only keep K and Q in our dynamic programming state, which was good enough in the TopCoder problem.
These two problems are examples of a somewhat general trick: if you come up with a dynamic programming solution that has too many states, it might well be that most states are unreachable and/or some states can be joined into one since they are handled in the same way anyway. However, as always with dynamic programming, there's no general way to come up with this reduction in size (or is there? one might try to implement the dynamic programming and see if there are many unreachable states on random inputs).
Thanks for reading, and see you next week!
No comments:
Post a Comment