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

moaforlife's blog

Solutions failing hacks even with some non-optimal logic
By moaforlife, history, 8 months ago, In English

I was trying to hack some solution for problem D of yesterday's contest. Now, as far as I know, the solution which are running loop on all the primes should be failed in hacks, as the time complexity is around O(# of primes)*O(n). This is around $$$7.8*10^8$$$. And all these solutions are running in 2 seconds if they have used some thing like fast input output.

I think that the bounds in the problems should have been tighter for this to not happen... What do you guys think about this?

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

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

The intended solution should be $$$O(n \sqrt A)$$$ which is clearly larger than what you suggest. $$$O(n \log A)$$$ is possible with preprocessing using a sieve but of course then it would be harder than regular Div3D.

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

    Yeah! I totally agree with you with the $$$O(n \sqrt{A})$$$ solution.

    But I was saying about other solutions... The ones which calculate the primes till $$$10^6$$$ and then for every $$$a[i]$$$, run loop on every prime till $$$10^6$$$ and divide $$$a[i]$$$ with it...

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

      Well, that kinda sucks. But a larger bound on $$$A$$$ should make the $$$O(n\sqrt{A})$$$ TLE also. Anyways, the solution you described is $$$O(n \frac{A}{\log A})$$$, so we can't just blame the bounds.

      → Reply