chrome's blog

Topcoder Single Round Match 641
By chrome, 9 years ago, translation, In English

Hi!

Today, at 19:00 MSK will be held Topcoder SRM 641.

Let's discuss problems after contest!

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

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

double post

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

This amazing moment when you see a solution below and realize that you have no idea how to generate a vector of 2.5k elements at TopCoder Arena T_T

solution

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

    The same here :D
    I used GeoGebra trying to generate a pattern that never lead to collinear but failed on that.
    at a moment I thought that no test case will contains 2.5k input and brute force will pass I'm curious to know such big test cases.

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

    I have actually managed to squeeze N^3 solution under time limit: http://pastebin.com/e6NDEj0q

    but couldn't get all the bit juggling right during the contest time :)

    And when you look at simplicity of Petr's solution after such efforts, it's jaw-dropping :)

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

Any ideas on div1 hard?

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

    I had an idea that is based on writing down the basic equations and then noticing that, for instance, the part that depends on the cursor can be isolated since everything is additive:

    So, $f(m,i)=f(m)+d_i$, where

    So $f(m)$ seems to only depend on the number of set bits in m, and can be calculated via Gauss elimination. BUT that is not quite true, because if m = 0 or m = 2n - 1, then f(m, i) = 0 and we have to adjust for that. There is probably a way to derive the adjustment (it can be separated since everything is additive) from the mask, but I couldn't find it. There is also the possibility that I went completely the wrong way about it. There are some solutions in practice room but I didn't read them thoroughly and don't know if they're correct or not.

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

      Indeed, f(m) only depends on the number of bits set in m. The trick to deal with the bits = 0 or bits = n cases is to overcount, then remove what you overcounted.

      That is, for every combination of toggles that ends in position i, you will overcount the number of moves by di. So if we know, based on the starting position, what is the probability that the last bit toggled is i (let this probability be pi), then we can calculate f(m, i) normally and subtract at the end.

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

        Ah, that makes sense. And that probability can be calculated by noticing that the only thing that matters is whether the bit i is set, and how many other bits are set, so we can reduce the number of states to 2·n and use Gauss elimination again.

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

Is there a problem in Arena I can't login

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

tourist has the highest rating on topcoder too after this srm .

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +24 Vote: I do not like it

Here's my analysis of this round: http://www.rivsoft.net/blog/srm-641/

→ Reply