Hi everyone! Codeforces Month Of Blog Posts Pt. II has ended at 15th of November. Sorry for the delay of the results!
Overall, we (together with orz and artew) raffled $800! I've chosen 6 blogs to be named winners, and here they are: TeaTime, Iura_Shch, asdasdqwer, CelioPassos, catalystgma win $150 each and cadmiumky wins $50, congrats!
Here are the links and brief reviews of each winner blogs!
- TeaTime – Counting Perfect Matchings – won 150 usd! – interesting read, loved it! The described algorithm lets you count the number of perfect matchings in a bipartite planar graph in $$$O(n^3)$$$. Proofs are understandable, the blog is of high quality, not sure about the applications though :D
- Iura_Shch — Online 3D Mo's algorithm – won 150 usd! – interesting idea! Briefly, to answer subrange queries you split the $$$N*N$$$ grid into $$$C * C$$$ blocks, so you can update your struct in $$$O(C^2)$$$ and answer the queries in $$$O(\frac{N}{C})$$$. By choosing $$$C$$$ equal to $$$cbrt(N)$$$ you can get the something like $$$O(N^{5/3})$$$. Basically, the asymtotics is the same as in regular 3D Mo's algo, but now it supports online queries! (but uses additional memory :])
- asdasdqwer – Rotating Calipers and It's Applications (both parts) – won $150! – a blog about the rotating calipers technique with a lot of nice pictures and explanations. Also, a lot of applications – it turned out I didn't know most of them!
- catalystgma – Exponential Length Substrings in Pattern Matching – won $150! – a nice blog with an interesting idea and A TON of proofs :)
- CelioPassos – Snapshot of finite calculus and using it to solve a 3000 rated problem & The discrete derivative, falling factorials and polynomials – won 150 usd! – it is a nice introduction to the finite calculus! I loved the first blog, my inner mathematician is happy. As for the second blog, I was able to read only the first half of it, so can't really tell it's quality haha
- cadmiumky – Heigh-wise Small-to-large trick – won 50 usd! – classical/basic idea, but still a nice blog, make sure to read it if you don't know the trick!
Sorry for those who wasn't able to win this time! Make sure to check out every blog in the comment section of the announcement!
Thanks everyone for taking part in the challenge! Hope you liked it :D
Thanks for the prize!
Were there any blogs that were submitted, but weren't posted neither here nor in the comment section of the announcement?
There were some recent blogs submitted by Arpa, ghoudiy, Kurta_Sofia to name some. You may check out their blogs in their profiles, I guess :D
Congratulations to these winners, as well as other participants! And I am just curious. Does winning an award have anything to do with the difficulty of the blog? Seems most of them are advanced algorithms. Thanks.
One of the reasons I can name is that most of the easy blogs on codeforces are already written :D
To be honest, the blog by valeriu is actually not hard, have a look at it! Also, rotating calipers and online 3D Mo blogs are also relatively easy.