toss's blog

By toss, history, 9 years ago, In English

Here is my submission:

http://codeforces.net/contest/670/submission/17734251

I get a RUNTIME_ERROR for the 13th test case and I have no idea why. I cannot debug it, since the input is truncated. I tried to reproduce a test case with similar n and k, but random id's and it is working fine, or at least it doesn't cause a runtime error.

I hope that such questions are appropriate for the blog and I would very much appreciate your help. I would also be very happy if you could give me some general tips on how to approach such problems (figuring out why a truncated input caused a runtime error).

Full text and comments »

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

By toss, history, 9 years ago, In English

Today I completed my second competition (#333) and an important question regarding time limits arose. I solved the B problem in O(n) time and after locking the problem, I saw that a participant in my room solved it in O(n^2) time. Consequently, I wanted to hack his solution based on the given time limit, but I wasn't sure if my challenge would succeed.

So my question is how do you generally estimate if your/someone else's solution would fit the time constraint? I am aware that constants get dropped in big-O, but I am looking for some general rules. For this example, the aforementioned user would perform at least n*(n+1)/2 operations in worst case with n being at most 100 000 and time limit of 2 seconds. Was it reasonable to attempt to hack his solution and what is your approach with regard to the time limit?

Full text and comments »

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

By toss, history, 9 years ago, In English

Today was my first competition(#326) and I was surprised, because my solution for the Div2 C problem was asymptotically optimal [O(N+M) where N is the number of weights and M is the maximum weight], but it was not accepted, because it failed the 11th test case because of being too slow.

After the competition, I examined the successful solutions of other participants and I was surprised to see that they have the exact same strategy. How is this possible?

Full text and comments »

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