cgy4ever's blog

Topcoder SRM 710
By cgy4ever, history, 8 years ago, In English

Topcoder SRM 710

Time: 9:00 pm EST Thursday, March 9, 2017

Calendar: https://www.topcoder.com/community/events/

  • Vote: I like it
  • +59
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

This round will start in 22 hours!

→ Reply
»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Will start in 1 hour.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

oh my god! I am feeling so Stupid! euheuheuh I have no idea about div1 A topcoder! Can anyone explain the DIV1 A solution?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too.but the contest does not end

    → Reply
»
8 years ago, # |
  Vote: I like it +132 Vote: I do not like it

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.

Div2
Div1
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Nice problems, thank you!

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +80 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      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.

      code
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 6   Vote: I like it +5 Vote: I do not like it

        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).

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        :) thank you for the problems anyway. This problem really made me feel the 'Misere' part of game theory :)

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +30 Vote: I do not like it

          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 :(

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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...

            → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I don't want to participate in div1 at all but topcoder pushed me too fast, I do not belong there :(

→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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 ... :(

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    I tried to make that clear with the first two samples. But, I'm not sure how many people read the samples carefully.

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Did anyone try div2 600 using dfs with each vector state as a node ?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Challenges to write editorials are up, though I didn't note when exactly they appeared.

    → Reply