Thanks for reading, and check back for more :)
Monday, October 28, 2019
A congratulations week
Thanks for reading, and check back for more :)
Sunday, October 27, 2019
A fusion week
If we didn't care about the number of edges, and just wanted to count all spanning sets, the following standard approach would be used: let's count all sets (there are 2m of them) and subtract the sets which are not spanning. Each set that is not spanning has a uniquely determined connected component containing the vertex 0. So for each possible non-full subset of vertices containing the vertex 0 we need to subtract the number of subsets of edges with both ends within that component that are spanning within that components times two to the power of number of edges with both ends outside that component. Thus we can determine the number of spanning subsets for each subset of vertices containing the vertex 0 using dynamic programming with a running time of O(3n) if we precompute the number of edges within that subset for each subset of vertices, and the powers of two.
Adding a parameter for the number of edges makes this dynamic programming run in O(3n*m2): for each of O(3n) (set, subset) pairs we need to iterate over the number of edges in the subset, and the number of edges being added outside the subset, and our dynamic programming transition looks like
dp[set,a+b]-=dp[subset,a]*comb(outside_edges(set,subset),b)
Where comb(outside_edges(...),b) is the combination number that counts the ways to pick b edges to be added in the disconnected part. O(3n*m2) was too slow in this problem, but how to make this solution faster?
In many problems (for example in the TopCoder problem from three summaries ago), the key idea is about collapsing a subproblem as a separate dynamic programming to reduce the number of states or the processing time for each transition in the main dynamic programming. In this problem, we're going to do the opposite: the combination number is computed by its own dynamic programming, so we're going to unwrap that dynamic programming and fuse it with the main one!
Our state will now be the set of vertices, the number of edges we got so far, and the number of outside edges, for each of which we need to take a decision whether we add it to our edge counter or not.
We can then do (I'm describing a "forward" dynamic programming everywhere in this post)
sub[set,a,outside_edges(set,subset)] += dp[subset,a]
for all subsets of set and all values of a, then
sub[set,a,o-1] += sub[set,a,o]
sub[set,a+1,o-1] += sub[set,a,o]
to reconstruct the combination number by trying two possibilities on whether to include the next outside edge, and finally
dp[set,a] -= sub[set,a,0]
to subtract the disconnected graphs once we have made all decisions on the outside edges.
The first statement runs in O(3n*m), the second block of statements runs in O(2n*m2), and the last statement in O(2n*m), so the running time now is O(3n*m+2n*m2) which is fast enough.
By fusing the combination number dynamic programming into the main one we could no longer reuse its results between different transitions in the main part, so our complexity could become O(3n*m3) after doing this. But we achieved a different type of reuse: we can now do the part that adds the outside edges for all values of subset of a given set, and for all values of a for a given set, at the same time instead of doing it separately for each (subset, a) combination by iterating over b as we did before.
This dynamic programming fusion looks to be a quite general technique, but I couldn't remember many problems where it appeared, apart from one large cluster of problems: dynamic programming on "broken profile" can be viewed as an application of such fusion to dynamic programming on "normal profile" and the sub-dynamic programming between two profiles. Do you have more examples?
Thanks for reading, and check back for more!
Saturday, October 26, 2019
A Stonefeang week
Thanks for reading, and check back for my solution of this problem!
A twenty billion week
The key idea is the following: a block of exactly 2*1010 consecutive coins is extremely useful when playing against a random player. If a random player makes a move inside this block, it will almost certainly be not at the boundary, and thus no further moves will be possible there, so unless we make a move at the boundary ourselves, this block behaves exactly like a block of size 2*1010-1, or a block of size 1010. However, if it's our turn and we need to do so, we can move at the boundary of this block and leave a block of size 1010 behind which still allows one more move. In other words, we can skip a move if we have a block of size exactly 2*1010 available.
Skipping a move turns a losing position for you into a losing position for other player, which means we can win with certainty if we know if the current position is winning or losing :) However, we don't know that in the general case. Instead of trying to determine it, let's just do the following: if there is a block of size >=3*1010, we can make a move that creates a block of size exactly 2*1010, let's do so. Otherwise if there's still a block of size at least 2*1010+1, let's make any move inside any such block.
At some point we will end up in a situation where all remaining blocks are of size between 1010 and 2*1010. The random player makes exactly one move in any such block, so it's very easy to determine if a position is winning or losing: losing positions have an even number of such blocks. If we are in a losing position, and there's still at least one block of size 2*1010 remaining, we can use the above trick to skip a turn and give the other player a losing position.
And since we always create such blocks while there are still large blocks remaining, and the random player can destroy them but does not always do so as it's more likely to move inside a bigger remaining block, the probability that we will have at least one block of size 2*1010 remaining when we reach that "simple" state with no bigger blocks is essentially 1.
Thanks for reading, and check back for more!
A week independent of x
The easiest problem in this round required a bit of creativity: you are playing a game that starts with 1012 coins arranged in a row. In one turn, each player must pick any 1010 consecutive coins and remove them. The remaining coins are not shifted, therefore the coins that were on both sides of the removed segment do not become consecutive. The player who can't make a move loses. The first player always picks a valid move uniformly at random, and you are playing for the second player. Can you win at least 499 games out of 500?
The most straightforward dynamic programming would compute for each l<=t<=r the probability that the t-th player wins in a tournament where the players from l-th to r-th participate. This dynamic programming would have O(n3) states though, and each transition would require iterating over the last non-winning player remaining, and the splitting point between the two segments that they beat, resulting in a complexity in the ballpark of O(n5) which is too much.
The first observation is to notice that we have two basically independent tournaments happening to the left and to the right of the winning player, so we can compute the probabilities that the t-th player wins in the [l;t] and in [t;r] segments and multiply them. Therefore we can afford to have a quadratic number of states: the probabilities that the first and the last player wins in each segment, and the running time of the entire solution becomes O(n4).
In order to get a further speedup, we need to become a bit more explicit with the formulas. If we denote the probability that the l-th player wins in the segment [l;r] as pl,r, the probability that the r-th player wins in that segment as ql,r, and the probability that the i-th player beats the j-th player in a direct encounter as wi,j, then our current solution can be viewed as:
pl,r=sumx(sumy(1/(r-l)*pl,x*qx+1,y*py,r*wl,y))
Where y denotes the player we beat the last, and x denotes the right boundary of the segment of players that we beat directly or indirectly before beating y. Note that the value of x does not actually depend on the outcomes of the games, just on which game is the last one: if we imagine that initially we have n players and n-1 "potential games" placed between them, then at every turn we take one potential game and remove it, so the order of games is just a permutation of n-1 elements, and the value of x is the last element of that permutation, so each possible value has the same probability of 1/(n-1), which transforms to 1/(r-l) in our formula.
There are two magical things about this result:
- The fact that after we condition on a given x, the games happening in [l;x] and [x+1;r] segments are independent and random in the same sense as in the original problem, so that dynamic programming can work at all.
- The fact that the probability for any x is just 1/(r-l) and crucially does not depend on x enables the most exciting magic of this problem to happen, because we can now reorder our summation as
And notice that the inner sum on x does not depend on r, and can be computed as an additional dynamic programming table ul,y and reused between different values of r, thus reducing the overall running time to O(n3). Had the probability depended on x, we would not be able to collapse the inner summation, and the problem would be much less interesting.
The official editorial does not mention this magical property at all, so I'm wondering if there's a less magical implied explanation there :)
Without loss of generality, let's assume that f(0) is positive, so our goal is to make the sum negative.
First, we can notice that the masks simply mean that we have 62 subsets of our objects, we're allowed to flip the sign of values in any of those subsets, and each object belongs to at least one subset.
Had the subsets been disjoint, the solution would have been easy: we could just flip the sign of all subsets which have a positive sum. Then all subsets would have a zero or negative sum, and we would have at least one negative subset since the total sum is not zero.
It turns out that our problem is almost as easy: let's fix an arbitrary order in which we will traverse the subsets, and say that each object truly belongs only to the last subset that contains it, in that order. Then we can go through the subsets in that order, and flip all subsets which have a positive sum of values of objects that truly belong to it. Note that the values we are summing here could have their signs flipped by the previous subsets that those elements belonged but not truly belonged to.
Since the object is never touched after we process the subset it truly belongs to, the total sum of values in the end is equal to the sum of sums of values of truly belonging objects for each subset as we process it, and all those sums are zero or negative by construction, and at least one of them is negative, so the overall sum is negative as needed.
The naive min-cost-max-flow network would look as follows: edges from the source to each red group with capacity equal to the size of the group and cost 0, edges from each red group to each blue group with infinite capacity and cost equal to negative Manhattan distance between the points, and edges from each blue group to the sink with capacity equal to the size of the group and cost 0.
The negative Manhattan distance has the following form: -abs(x1-x2)-abs(y1-y2). Suppose we know how each absolute value expands (the signs of its argument), for example: -(x1-x2)+(y1-y2). This can be reformulated as (y1-x1)+(x2-y2). Let's insert a vertex in the middle of this edge, and split its cost into two: the edge from the red group to this vertex has cost (y1-x1), and the edge from this vertex to the blue group has cost (x2-y2).
So far we did not change much, but here comes the key idea: we have only four types of those intermediate vertices, corresponding to the four ways the absolute values can be expanded, and for all intermediate vertices of the same type the costs of the edges going into them from a fixed red group are the same (since the value (y1-x1) does not depend on the blue group), and the costs of the edges from them to a fixed blue group are the same. Therefore the natural next step is to collapse all intermediate vertices of the same type into one, and any valid flow in the old network naturally corresponds to a valid flow in the new network with the same cost.
The new network has more valid flows, though: now it is possible for the flow to go from a red group to a blue group through a "wrong" type of intermediate vertex. However, such way has a higher cost than going through the correct type of intermediate vertex (since expanding the absolute value in the wrong way results in a lower value), and therefore will never appear in a minimum cost flow, so the value of the min-cost-max-flow in the new network is the same, and the new network has linear size!
Thanks for reading, and check back for more.
A Kotlin week
The hard problem in this round required a few nice observations to make the dynamic programming fast enough. 500 table tennis players are sitting in a row. Repeatedly, we do the following: pick two adjacent players uniformly at random, play a game between them, and eliminate the player who lost, until there is only one player left. Each player has a rating ri, and the probability that the i-th player wins against the j-th player is ri/(ri+rj). What is the probability that the given player wins the entire tournament?
Problem F in this round was very easy for me, but quite difficult and with a lot of system test failures overall: you have 300000 objects, with each object having two attributes: a value between -109 and 109, and a nonzero mask with at most 62 bits. Given another mask s, we compute f(s) as the sum of values of objects which have an even number of shared bits between their mask and s minus the sum of values of objects which have an odd number of shared bits between their mask and s. f(0), which is just the sum of all values, is not equal to zero. Your goal is to find any s such that f(0)*f(s) is negative, in other words to flip the sign of the sum. Can you see how to do it?
Here's what the problem was about: you are given at most 1000 groups of red balls, and at most 1000 groups of blue balls. Each group contains at most 10 balls in the same location, and the coordinates of those locations are integers not exceeding 109 by absolute value. The total number of red balls is equal to the total number of blue balls. Consider all possible matchings where each red ball is matched with one blue ball and vice versa. You need to find the maximum sum of Manhattan distances between the matched balls. Can you see how to make the network linear?
The most straightforward dynamic programming solution would just remember the set of already visited cells and the position of the token, but there are too many possible combinations. The first optimization we can make is to avoid storing the position of the token, instead rotating the set so that the token is always in a fixed position.
This does not make the solution fast enough, so we need another key optimization idea: notice that we can never jump over two consecutive visited cells, so if we find the closest such pair to the left and to the right of the token, everything outside those does not really matter, and we can assume that all outside cells are visited as well, for example replacing the state 0101110T001011010 with 1111110T001011111.
Now the number of reachable states is actually polynomial, since outside the all-one part we will always have a prefix/suffix of alternating 0s and 1s, and maybe some 0s in between those. We could try to encode them effectively using that observation, but we don't actually need to: we can still represent them as bitmasks, and just rely on the fact that the number of reachable bitmasks will be small. Since the largest testcase is obvious, we can run our solution on it to make sure it's fast enough before submitting it. And even if it weren't, we could precalculate the answers.
Thanks for reading, and check back for more!
A past glory week
Problem J required a nice but not very difficult observation. You have n (n<=50) cells arranged in a circle and a token in one of the cells. Then you repeatedly do the following: pick a number uniformly at random from the set {-2,-1,+1,+2}, and move the token this many cells along the circle (positive numbers corresponding to the clockwise movement, and negative to the counter-clockwise one). What is the expected number of moves before the token visits the same cell twice? The cells that are passed through in the middle of a -2/+2 move do not count as being visited.
Thanks for reading, and check back for more!
Subscribe to:
Posts (Atom)