June 20, 2017 10 Years of Problem Writing: My Favorite Problems

This June I’m celebrating an anniversary – exactly 10 years since the fateful “Ok, HS SRM 34 is yours” email from the Algorithm coordinator which marked my entrance into the world of writing problems for Topcoder. As I look back at all the contests I’ve written over the years, I want to share with you some of the problems which are special for me.

Three Favorite Marathon Problems

#1 PolygonArea
Short and clean statement reveals an elegant measurement-based problem in which it’s up to you to decide which points you need to get the most precise answer. This match had one of the highest ever participation levels for a non-tournament match, it was one of the best problems I’ve ever written, if not the best one, – and it definitely secured my problem writing career!
#2 MovingNQueens
This was the first problem I wrote after an almost-three-year-long break I had to take due to visa restrictions. The credit for the idea goes to my husband – he loves chess and chess-based puzzles. Again, it is a problem with short and clear concept and some really interesting solution approaches – and it marked my comeback!
#3 Layout problems
It was unexpectedly hard to pick the third-favorite problem. I love image-based problems, so BrokenClayTile was a strong contender. I also love game-based problems, and I’ve had lots of fun playing prototypes of ChessPuzzle and TwistedGame (both of which also have rather nice visualization).
But in the end I’ve decided to go with a layout problems: problems which require to draw some simple objects on a plane to satisfy certain constraints and/or to optimize certain function: MegaParty, Planarity, QualityPolygons, SmallPolygons and GraphDrawing. I like how intuitive these problems are and how naturally they map to a visualization; the only issue with them is that there shouldn’t be more than one of them in each given year 🙂

Three Favorite Algorithm Problems

#1 AgeEncoding
My favorite part of an SRM is Challenge Phase – that’s what makes this contest format different from every other contest out there. So naturally my favorite problem would be one which provided ample challenge opportunities and had less than 10% success rate in Div1.
#2 WallClimbing
Writing Div1 Hard problems is a major challenge for me, and this problem is one of the only two I’ve created for Topcoder. It was used in the first ever Member SRM – the series of SRMs created by volunteer authors to support more frequent SRMs in 2009-2011. So when I think about this problem, I’m both proud that I could come up with it and happy that I contributed back to the community.
#3 PingPongQueue
What can I say? I just like playing ping-pong 🙂

Three Memorable Problems

Some problems are, well, just problems – I’ve stumbled more than once on a problem written by me which I had absolutely no recollection about. Nice surprises, they are, but I prefer memorable problems, problems which leave great memories and make great stories to tell. Here are a few.
#1 BounceOff (a.k.a. The pure joy of creation)
This problem featured rather complicated geometrical calculations for the ball trajectory. I spent many hours coding and even more debugging the code, and all this time the ball kept rocketing off the field in random direction with insane acceleration or teleporting between random places. And then finally there is was – the perfect trajectory! This moment is the one I think about when asked what do I like about programming, even though the code itself ended up thrown away later.
#2 GrilleReconstruction
This match launched on December 31st, and the participants pointed out a scoring bug right away, so I spent a big part of my New Year’s night fixing it. You know what they say, how you spend New Year’s Eve is how you’ll spend the rest of the year, and indeed it turned out a rather good year.
#3 MegaParty
This is the problem which had the least time from approval (Sunday night) to launch (Wednesday), and the fastest Marathon problem preparation I’ve ever done. Since then I start conversations about which problem we should use for the upcoming match a lot earlier!
Many happy returns to me!