Hi Codeforces,
Time goes by, and so should we. And it seems that the time has come for this year. So, it's a great time to reflect on and appreciate the standout problem sets that made this year memorable. What specific problem stands out to you as the highlight of your year?
PS: For the problems included in some of the most upvoted comments, I think I will host a poll to truly get the best problem of the year (so problems should be from a contest pertaining to this year). Applications (meaning comments taken in consideration) for this will naturally close at the end of the year after we've had time to see all of them.
Watermelon
I've mentioned this before, but CF round 887 contains some of my favorite problems of the year. ABC are all great, B in particular is one of the best constructives I've seen (at least for problems of that level). This round also holds a special place in my heart, as my first ever div1 contest ;)
1882D - Tree XOR
1889B - Doremy's Connecting Plan Interestingly enough when I solved it I didn't really feel anything but only when I was discussing it with my friend this problem somehow touched my heart
Mine is definitely to become max since …
it’s such a cool and creative application of binary search?!
In order of difficulty:
1864C - Divisor Chain and 1842D - Tenzing and His Animal Friends require standard ideas in a context which seems completely unrelated.
1839E - Decreasing Game and 1844E - Great Grids require multiple cool steps.
1789F - Serval and Brain Power and 1830C - Hyperregular Bracket Strings require some very unusual ideas that I have not seen anywhere else.
1776C - Library game's solution is much cleaner than one may expect.
1889D - Game of Stacks is just magic.
in Game of Stacks , idea is to remove the cycles since their removal will not affect the result.
I mean, the idea is quite intuitive after you come up with it, but it's hard to believe something so simple just works.
Agreed , I also find the idea quite neat and beatiful. I think it is a good candidate for the problem of the year.
My most favourite is for sure 1844G - Tree Weights. The problem itself is natural, and the solution is cute!
For me it is Tourism from JOI Spring Camp :3
D2. Prefix-Suffix Palindrome (Hard version)
Iva & Pav
Data Structures Fan
Sum in the tree
Serval and Brain Power by Serval (February)
M-tree by RDDCCD (March)
Tenzing and Tree by ??? (June)
Imbalanced Arrays by synths (July)
Candy Party (Easy) by Error_Yuan (September)
Turtle and GCD by skye__ (October)
Bonus! Aranara Game (easy) by oursaco (March)
Serval and Brain Power
I remember that my first solution to Serval and Brain Power was borderline cheese, since i didn't realize that the 4 case is already covered in the 2 case. As such, it ended up being >1s TL and I thought the constraints of the problemn were poor. But even then I thought it was a great problem. After reading the editorial and removing the 4 case I liked it even more; I had never previously seen this sort of problem where it looks like brute force is barely too slow and you need to use some logic to show that you can use a faster idea on other cases. It also uses a trick based on observation rather than some random heuristic pruning / optimization which tend to be both unsatisfying and hard to prove (I am very bad at proving and guess too much so it's probably why I get wrong answer so frequently in contests haha)
M-tree
I am more biased than normal for this problem because I did it with a friend (oursaco) over discord which surprisingly was wayyy more fun than solving a problem alone (though I wouldn't do it regularly); I thought it would be worse online but it wasn't. Honorable mention to another problem I did with a friend (but irl instead at school), which was Laboratory in Pluto. That one didn't make the list even though it is a great problem cause I think the first subproblem is pointless and doesn't add to the second, and I'm told the second problem is very standard. Anyway, oursaco (being the genius he is) was able to find the very clever base-m idea after we had both done the basic maths to simplify everything, which means I didn't solve this problem at all, but I still think the idea is very cool.
Tenzing and Tree
I couldn't find which of the round authors wrote this problem, but it's fron CodeTON 5. Anyway this problem feels particularly special since I spent like 2 hours thinking on this problem pondering the normal Absolute Value ideas you see in competitive programming and at one point I ended up in the state of mind where I wasn't distracted or anything but I just couldn't focus or think at all aside from repeating the statement in my head. I eventually came across the centroid idea and it felt very clever since the solution still manages to utilize the absolute value property without doing it in a boring way like literally every other absolute value problem.
Imbalanced Arrays
Heavily biased on this one since the problemsetter is one of my very best friends :), but I think this is one of the cooler constructives as every step feels super natural and no part of the problem, not even the proof, requires some sort of magic leap of faith. All of this while still requiring thinking every step of the way.
Candy Party (Easy)
Similar boat with the previous problem. I have a sort of love/hate relationship with greedy problems since they can be so smart but also super unsatisfying or guessworky. This problem feels the perfect difficulty for its position (I think greedy problems typically have wayyy lower rating than they should since you don't have to prove in CP so the rating and position of this is actually fantastic) and I remembered enjoying proving and solving it in contestm, which I typically don't since I dislike doing contests in general and prefer practice @_@. I also prefer this to the harder version since the harder one feels like a bit more implementation for a more unsatisfying idea (I definitely didn't prove the harder version in contest).
Turtle and GCD
The problemsetter is yet another one of my best friends on this site, and I did this problem while testing his contest (I only ended up trying one of the other problems XD I'm a bad tester but that's a different story). And being from a school contest I thought it would both be very easy and very standard; I thought about the dinner and pineapple I was going to have later instead of solving the problem. With that said, I ended up eating dinner 2 hours late. But story aside, I generally hate NT problems cause all the ones I've done (usually the 1500-2400 CodeForces stuff) always feel like the same problem repeating the same sqrt trick / divisor trick / use primes to do some magic / mobius / etc. and I always get stuck on TL because I don't understand number theory complexity haha. But I guess why this problem doesn't have that is because there's also some combo involved (which you'd never guess looking at the problem), which makes it even cooler. I also had a cheese solution initially but I eventually fixed it to the intended. It also seems Um_nik and InternetPerson10 have some dark magic faster solutions which is cool too.
Aranara Game (Easy)
Possibly the funniest problem of 2023. It's also in my opinion the best and coolest print(input) problem out there. Despite this, I can easily see why alot of teams in HPI (the contest its from) didn't solve it.
As always, thanks to all problemsetters who wrote problems this year :). Thank you for writing problems!
https://codeforces.net/problemset/problem/1863/H
Loved the Pinley round in general, especially Goldberg Machine 3. Thanks Endagorion!
This is a good shortest path problem: 1860E - Fast Travel Text Editor
Common W for Iva & Pav :)
koxia and number theory
Swap and Reverse
1804F — Approximate Diameter
1835C — Twin Clusters
1863G — Swaps
1876E — Ball-Stackable
AGC064D — Red and Blue Chips
1804F — Approximate Diameter a nice problem on approximate algorithm which is not very prevalent in CP
1835C — Twin Clusters a non-trivial application of pigeonhole principle. Also it is quite interesting to see birthday paradox being used in CP problem not related to hash :O
1863G — Swaps, 1876E — Ball-Stackable, AGC064D — Red and Blue Chips I think the rest three problem go into the same category: simple setting, an fascinating math model, and a chain of interesting observation require to solve the problem
Here are some problems I remember being very nice imo (in no particular order):
1860D - Balanced String , this is the problem that took me to the candidate master !!
1830E — Bully Sort
(totally unbiased opinion :clown:)
Probably sorted by difficulty:
1909B - Make Almost Equal With Mod
104782A - Maximum Distance
1829H - Don't Blame Me
1917E - Construct Matrix
START113 - Make All Equal
1898E - Sofia and Strings
1837F - Editorial for Two
ABC290H - Bow Meow Optimization
OII23C - Arte nei corridoi
1909B - Make Almost Equal With Mod: Finally found another god tier problem B after 1634B - Fortune Telling.
104782A - Maximum Distance: Simple but good observation, I really like it.
1829H - Don't Blame Me: Not a complicated bitmask DP problem, but I somehow couldn't solve it during the contest. It's a very nice practice problem if you're just starting to learn bitmask DP.
1917E - Construct Matrix: If you also like it, here is another one 1628C - Grid Xor.
START113 - Make All Equal: The proof by using grid that called "classical idea" in the editorial is amazing.
1898E - Sofia and Strings: The problem itself is good, but it became even better when I managed to solve it with the constraint $$$a_i \le 10^9$$$ instead of $$$a_i \le 26$$$.
1837F - Editorial for Two: Love this one.
ABC290H - Bow Meow Optimization: Probably the hardest problem I have solved this year, it took me several days to understand the $$$\mathcal{O}(n\log{n})$$$ solution.
OII23C - Arte nei corridoi: I didn't fully solve this one, subtask 6 is nice, but subtask 7 is a big jump to an IOI-level problem (or maybe not).
The path is $$$0 \rightarrow x \rightarrow 1 \rightarrow x \rightarrow 2$$$. For subtask 6, you are probably iterating over $$$x$$$. For subtask $$$7$$$, can you find the best $$$x$$$ fast? First of all, instead of fixing $$$k$$$ and iterating over $$$x$$$, fix $$$x$$$ and find the cost as a function of $$$k$$$.
Personal opinion of the candidates of best problems that I have viewed or done: (in no particular order)
1834E - MEX of LCM
1854D - Michael and Hotel
1789F - Serval and Brain Power
1889D - Game of Stacks
1863G - Swaps
1844G - Tree Weights
1844F2 - Min Cost Permutation (Hard Version)
problems I found interesting and/or learned a lot from
1864D — Matrix Cascade
1864E — Guess Game
1854A2 — Dual (Hard Version)
1848F — Vika and Wiki
1844E — Great Grids
1817D — Toy Machine
1794D — Counting Factorizations
1859E — Maximum Monogonosity
1852C — Ina of the Mountain