Formally speaking, last week had just one contest that I'd want to cover - the second stage of the Open Cup, also known as the Wide-Siberian olympiad. However, its results are not available because the award ceremony has not happened yet, so it will have to go into the next week's summary.
However, TopCoder SRM 638 happened very early this Monday, which can be attributed to the last week in some timezones (problems, results, top 5 on the left). Judging from the scoreboard, it was a very wild contest, so congratulations to Kazuhiro for overcoming most difficulties and claiming the first place!
Let's also return to one of the problems I've shared in the past: you're given a positive integer M, and need to come up with an instance of the knapsack problem which has exactly M solutions. More precisely, M is up to 1018, and you have to find at most 200 positive integers ai, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {ai} sum to W. Some ai might be equal, but they are still treated as different for the purpose of subsetting.
Here's how one might approach this problem: what are the standard tricks allowing us to "assemble" an arbitrary number up to 1018? Well, probably the most famous way of assembling numbers is positional notation: represent the number as the sum of powers of some base, for example 2 or 10. In order to apply it in our problem, we have to learn how to achieve powers of base, and how do we achieve the sum.
Let's concentrate on the second part first. In order to achieve summation, we can apply the following observation: out of all numbers greater than W/2, at most one will be used in any subset that sums to W. That means that if we have some set of numbers {ai} which has X subsets that sum to W and Y subsets that sum to some other number V that is less than W/2, the set of numbers {ai}+{W-V} will have exactly X+Y subsets that sum to W.
So if we had a way to find a set {ai} such that there are less than M subsets that sum to W, and all powers of two are found as the number of ways to achieve sum number less than W/2, we can add at most log(W) numbers and achieve exactly M ways to assemble W by representing the extra ways we need to add as the sum of powers of two.
However, it's not entirely clear how to achieve the powers of two for smaller numbers. But since we have quite a lot of room - we can have 200 numbers in our set, and log(1018) is about 60 - we don't need exact powers of two! The only thing we need is such set {ai} that the number of ways to achieve small numbers is sufficiently dense in the logarithmic scale. If that is the case, then applying the greedy algorithm - repeatedly taking the largest number that doesn't take us over the required sum - to represent M as the sum of those numbers will yield less than 200 numbers in all cases.
Having made this observation, we can try serveral possibilities for the set {ai} on our computer and output the number of ways to assemble 1,2,... using those numbers - our goal for those numbers of ways is to grow with roughly constant exponential speed. The set that worked for me during the actual contest was: 70 random numbers, each between 1 and 5, with 5s being more likely and 1s being less likely (the exact formula I used was "5 - random.nextInt(random.nextInt(5) + 1)"). Such set yielded the following number of ways to achieve 0,1,2,... as the sum:
1
3
9
24
69
194
464
...
769063368889619578
893415583044613189
1034306623895263056
The last number is greater than 1018 and is the number of subsets that sum to 99. Also, since we have 70 numbers up to 5, their sum is at most 350, so if we put W=500, there will be 0 ways to achieve that sum using only our 70 small numbers, and we can then add appropriate numbers between 402=500-98 and 500 to the set to achieve exactly M subsets that sum to W using the addition trick described above.
Please tell if something isn't clear from my explanation, or if you have alternative approaches you want to share. Also, of course, check back next week for the results of the Wide-Siberian olympiad and other contests! Finally, here's some Zurich fall mood for you:
Let's also return to one of the problems I've shared in the past: you're given a positive integer M, and need to come up with an instance of the knapsack problem which has exactly M solutions. More precisely, M is up to 1018, and you have to find at most 200 positive integers ai, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {ai} sum to W. Some ai might be equal, but they are still treated as different for the purpose of subsetting.
Here's how one might approach this problem: what are the standard tricks allowing us to "assemble" an arbitrary number up to 1018? Well, probably the most famous way of assembling numbers is positional notation: represent the number as the sum of powers of some base, for example 2 or 10. In order to apply it in our problem, we have to learn how to achieve powers of base, and how do we achieve the sum.
Let's concentrate on the second part first. In order to achieve summation, we can apply the following observation: out of all numbers greater than W/2, at most one will be used in any subset that sums to W. That means that if we have some set of numbers {ai} which has X subsets that sum to W and Y subsets that sum to some other number V that is less than W/2, the set of numbers {ai}+{W-V} will have exactly X+Y subsets that sum to W.
So if we had a way to find a set {ai} such that there are less than M subsets that sum to W, and all powers of two are found as the number of ways to achieve sum number less than W/2, we can add at most log(W) numbers and achieve exactly M ways to assemble W by representing the extra ways we need to add as the sum of powers of two.
However, it's not entirely clear how to achieve the powers of two for smaller numbers. But since we have quite a lot of room - we can have 200 numbers in our set, and log(1018) is about 60 - we don't need exact powers of two! The only thing we need is such set {ai} that the number of ways to achieve small numbers is sufficiently dense in the logarithmic scale. If that is the case, then applying the greedy algorithm - repeatedly taking the largest number that doesn't take us over the required sum - to represent M as the sum of those numbers will yield less than 200 numbers in all cases.
Having made this observation, we can try serveral possibilities for the set {ai} on our computer and output the number of ways to assemble 1,2,... using those numbers - our goal for those numbers of ways is to grow with roughly constant exponential speed. The set that worked for me during the actual contest was: 70 random numbers, each between 1 and 5, with 5s being more likely and 1s being less likely (the exact formula I used was "5 - random.nextInt(random.nextInt(5) + 1)"). Such set yielded the following number of ways to achieve 0,1,2,... as the sum:
1
3
9
24
69
194
464
...
769063368889619578
893415583044613189
1034306623895263056
The last number is greater than 1018 and is the number of subsets that sum to 99. Also, since we have 70 numbers up to 5, their sum is at most 350, so if we put W=500, there will be 0 ways to achieve that sum using only our 70 small numbers, and we can then add appropriate numbers between 402=500-98 and 500 to the set to achieve exactly M subsets that sum to W using the addition trick described above.
Please tell if something isn't clear from my explanation, or if you have alternative approaches you want to share. Also, of course, check back next week for the results of the Wide-Siberian olympiad and other contests! Finally, here's some Zurich fall mood for you:
No comments:
Post a Comment