amlelephant_fan's blog

Looking for Hack on Round 883 E2
By amlelephant_fan, history, 17 months ago, In English

Hi, during today's Div.3 contest, I solved E2 by using the similar approach to E1, checking all the k from 2 to 3000 such that 1+k+k^2+...+k^r==n, and only adding some special O(1) checks for cases when r = 2, 3, 4, 5. I think the solutions is probably not correct but I could not find a hack for it. I am looking for a hack that can make the code WA or TLE. The submission is the following: 212679414. Any help would be appreciated, thanks in advance!

Update: I did not get the E2 hack, but I did get a B hack...

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

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Update: I did not get the E2 hack, but I did get a B hack...

LOL :)

→ Reply
»
17 months ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

I think your solution is correct. TLE is impossible, since you are doing 3000 iterations of an O(log n) code block. WA is also impossible:

  • If the top power is more than 5, then it will be captured by the last for-loop. This is because (10^18)^(1/6) = 10^3 = 1000, which is less than 3000, your upper limit.
  • If the top power is less than or equal to 5, then it will be captured by the first four for-loops. This is because the inequality (1-(n^(1/k)-5)^(k+1))/(1-(n^(1/k)-5))<n<(1-(n^(1/k)+5)^(k+1))/(1-(n^(1/k)+5)) has no solution for 2<=k<=5 where n^(1/k) is above 3000. ( I checked with wolfram alpha )

So, unless I've made a mistake in my reasoning, there should be no hacks for you :)

Update: I forgot that t<=10^4, so maybe TLE could be possible — I'll look more into it.

Update2: The first k for which (1-k^7)/(1-k) < 10^18 is 999. So your for-loop does around 10^3 operations give or take. And there are 10^4 test cases total. So there's no way you get a TLE from that either with only ~10^7 total. On my machine it ran in around 500ms.

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

    Thank you very much for your explanation! In the end, no hacks happened to me on E2. The reason I was asking for hacks was that I thought the solution I did was very cheesy should not get AC. But anyways thanks for checking my code and doing the math for it!

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did the same thing but for r<=10

→ Reply