Codeforces Round 637 last week was declared unrated after the reference solution for problem E turned out to be incorrect, and the problem seemed to be unsolvable.
Therefore TopCoder SRM 784 was the first round that counted (problems, results, top 5 on the left, TCO qualification standings, analysis). The constructive hard problem required one to come up with a pattern, and some people did it much faster than others :) I could not come up with an explicit pattern myself, instead finding a pattern in row and column sums from solutions of small inputs, and finding the actual grid using max flow. This took me about 3 times longer than the fastest solutions to this problem, though, so I was out of contention for the top places. tourist was among the fastest solvers there, and he was also twice faster than me on each of the first two problems. Congratulations on the well-deserved victory!
Open Cup 2019-20 continued its non-stop return with the Grand Prix of Moscow (results, top 5 on the left, analysis). After the same 3 teams split the first 12 stages between them, we started getting new winners, and team japan02 is already the sixth team to win a stage this season. Congratulations on the superb performance!
In my previous summary, I have mentioned an Open Cup problem: you are given k (k<=200) distinct positive integers ai (ai<=105). Consider all sequences of length n (n<=1018) with all elements equal to one of the given integers. Count the number of those sequences with the given sum s (s<=1018). Is that number odd or even?
Since we're asked about the answer modulo 2, a natural idea is to try and discard groups of sequences which have an even count. There are actually multiple ways to do that, but for us the most natural way was to notice that since the order of the numbers matters, we can count the number of different orderings for each multiset of n numbers that add up to s, and discard those multisets for which this number of orderings is even. When our multiset has ci occurrences of the number ai, this number of orderings is given by the multinomial coefficient: n!/(c1!*c2!*...*ck!).
A quick Google query led us to this mathoverflow post, which tells that this coefficient is odd if and only if there is no carry when performing the addition c1+c2+...+ck=n modulo 2. This, in turn, means that for each bit that is set in n, there must be exactly one ci that has this bit set. Or, in other words, if the binary representation of n is 2b1+2b2+...+2bt, then we need to count the parity of the number of ways to take one of the ai's 2b1 times, one of the ai's 2b2 times (possibly the same one), and so on, so that the sum of all that is s.
I find it beautiful that there is a completely orthogonal argument that leads to exactly the same subproblem, obtained by noticing that the number of non-palindromic sequences is always even. You can find more details in this Codeforces comment.
Now, how to solve the subproblem? Given that s is up to 1018, it still seems to be a pretty tough instance of the knapsack problem. A naive approach would be to implement dynamic programming which counts the [parity of] the number of ways to reach every sum u<=s using the first i powers of two 2b1, 2b2, ..., 2bi, but the running time of that would be O(s*k*t), which is enormous.
However, we can notice that many states of that dynamic programming are actually useless! Suppose we're processing the powers of two in increasing order, and we have processed all powers of two up to but not including 2bi. Then everything that we will add later will be divisible by 2bi. Therefore, only the states that are equal to s modulo 2bi can contribute to the final answer. On the other hand, our current sum will not exceed m*(1+2+...+2bi-1)<m*2bi, where m is the maximum of ai. So there are at most m possible sums with the given remainder modulo 2bi, therefore our new solution runs in time O(m*k*t).
Since m=105, k=200 and t=60, this is about one billion operations — somewhat borderline. It was fast enough for us during the contest, but in case it would not be, I was planning to optimize it further taking advantage of the fact that we only care about parity, and therefore can use bitsets to represent our dynamic programming arrays and do operations on them.
Thanks for reading, and check back for this week's summary!
Since we're asked about the answer modulo 2, a natural idea is to try and discard groups of sequences which have an even count. There are actually multiple ways to do that, but for us the most natural way was to notice that since the order of the numbers matters, we can count the number of different orderings for each multiset of n numbers that add up to s, and discard those multisets for which this number of orderings is even. When our multiset has ci occurrences of the number ai, this number of orderings is given by the multinomial coefficient: n!/(c1!*c2!*...*ck!).
A quick Google query led us to this mathoverflow post, which tells that this coefficient is odd if and only if there is no carry when performing the addition c1+c2+...+ck=n modulo 2. This, in turn, means that for each bit that is set in n, there must be exactly one ci that has this bit set. Or, in other words, if the binary representation of n is 2b1+2b2+...+2bt, then we need to count the parity of the number of ways to take one of the ai's 2b1 times, one of the ai's 2b2 times (possibly the same one), and so on, so that the sum of all that is s.
I find it beautiful that there is a completely orthogonal argument that leads to exactly the same subproblem, obtained by noticing that the number of non-palindromic sequences is always even. You can find more details in this Codeforces comment.
Now, how to solve the subproblem? Given that s is up to 1018, it still seems to be a pretty tough instance of the knapsack problem. A naive approach would be to implement dynamic programming which counts the [parity of] the number of ways to reach every sum u<=s using the first i powers of two 2b1, 2b2, ..., 2bi, but the running time of that would be O(s*k*t), which is enormous.
However, we can notice that many states of that dynamic programming are actually useless! Suppose we're processing the powers of two in increasing order, and we have processed all powers of two up to but not including 2bi. Then everything that we will add later will be divisible by 2bi. Therefore, only the states that are equal to s modulo 2bi can contribute to the final answer. On the other hand, our current sum will not exceed m*(1+2+...+2bi-1)<m*2bi, where m is the maximum of ai. So there are at most m possible sums with the given remainder modulo 2bi, therefore our new solution runs in time O(m*k*t).
Since m=105, k=200 and t=60, this is about one billion operations — somewhat borderline. It was fast enough for us during the contest, but in case it would not be, I was planning to optimize it further taking advantage of the fact that we only care about parity, and therefore can use bitsets to represent our dynamic programming arrays and do operations on them.
Thanks for reading, and check back for this week's summary!
No comments:
Post a Comment