Here is my submission:
http://codeforces.me/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).
Are you sure, that index is between 0 and n-1?
Could it be because of overflows? I googled and found here that long has the same maximum value as int.
You used condition n(n + 1) < 2k in your solution where n is only a "long", which might cause an overflow when k is something like 2e9 where n(n + 1) can be up to almost 4e9.
Thanks, that was indeed the case! I had no idea that the maximum value of int is the same as long. Switching to long long fixed the issue.
You're welcome! This is my new knowledge too; I've always thought long long > long > int, so thanks to you also. :)
I have always known that the sizes of the primitive data types vary for the different architectures, but assumed that the difference is not noticeable for newer machines. However, it turned out that my computer uses 8 bytes to represent a long, whereas the judge uses 4 bytes for longs, meaning that they have the same size as int.
If you are interested in the size of some of the data types, here is an experiment I did:
http://codeforces.me/contest/670/submission/17760098