Блог пользователя cgy4ever

Автор cgy4ever, история, 9 месяцев назад, По-английски,
 
 
 
 
  • Проголосовать: нравится  
  • +59
  • Проголосовать: не нравится  

»
9 месяцев назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

This round will start in 22 hours!

»
9 месяцев назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Will start in 1 hour.

»
9 месяцев назад, # |
  Проголосовать: нравится -95 Проголосовать: не нравится

We need CF round :(

»
9 месяцев назад, # |
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?

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    me too.but the contest does not end

»
9 месяцев назад, # |
  Проголосовать: нравится +132 Проголосовать: не нравится

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
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    Nice problems, thank you!

  • »
    »
    9 месяцев назад, # ^ |
    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).

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится +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.

      code
      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        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).

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
      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.

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится +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 :)

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
            Проголосовать: нравится +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 :(

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится +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...

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
          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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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.

»
9 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
9 месяцев назад, # |
  Проголосовать: нравится +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 ... :(

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

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

»
9 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      yes challenge is now up and that is why I just edited my comment but still they mentioned it like this "just after the srm" challenge will be open.