Friday, January 3, 2020

A mobile-first week

Last week has wrapped up the competitive 2019 with two rounds. AtCoder Grand Contest 041 took place on Saturday (problems, results, top 5 on the left, analysis). mnbvmar, ecnerwal and Um_nik in first three places all have a different set of problems solved, and mnbvmar's set was the best one. He also tried to submit a solution that just tries random decisions until time runs out for E in the last minute, but that did not fly. Nevertheless, congratulations on the win!

I was writing this round on the go, and around the middle of the round my laptop shut down because of low battery, which was very exciting as you might guess :) After I've turned it back on it continued to work for a long time somehow, suggesting that the problem lies with the battery level detection. A few minutes before the end of the round it shut down again, so I've tried to fix my solution to problem A from my phone. Unfortunately I was a few seconds too slow, otherwise it would have been a nice achievement :)

Problem D in this round had an awesome intended solution, even though most contestants managed to squeeze in a more boring one: an assignment of integer scores between 1 and n (not necessarily distinct) to n programming contest problems (n<=5000) is called good if for each k the total score of every set of k problems is strictly less than the total score of every set of k+1 problems. How many good assignments of scores exist, modulo the given prime m?

This round has concluded the selection of 8 AtCoder World Tour finalists that would come to Japan in February for the onsite finals (results, top 8 on the right). With this win, mnbvmar has jumped onto a departing train (there is such idiom in Russian, вскочить на подножку уходящего поезда, but I'm not sure if there is a direct English equivalent or a different idiom with the same meaning — is there?) and overtook eatmore by just 6 points. See you all in Japan!

Codeforces Good Bye 2019 followed on Sunday (problems, results, top 5 on the left, my screencast, analysis). Not without help from a notorious coincidence and a bad day for tourist, Radewoosh has solved everything, won the round, ended the 2019 top rated, and was still a bit salty. Still, congratulations!

Problem G generated some conflicting opinions, but I have enjoyed solving it quite a bit: you are given n integers ai such that i-n<=ai<=i-1 (i goes from 1 to n), in other words one integer from [-(n-1),0], one from [-(n-2),1], ..., one from [0,n-1]. You need to find any nonempty subset with a zero sum. You are guaranteed that such subset always exists, which is by itself quite a hint. n is up to a million.

Thanks for reading, and see you in the present!

No comments:

Post a Comment