Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### cgy4ever's blog

By cgy4ever, history, 7 years ago,

Topcoder SRM 710

• +59

| Write comment?
 » 7 years ago, # |   +47 This round will start in 22 hours!
 » 7 years ago, # |   +29 Will start in 1 hour.
 » 7 years ago, # | ← Rev. 3 →   +27 oh my god! I am feeling so Stupid! euheuheuh I have no idea about div1 A topcoder! Can anyone explain the DIV1 A solution?
•  » » 7 years ago, # ^ |   +23 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.
•  » » 7 years ago, # ^ |   0 me too.but the contest does not end
•  » » 7 years ago, # ^ |   +31 Nice problems, thank you!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +80 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).
•  » » » 7 years ago, # ^ |   +38 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. codeint xxor = 0; int mx = 0, mx_misere = 0; for(auto i:arr){ xxor ^= i; mx = max(mx, i); mx_misere = max(mx_misere, i >> 1); } if(xxor == 0 || mx == 1) return "Alice"; else{ int xor1 = xxor >> 1; int low = xxor & 1; // misere nim subgame result is lose for current player // reason: some pile with more than one stone // xor of all numbers is 0 if(mx_misere >= 2 && xor1 == 0){ if(low == 1)return "Bob"; else return "Alice"; } // misere nim subgame result is lose for current player // reason: no pile with more than one stone // number of piles odd if(mx_misere <= 1 && xor1 == 1){ if(low == 1)return "Alice"; else return "Bob"; } // misere nim subgame result is win for current player return "Alice"; }
•  » » » » 7 years ago, # ^ | ← Rev. 6 →   +5 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).
•  » » » 7 years ago, # ^ |   +13 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.
•  » » » » 7 years ago, # ^ |   +28 :) thank you for the problems anyway. This problem really made me feel the 'Misere' part of game theory :)
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +5 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.
•  » » » » 7 years ago, # ^ |   +16 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 :)
•  » » » » » 7 years ago, # ^ |   +30 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 :(
•  » » » » » » 7 years ago, # ^ |   +3 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...
•  » » » » » 7 years ago, # ^ | ← Rev. 3 →   0 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?
•  » » 7 years ago, # ^ |   +10 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.
•  » » » 7 years ago, # ^ |   +10 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.
 » 7 years ago, # |   +11 I don't want to participate in div1 at all but topcoder pushed me too fast, I do not belong there :(
 » 7 years ago, # |   +15 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 ... :(
•  » » 7 years ago, # ^ |   +25 I tried to make that clear with the first two samples. But, I'm not sure how many people read the samples carefully.
 » 7 years ago, # |   +5 Did anyone try div2 600 using dfs with each vector state as a node ?
 » 7 years ago, # | ← Rev. 2 →   0 .
•  » » 7 years ago, # ^ |   0 Challenges to write editorials are up, though I didn't note when exactly they appeared.