A 400-500 week

Let's take a quick break from the World Finals practice session and take a look at last week's events. Codeforces Round 352 on Wednesday was one of the last chances to practice before this week's event (problems, results, top 5 on the left, analysis). Quite fittingly, three out of top five spots were taken by the World Finals competitors, including yet another first place for subscriber – he is on fire!

TopCoder Open 2016 Round 2A took place a day later (problems, results, top 5 on the left, my screencast). The point values of 400, 500 and 1000 (instead of the usual 250, 500, 1000) gave a hint that this will not be a usual round, and it did go strangely indeed (self-inducing prophecy?..) The 1000 was probably the most "typical" problem of the round, so going for it after the 400 has paid off for me. I've also managed to get the 500 submitted and even accepted, but there actually exists a test that makes my solution time out. Can you come up with one? Here's the solution (requires TopCoder login). Bonus points if your test makes it time out even after shuffling the vertices – I don't know how to do that :)

Here's the problem statement of the hard problem that saved my day: you have 40000 tokens which you can spend using 15 vending machines. Each machine takes tokens, and sometimes gives a prize in response (but sometimes not). The probability of getting a prize after inserting K tokens and not getting a prize on the first K-1 attempts is min(1, K²/L_i²), where L_i is a constant, different for different vending machines. After you get a prize from a machine, its state resets to the initial one (so K in the above formula becomes the number of tokens inserted after that). Your strategy must be to pick some vending machine, keep inserting tokens to it until you get a prize, then pick some different vending machine, give tokens until a prize there, then pick some different vending machine again (this one might be the same as some previous machine used, but not as the vending machine used to get the last prize), and so on until you run out of tokens. The prizes from i-th vending machines have value V_i. How to maximize the total expected value of all prizes you get?

Thanks for reading, and keep checking my twitter for ICPC 2016 updates!