Topcoder SRM 710
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Topcoder SRM 710
Name |
---|
This round will start in 22 hours!
Will start in 1 hour.
oh my god! I am feeling so Stupid! euheuheuh I have no idea about div1 A topcoder! Can anyone explain the DIV1 A solution?
Type-B is reverse of type-A. Do type-A for two sequences to get the same sequence. Example: the first slot get all stones.
me too.but the contest does not end
I was the author for this round. I hope you enjoyed the problems! Here are some short hints to the problems along with the code.
What if there were no magic stones?
What should we do if we take the magic stone?
Take the max of the two cases above.
Choose an arbitrary pile as the "final" pile. What are some strategies to get all the stones in that pile?
Do we have enough moves?
Let's choose pile 0 as our "final" pile. Then, while there exists a non-empty pile that is not pile 0, do a move on that pile. This is guaranteed to terminate in at most (num stones) * (num piles) steps.
There are two different approaches.
Add the edges in increasing cost.
Fix the largest weight node that we will use. Then, we can do something like Kruskal.
How long does it take to update a single edge? Maybe try amortized analysis also?
Add the nodes in increasing cost.
This kind of looks like Floyd Warshall.
Let's change the order that we add nodes in with Floyd Warshall.
The two operations are inverses of each other.
We can bring both of them to any common state.
Read the problem statement for div2 med. Try to get all the stones into one pile.
What are some obvious winning or losing states?
All piles have 1 stone. Alice can always win by taking the magic stone then deciding based on parity of remaining stones.
XOR of all stones is equal to zero. Alice can take the magic stone and leave the victory condition alone.
Otherwise, if the xor is nonzero and there exists a pile with at least 2 stones, then it is not optimal to take the magic stone. Since winning conditions of misere and normal nim are the same when there exists a pile with at least 2 stones, you are passing a winning state to the other player by taking the magic stone.
After checking those two cases, we can ignore the lowest bits of all the numbers, as well as the magic stone.
This then becomes a game where a[i] is replaced by a[i]>>1, and the last player who takes a stone loses. This is misere nim.
Solve the problem when k = 1.
Solve a more general version of the problem when k=1, but we also want certain pairs of hyperboxes to be intersecting (described by a bit-mask with (m choose 2) bits). To restate, for every 2^(m choose 2) choices of bitmasks, compute the number of ways to solve this problem in 1 dimension.
Two hyperboxes intersect if and only they intersect in every single dimension. Thus, they are disjoint if we take the bitwise and of all intersections of each dimension and it equals zero. This can be done efficiently with a Fast Walsh Hadamard transform.
Nice problems, thank you!
I still don't understand one thing in MagicNim problem solution. Why can we use nim modification with a[i] >> 1? In this case, for example, test with signle pile with 2 stones must have the same answer as test with single pile with 3 stones, but I think it's not true (single pile with 2 stones is loosing, while single pile with 3 stones is winning as we can remove one stone from it and reduce the problem to a pile with 2 stones).
I had a hard time understanding the solution too, and in my opinion the setter hints and solution above lack one specific detail, the last bit of numbers can't simply be 'ignored'. Although the official (and neat) java code is correct :). Hope the following code explains a bit more.
In your code: "if (mx_misere >= 2 && xor1 == 0)"
why does Bob wins only when low == 1?
I think Bob always wins in this case(regardless of the value of low) because the only hope for Alice to win is to keep xor1 value equal to zero using an odd number and decreasing it by one, but if she does that the original xor value becomes zero and Bob uses the magic stone and wins.
UPD: Actually the expression(xor1 == 0 && low == 0) will never be true so there is no problem code-wise(it will get AC).
Yes, sorry, I missed one step. In particular, if the misere nim is a losing case for the current player, the current player can only win if there are an odd number of piles with an odd number of stones. They can win by taking a single stone from some pile with an odd number of moves (i.e. a "pass" move). Only the parity of the number of pass moves matters, since our opponent can copy our passes.
:) thank you for the problems anyway. This problem really made me feel the 'Misere' part of game theory :)
Can someone explain how that playing a misere nim game after dividing pile sizes by 2 came up in MagicNim problem? Sorry didn't understood that.
We know that in MagicNim, two positions are for sure winning:
1- all piles with less than two elements: we take the magic stone, and choose the nim if the number of remaining piles is even, otherwise choose misere nim.
2- the xor of all numbers is 0: we take the magic stone and choose to play normal nim.
Moreover, in any other case you cannot take the magic stone, as in both cases, nim or misere nim, you would leave the adversary in a winning position.
Then we can somehow try to simplify the game, and get rid of the magic stone. The first player that after his move leaves the game in one of the two positions above loses (and that's the only way one can lose), so we can define a new game, where there is no magic stone, and the losing positions are the two above. In that new game, we can forget about the last bit in each number, the only thing we need to remember about those bits is the parity. So our new game is a misere nim + (odd-even game with the last bit). And then you get the messy analysis above :)
Why we can ignore last bit in each number? I can't understand it(There could be an even->odd move). Anyway, Nim game probs are too hard :(
I couldn't understand it either, maybe someone has to make some graphics, at least I cant :(.
To answer your question, the last bit can't be ignored. Imagine we are playing the game where losing positions are those whose xor is 0, or all piles have at most 1 stone, and there is no magic stone (the original game reduces to this one, the last one to move loses, so this is by itself misere).
Now the trick for the solution is that in these new game we can define 8 states, following this: each time:
there will be some piles with more than one elements, lets say those piles are represented as its half in the misere nim subgame (observe here we are ignoring the last bit), in this subgame we have at most 4 states (as in misere nim), and every time we make a move we can change the parity of the last bits.
also there are some piles with one stone: we represent all the last bits on all numbers as one, its xor or parity, whatever, so in this subgame we have two states.
in general we have 8 states.
now the possible moves are: take a stone from a pile with one stone: this corresponds to changing the parity of the last bit. take some stones from another pile, this corresponds to a move in the misere subgame, and can always change the parity of the last bit.
The trick and surprise and solution is that with those 8 states is enough for defining winning and losing positions for the whole game, and that can be proven by analyzing all cases, and all possible transitions...
and I can say a lot of problems are too hard :( but wouldn't choose nim games between them :) although this one more than being hard is messy, mostly to explain...
Still can't understand why after dividing all number by 2 it becomes a misere nim. I mean the losing state becomes the xor sum of all number is 0 or all number is less than 2. Why we can still use the same way solving the misere nim to solve this by just forgetting about the last bit?
Talking about hard problem: The last part could be also easily done with Inclusion–exclusion principle. The hardest part is k = 1. What is your asymptotic? Could you please clarify it? I wrote this part also in a different way: I generate number of way to put segments with compressed coordinates. After that, if I know that there are 100 ways of putting segments (6 segments) onto 11 points with some intersection_mask, then I just add to dp[intersection_mask] += 100 * C(n, 11).
I didn't like medium problem: I guess it could only be solved (and very fast, i got ac after writing stupid solution with this approach in a couple of minutes) by looking at a table of numbers.
Easy is a cool problem. But I made a bug, so without a small pretest I spent a lot of time trying to find the mistake in the code.
I can give you some loose bounds; there may be better ways to make it tighter. You can also add counters to code to see exact number of operations.
I fix the order that the intervals open. Since the intervals can be represented by balanced parenthesis, a very loose bound is catalan(6) * 6! * 2^12 ~ 10^7. More specifically, catalan(6) comes from number of ways to form a balanced parenthesis sequence, 6! comes from number of ways to close parenthesis, and 2^12 comes from number of ways to split the elements into groups where they take the same value. In practice, this is smaller, since I don't expand impossible states.
Afterwards, I can do a post-processing step where I can permute the labels. This step takes 2^(m choose 2) * m! * m^2, but actually, if I prune out zero entries (i.e. masks with zero ways), it's actually 2^(m choose 2) + (m!)^2 * m^2. I'm not sure why there are exactly m! nonzero masks before permuting labels.
This approach takes 0.5s for everything for my solution in Java.
I don't want to participate in div1 at all but topcoder pushed me too fast, I do not belong there :(
How silly is it to not be able to see that the two operations in Div1 300 are inverses of each other? In retrospect these things always seem so obvious ... :(
I tried to make that clear with the first two samples. But, I'm not sure how many people read the samples carefully.
Did anyone try div2 600 using dfs with each vector state as a node ?
.
Challenges to write editorials are up, though I didn't note when exactly they appeared.