One and a half months ago I proposed a challenge to every one of you to get something from your drafts or from your head and actually write a blog post about it. I got a bunch of submissions, and you can find the links to all of them throughout this blog post (I was actually surprised that all entries were meaningful and interesting, so I definitely recommend checking them out). If you submitted an entry and I didn't mention it here, it is not purposeful! Indicate it via a direct message and I will include it here. It was just a bit hard to keep track of all submissions.
I went through all the submissions. Some of them were very complicated, and I tried my best to get the overall idea but I will need to come back to dive deeper into some technical proofs. However, I believe that these technicalities that I glanced through do not affect my decisions. We are ready to present the winners!
Regarding the first place, there was no doubt in my head. Without any hesitations, I give it to Monogon with his blog post about priority-queue-like undoings on data structures. It ticked all the boxes I wanted from this challenge. It is a novel idea that is pretty easy to understand and implement at the same time. The explanation is clear and concise. I highly recommend everybody who is at least orange read it. So congratulations to Monogon. The $300 prize is yours!
Thanks to rafaelgo we also have a prize of $50 for second place. And this decision was much harder to make. In the end, it came down to two candidates:
First is adamant with his blog post on online FFT and its generalization. I am a big fan of FFT, generating functions, and similar algebraic viewpoints on combinatorial problems. For me even the online FFT part was new, and even though it was already explained somewhere before, I enjoyed the explanation and the examples. And the generalization just looks like magic even though you understand that "yeah, should work I guess". Definitely not a beginner FFT material though!
Second is ko_osaga with his series of blog posts on range longest increasing subsequence queries. It's based on a research paper (with the author of which I actually had an opportunity to work on the related algebraic structure of LIS a couple of years ago but I decided to not do it, maybe I should have...), and hats off to ko_osaga for simplifying and codeforcesifying it. It is fascinating that such a classical simple problem can be viewed from a very different perspective, and tools you wouldn't expect to see arise. I wouldn't lie, I was not yet able to understand everything there, but I got the main ideas. Again, please, don't try to read it if you want to learn LIS. Come back 5 years later.
It was a hard decision but I decided to go with the first one as the topic resonated more with me, and at the end of the day if there are two great ideas, why not go with the one that is easier to understand and implement? :) Congratulations to adamant on the second place! Nevertheless, congratulations to ko_osaga for the third place.
I will contact the first two winners shortly and send them their prizes. (UPD: done)
And now the list of all other entries in no particular order:
- CMS trick by Dragonado. I was happy to see a submission from a purple user. Was sad that there weren't many. Interesting idea, I always like it when two segment trees communicate with each other.
- Convex optimization blog series by chromate00. And blue ones too, right? Math is not as scary as you think it is.
- On variations of string matching by brunomont. There are many different techniques for string matching. Nice to collect them all together. The wildcards one was new to me.
- Centroid decomposition for very sparse graphs by dimss. Simple and at the same time not obvious idea.
- FFT tutorial by -is-this-fft-. Solid tutorial with a good problem selection. I just didn't find any novel ways to explain stuff there for it to be great. Nevertheless, if you want to learn FFT, it is a place to go to.
- Simulated annealing by qwerty787788. External blog with cool animations. More of an exploratory approach to a simple idea that is not that easy to make work properly.
- Sometimes it's not their fault by Lyde. The only non-algorithmic entry in this challenge. I think what I got from this blog is that if I like a contest, I should write a comment about it.
- Push-Free Segment Tree by nikgaevoy. The main idea is pretty simple. I also used it sometimes. But the applications for the 2D case were novel to me. Good stuff.
- Two more blogs by adamant. I decided to not count them towards the win of the entry on FFT because it was a competition of blog posts, not people. The first one on permutation "basis" was very clear and not-too-mathy. The second one as I promised I did not really read into details yet. It is a continuation of a blog from 8 months ago that I also did not yet read. Looks scary and interesting.
Thank you for your attention. Arm Ukraine!
