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...
Update: I did not get the E2 hack, but I did get a B hack...
LOL :)
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:
(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 for2<=k<=5wheren^(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
kfor which(1-k^7)/(1-k) < 10^18is999. So your for-loop does around10^3operations give or take. And there are10^4test cases total. So there's no way you get a TLE from that either with only~10^7total. On my machine it ran in around 500ms.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!
I did the same thing but for r<=10