Hello Codeforces,
This year certainly was one of the years of all time. With it coming closely to an end, I think it would be worth to reminisce and applaud the greatest contemporary problem setting creations. Which problem made you your year?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello Codeforces,
This year certainly was one of the years of all time. With it coming closely to an end, I think it would be worth to reminisce and applaud the greatest contemporary problem setting creations. Which problem made you your year?
Name |
---|
1758D - Интервал = √Суммы was the problem that surprised me the most this year — and I still don't understand my own two-pointers solution(182519051) on it!
What were you surprised by in this problem?
The fact that A-D were all mid constructives that round
1673F — Anti-Theft Road Planning was the problem that made my year.
probably the simplest div2F for me lol
I don't have a link but:
Se da un sir de cifre separate prin operatori '*', '+', '-', '/', '^', '&', 'XOR', '!' '|'. Avand voie sa faci maxim K interschimbari intre operatori, aflati valoarea maxima a expresiei.
Marinush
This one
1687F - Koishi's Unconscious Permutation Certainly the most complicated g.f. tasks I have solved so far.
I also like ARC145F Modulo Sum of Increasing Sequences / 147F Again ABC String.
Sorry that I haven't solve much this year.
1748D - ConstructOR
Problem with Random Tests. randomized algorithms
1634B - Гадание на массиве, 1740G - Опасные лазеры, 1740H - MEX и манипуляции с деревом, 104094H - Одномерная игра.
If you asked me what would be the problem that encapsulates this years the best, I would certainly answer this one. Sadly the statement is in romanian, so the broader audience won't understand it.
I think maspy's D — Simultaneous Sugoroku deserves this place. Too beautiful problem.
It somehow reminds me of the dragon curve (paper folding).
DMOPC '21 Contest 9 P4 — Ace of Diamonds
I always look forward to seeing the blog "favorite problems of years X" :) I had so much fun solving so many different tasks through this year!
Here are some problems which made me very happy this year:
E. >= K it looks complex at first and it's easy to get lost in the implementation, but with a proper insight it's surprisingly simple
G. Anti-Increasing Addicts this just made me laugh out loud when I got AC
CEOI 2022 abracadabra the main idea is very cute, I saw it one Slovak problem once and I wished to see it again. My wish came true month later :)
E. Colorful Operations this problem looks standard at first but it has one surprisingly very cute idea which made me smile when I figured it out.
it's enough to just keep track of the sum of the values added to each color and also for each cell the sum of values the color of this cell received before we recolored it to this color.
BOI 2022 communication (the original joking problem) very creative statement and also very creative and surprising solution.
D. Koxia and Game the underlying idea is very cute and unexpected.
I'm sure there are more problems which are worth mentioning. I'll update the list when I'll remember them :)
USACO January Gold P3 — Tests for Haybales
Disclaimer: none of these is on this list necessarily because they are particularly beautiful in some algorithmic way.
Jolteon
Vaporeon
New Home
Stray Cat
Circuit
The Third Grace
Abracadabra
Bârligă! (Don't have link)
1753C - Знал бы я, как сортировать массив....
This is definitely the most beautiful problem I've solved this far.
Yet another vote here for CEOI 2022 Abracadabra.
It initially looked hard and I thought I'd have to implement something high powered, but the central idea is so simple and really elegant.
AGC057 C, AGC 057 D, AGC 058 D
Can you teach me how to be good at AGC?
Although I really loved God of War Ragnarök, it turned out Elden Ring won this year.
Thanks to all problemsetters for creating beautiful tasks in this year!
1729E — Guess the Cycle Size
An unusual type of problem, there is no solution that is 100% correct.
Also 1729 is the Hardy-Ramanujan Number, very well known in mathematics
1715F —— Crop Squares
C1,C2. Sheikh I would appreciate this problem , I tried so many different approaches and made many submissions and every time I was amazed to what test case it failed and I learned so many things too.
https://loj.ac/p/3626
You have a tree, and each point has a point weight $$$v_i$$$ . You need to find the determinant of a given matrix.
Related to matching on the tree
Oops!It came out in 2021's winter.But it's really a interesting problem.
G. Kirill and Company
F — Pay or Receive
E. Black and White Tree
1705E - Марк и профессор Коро
1715F - Квадраты на полях
1771C - Хоссам и ученики made the year.
1737D — Ela and the Wiring Wizard
The best problems I've seen this year are :
1750F - Majority
It's a unique way of looking at the overlapping subproblem, I've seen very few dps that are this creative.
1637G - Birthday
It was really not obvious to me that you can only end up at $$$2^k$$$ at the end. In retrospect, it makes sense, since I need to get $$$1$$$ eventually, and in reverse I'm only dividing by $$$2$$$. But I brute forced upto around $$$n = 9$$$ to even consider it a possibility. The actual construction is quite interesting as well, basically dp on Arithmetic Progressions, hard to spot the similarity with everything else.
1687E - Become Big For Me
The first part is quite simple, you realise not too many primes can be a factor of $$$n-1$$$ out of $$$n$$$ numbers. So we do some pruning and end up with only 20 numbers. That I think is the easy part. The hard part is effectively. You have array of size 20.
You want to somehow find a way to use subset max to find the smallest and second smallest element, but it has to be linear in all subset maxes, and work for all locations of smallest and second smallest. These kind of "no ifs" programming is something I really like, enjoyable problem.
Funnily enough, while looking through my solves, far too many good problems were made just 2 months before 2022.
My favorite problems just before 2022
1586E - Moment of Bloom
1586F - Defender of Childhood Dreams
1586G - Omkar and Time Travel
1610F - Mashtali: a Space Oddysey
1615F - LEGOndary Grandmaster
I really liked solving this problem 104067H - Расстановка тыкв. Also this C is nice also 1761C - Построение множеств
CF :
1646E - Степенная таблица
1736C2 - Хорошие подмассивы (сложная версия)
1691F - Дерево и k-подмножества
1700E - Пират Сережа
1733E - Конвейер
1743F - Пересечение и объединение
Atcoder :
ABC261Ex⠀--⠀Game on Graph
ABC281G⠀--⠀Farthest City
ABC272G⠀--⠀Yet Another mod M
ABC270G⠀--⠀Sequence in mod P
ABC243G⠀--⠀Sqrt
ABC268E⠀--⠀Chinese Restaurant (Three-Star Version)
ARC150C⠀--⠀Path and Subsequence
ABC263E⠀--⠀Sugoroku 3
ABC282G -- Similar Permutation
DMOJ :
YAC3P2⠀--⠀Work Experience
1771B - Хоссам и друзья
1773A — Amazing Trick
1624G — MinOr Tree
ABC273E — Notebook
ABC268E — Chinese Restaurant (3-Star Version)
ABC262E — Red and Blue Graph
https://codeforces.net/contest/1695/problem/D2
My favorite one.
There were many great problems that I solved this year. Here are some that I liked the most:
When flipping some value, you do not care about what other values are as the change of the result will be the same. The reason is that result is just a linear function that takes states of gates as inputs. And the nice thing about having linear function f(a,b,c...) is that f(a+da,b,c...)-f(a,b,c...) only depends on da. Makes sense when you write it out, but intuitively it does not.
By keeping the diameter of the tree but only of nodes that are far from 1. (Further than f(x)) I actually at first did it using segment tree + LCA, but it TLE-ed. Then I realized that all my queries are from L to N, so I just did something similar to the suffix sum. Similar to problem E from the local competition.
non-mentioned but very very cool problems
1667C - Покрытие полуферзями
1628C - XOR-сетка
1654F - Минимальное XOR-ирование строки
Thanks :)
For me it's no doubt Fake Plastic Trees 2 from Winter Petrozavodsk Day 2. It looked like a completely unsolvable problem, so it was so satisfying to finally solve it, I felt like a genius
Doremy's Pegging Game — The idea of the solution is really nice.
Changed my mind, this is the greatest problem
1736B - Играем с НОД
ARC 147D CF 1693C
1726A. Mainak and Array for the wrong reasons. Common mistake would be printing the difference between the maximum and minimum element. The mistake gave an answer of "996" (72 hours a week) instead of "962" (18 hours a week). So we made the servers work an "extra 54 hours" to process the influx of incorrect solutions
For me the greatest problems were :
1762D - Запросы НОД
1733D2 - Ноль-один (сложная версия)
And those problems were nice and I enjoyed solving them although they are a bit easy:
1697D - Угадай строку
1772F - Копия копии копии
1713D - Отсчет турнира