Topcoders Favorite Problems of 2020

Last week we reached out some of our members who contributed to Topcoder Algorithm Track in some way or the other by writing, testing and competing regularly or at the highest level in 2020.

I thought like me, many members would be interested and keen on knowing their favourite Topcoder problem of the year and why did they pick that.

Choosing one(1) is always hard so we gave these greats an option to pick three. Check out what did they pick and why:

PS: We have some more interesting submissions coming in - we will keep updating the article time to time ;)

misof

It’s so hard to choose, on another day I would probably pick other three but I like the three I picked, so shrug. Here are my top 3 at the moment

• BinarySearch (by laoriu)

• RoseDressGame (by misof)

• DiscountedShortestPaths (by jy_25)

tourist

• SRM 789 FollowingNim: an interesting addition to the Nim game made a nice problem with several layers of reasoning.

• SRM 795 DiscountedShortestPaths: An unexpected usage of spanning trees for finding shortest paths in a special setting.

• Two problems of similar style, TCO Round 3A Hamiltons, and TCO Europe Final Round GreedyKiller: “find a test case to kill this greedy algorithm” problems with nice parametrizations which turned them into fair input-output problems.

lg5293

• FollowingNim - Of course, I have to choose one of my own problems as a favourite. I liked this one since there are a lot of small steps towards the solution and each of those is not particularly hard to follow

• DiscountedShortestPaths - jy_25 has been writing a lot of good problems lately, and this is yet another example of a great problem. The relaxation from shortest paths to MST is something very unique.

• SoccerStadium - This is square1001’s medium from their first SRM as an author. It does look like a bitmask DP problem at first, but this problem has a lot of nice observations that make it easier and easier until it becomes obvious how to finish it.

Petr

• FollowingNim - Because the way the special moves lead to just “skipping” some numbers when computing the nimbers is amazing.

• BinarySearch - Because of the way the dynamic programming ends up being polynomial and not exponential quite unexpectedly.

• DiscountedShortestPaths - Because of the way we completely unexpectedly replace the actual task with a different one but for which applying the discounts is easier.

Bqi343

Benjamin had a clear and interesting choice:

• TaleOfTwoSquares

espr1t

• ClassRankings - Interesting DP with relatively short and easy to grasp statement.

• ChristmasSnake - It required observations to get the right idea and some thought to create nasty test cases. Codewise it included very standard algorithms, although being D1 Medium.

• EllysNim - It is a variation of a very well known problem, solved entirely in a different way. The code that solves it is short, but the observations are hard.

laoriu

laoriu had some interesting picks too. Do check them out.

• EllysFlags

• BinarySearch

• FollowingNim

a.poorakhavan

• PaintItBlack - This was a nice graph problem and also very creative.

• Cascade - Nice DP, Math problem to solve

• AqaAsadiSaves - Again a graph problem but had a nice combination of ideas.

KaasanErinn

Our Topcoder Algorithm Admin

• ChristmasBatteries

• OneForYou

• CardDrawPoints

square1001

• TCO20 Round 2A - PrimeSubstrings. I really like it, especially that the complete construction is possible for L<=7 but not L>=8. I could estimate the boundary probabilistically, using prime number theorem, and I thought the aspect of prime number from different directions are full of mystery.

• SRM 776 Div1 Hard - FinishingDice. This is my favourite Div1 Hard of 2020. This problem requires the idea to express the probability distribution by polynomials, and if we come up with it, we can solve it elegantly by polynomial division. Also, I think that the amount of solution-thinking and implementation was well-balanced for Div1 Hard.

• SRM 788 Div2 Medium - StarsInTheSky. This is the problem in my first contest creation. I freshly remember that, during the contest, there were submissions of two completely different solutions, which is interesting for contestants (of course when it comes to challenging phase, and it also urges participants to understand others’ solutions). Moreover, we can learn two different things, exponential search and coordinate compression, with just a single problem. Since the difficulty is also appropriate for Div2 Medium, I chose it as one of my favourite problems.