macaquedev's blog

I think some people are hacking the CF algorithm
By macaquedev, history, 3 weeks ago, In English

See this... How the hell does creating a 1e5 ish sized array 1e4 times pass?? I think he's probably hacked Codeforces or something...

  • Vote: I like it
  • -45
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I think its fine. That is within the allowed number of iterations if you consider total tests.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    1e9 should not pass in 2 seconds

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

      Maximum number of iterations is ~63245 because $$$(N+1)*N/2<MAX$$$ .

      So in total it will be $$$6*(1e8)$$$ which is fine.

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

      Even if was a pure 1e9, it still depends on other constants. There are huge differences between performing 1e9 additions and 1e9 prints, and the former even fits in like 0.5s, whilte the latter can't run even in 10s. Pushing to a vector is a little more heavier, but 6e8 still barely fits in 2s.

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it's not 1e9 iterations as it's increasing each time like this 1 3 6 10 15 21 27 so it's not 1e9 so it passed

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For every test case a new array of at max 1e4 will be created. Which is anyways fine. What is the problem here?

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

    because there are 1e4 testcases, and push_back is slow...

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

Eliminated.

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

    How did you do it? Can you tell me what testcase you used? I did the maximal one (1 1000000000, repeated 10000 times) and that did not TLE...

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

      It's about luck. You just need to spam hacks with slightly different values every time. Execution time is unstable enough to make 100~200 ms differences with many many tries, while different test cases make barely any effect on it on average (as long as you keep $$$t=10^4$$$).

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

        But surely you can't spam these hacks in a div2 where you get -50 every time you fail?

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

          Yes, it will most likely survive if it were a Div. 2.

          → Reply