The recording of my computer screen during Google Code Jam 2017 Round 1A.
My solution for C-large runs in ceil(A_k/D), which can be up to 10^9 if D=1. It turns out that it is fast enough for one case, but could not run below 8 minutes for 100 testcases (as you can see in my screencast, it is an interesting race between 8 minutes countdown and my program). I downloaded several correct C-large solutions and they also run as slow as mine, but they parallelized the testcases.
TIL : I should add multithreading libraries into my Codejam template.
NB! I'm not accusing anyone of any behaviour (even if someone is actually doing this, in which case I'm genuinely interested -- how much does it cost?) with this comment, just discussing a hypothetical scenario.
The multithreading seems like a fair game to me, the more interesting question is this: am I allowed to buy 100 VMs in Amazon Cloud, split the input file, send 1 case to each VM and then merge the answers together (and ship them along with the code that actually communicates with VMs)? This feels like it shouldn't really be allowed, but I cannot find anything in Terms prohibiting it. The Terms mention that your code has to give the same output as you submitted, but don't mention anything about the time/resources it has to do so in.
I presume you are allowed, because who is to say that your personal computer doesn't have 128 cores or whatnot. I suppose the effect can not be this large on the contest, because once you get to finals you have to use provided computer.
I never thought that multithreading was allowed -- turns out it's only banned in the Distributed rounds.