Hi everyone! As we're reaching the end of this year and as AI becomes smarter, I'd like to write such a blog, motivated by similar blogs by adamant, by tibinyte2006, by antontrygubO_o, by wuhudsm and by satyam343.
I am a member of the SUA Programming Contest Problem Setter Team, so most of the problems I authored are for the onsite contests prepared by our team. I would like to thank all our team members for discussing the problems with me, and preparing some problems for me after I attended work. What's more, I would like to thank them for being kind and supportive friends in my everyday life. Without them, my world will become dim.
It is astonishing to find out how many of these problems are related to my life. There are ideas from the (board) games I played, from the songs I listened to, and even from the places I've passed by. I can vividly remember how I came up with the idea, how I discuss it with my friends, how I learned new algorithms through preparing the problems when I wrote this blog. This is not just a collection of my problems, it even feels like a diary for my past years. I don't care about how AI might ruin this contest, I just felt grateful that I had the chance to share my life with so many friends and contestants through these problems. Thank you, my dear competitive programming community, for giving me this unforgettable experience.
This is not a comprehensive list as it only contains publicly available problems. I'll try to update this blog each time after we make our new contests public. Also the ratings below are a (maybe very biased) estimation from my perspective, so it might not be precise.
# | Problem | Contest | Rating (Est.) | Tags | Comments |
---|---|---|---|---|---|
125 | Bingo | 2024 ICPC Nanjing | 2500 | combinatorics | Idea from a meme. |
124 | Binary Tree | 2024 ICPC Nanjing | 2000 | interactive, trees, divide and conquer | |
123 | Strips | 2024 ICPC Nanjing | 1800 | constructive, greedy | |
122 | Social Media | 2024 ICPC Nanjing | 1400 | sortings, enumeration | |
121 | Left Shifting 3 | 2024 ICPC Nanjing | 1200 | enumeration | |
120 | Stop the Castle 2 | 22024 ICPC Kunming Invitational | 2600 | bipartite matching | |
119 | Collect the Coins | 22024 ICPC Kunming Invitational | 2400 | binary search, dp | One of the problems I liked, as the key observation is nice. |
118 | Subarray | 22024 ICPC Kunming Invitational | 2500 | fft | |
117 | Trails | 22024 ICPC Kunming Invitational | 2300 | binary search, dp | Idea from the board game Trails, although it is not very related to the game mechanism. One of the problems I liked, as it requires the contestants to have a good understanding on using binary search to calculate LIS. |
116 | The Quest for El Dorado | 22024 ICPC Kunming Invitational | 2200 | shortest paths, data structures | Idea from the board game The Quest for El Dorado. |
115 | Italian Cuisine | 22024 ICPC Kunming Invitational | 1900 | geometry | |
114 | Relearn through Review | 22024 ICPC Kunming Invitational | 1900 | math theory | |
113 | Two-star Contest | 22024 ICPC Kunming Invitational | 1600 | greedy, constructive | Idea came from the event that some experts ranked ICPC as a two-star contest, because they can't get the statistics about ICPC so they just esimate them with the lower-bounds. |
112 | Left Shifting 2 | 22024 ICPC Kunming Invitational | 1400 | enumeration | |
111 | Gold Medal | 22024 ICPC Kunming Invitational | 1200 | sortings | Idea came from the fact that there are 5 contests going on at the same time in that weekend. |
110 | Triangle | 2024 CCPC Shandong Invitational | 3000 | strings, combinatorics | |
109 | Palindromic Polygon | 2024 CCPC Shandong Invitational | 2300 | geometry, dp | |
108 | Stop the Castle | 2024 CCPC Shandong Invitational | 2200 | bipartite matching | |
107 | Hero of the Kingdom | 2024 CCPC Shandong Invitational | 2000 | sqrt trick | Idea from the game Hero of the Kingdom. |
106 | Colorful Segments 2 | 2024 CCPC Shandong Invitational | 1700 | sortings, combinatorics | |
105 | Divide the Sequence | 2024 CCPC Shandong Invitational | 1600 | suffix sums, greedy | Coincides with CF1175D. |
104 | Printer | 2024 CCPC Shandong Invitational | 1400 | binary search | |
103 | Matrix | 2024 CCPC Shandong Invitational | 1200 | constructive | |
102 | Left Shifting | 2024 CCPC Shandong Invitational | 800 | enumeration | |
101 | Ticket to Ride | 2023 ICPC Jinan | 2900 | dp | Idea from the board game Ticket to Ride. One of the problems I liked, because the optimization needs some creative thinking. |
100 | Rainbow Subarray | 2023 ICPC Jinan | 1900 | two pointers, data structures | Idea from the board game TEN. |
99 | Largest Digit | 2023 ICPC Jinan | 800 | enumeration | |
98 | Red Black Tree | 2023 ICPC Nanjing | 2600 | trees, dp, convex optimization | |
97 | Trapping Rain Water | 2023 ICPC Nanjing | 2200 | data structures | |
96 | Elevator | 2023 ICPC Nanjing | 1900 | greedy | |
95 | Cool, It’s Yesterday Four Times More | 2023 ICPC Nanjing | 1800 | bfs | |
94 | Primitive Root | 2023 ICPC Nanjing | 1600 | bitmasks | Idea from a meme. |
93 | Counter | 2023 ICPC Nanjing | 1200 | sortings | |
92 | Trie | 2023 Shandong Provincial | 2600 | strings | One of the problems I liked, as it requires the contestants to have a good understanding on suffix arrays. |
91 | Colorful Segments | 2023 Shandong Provincial | 2400 | dp, data structures | |
90 | Difficult Constructive Problem | 2023 Shandong Provincial | 2200 | dp | One of the problems I liked. It looks like some constructive algorithms, but it is not. |
89 | Building Company | 2023 Shandong Provincial | 1700 | topological sort | Idea from the board game Splendor. |
88 | Matching | 2023 Shandong Provincial | 1200 | greedy | |
87 | Orders | 2023 Shandong Provincial | 1000 | sortings | |
86 | Classic Problem | 2023 Guangdong Provincial | 3000 | minimum spanning trees | Very standard Boruvka algorithm problems. |
85 | Canvas | 2023 Guangdong Provincial | 2600 | graphs, constructive | Idea from the board game Canvas. One of the problems I liked, as the modeling process is nice. |
84 | Computational Geometry | 2023 Guangdong Provincial | 2000 | geometry | |
83 | New but Nostalgic Problem | 2023 Guangdong Provincial | 1900 | strings, data structures, greedy | |
82 | Base Station Construction | 2023 Guangdong Provincial | 1900 | dp | |
81 | Path Planning | 2023 Guangdong Provincial | 1600 | binary search, sortings | |
80 | Peg Solitaire | 2023 Guangdong Provincial | 1400 | searching | Idea from the chess game Peg Solitaire. |
79 | Programming Contest | 2023 Guangdong Provincial | 800 | enumeration | |
78 | NaN in a Heap | 2022 ICPC Nanjing | 2600 | combinatorics | I came up with the idea when dealing NaNs at my work. |
77 | Drain the Water Tank | 2022 ICPC Nanjing | 1900 | geometry | |
76 | Ropeway | 2022 ICPC Nanjing | 2100 | dp | |
75 | Chat Program | 2022 ICPC Nanjing | 1900 | enumeration, prefix sums | |
74 | Stop, Yesterday Please No More | 2022 ICPC Nanjing | 2000 | enumeration, prefix sums | |
73 | Inscryption | 2022 ICPC Nanjing | 1400 | greedy | Idea from the game Inscryption. |
72 | Perfect Palindrome | 2022 ICPC Nanjing | 1000 | greedy | |
71 | Permutation on Tree | 2021 ICPC Macau | 3000 | trees, dp | The complexity can be as low as $$$\mathcal{O}(n^2)$$$. |
70 | Cyclic Buffer | 2021 ICPC Macau | 2100 | dp, data structures | I came up with the idea when passing through a stereo garage. |
69 | Laser Trap | 2021 ICPC Macau | 1900 | geometry | |
68 | Link-Cut Tree | 2021 ICPC Macau | 1500 | greedy, dsu | |
67 | Card Shark | 2022 Bytedance-Moscow Workshops Camp | 1900 | euler paths, greedy | Idea from the game Card Shark. |
66 | Paimon's Tree | 2021 ICPC Nanjing | 2700 | trees, dp | One of the problems I liked, as the idea is kind of different from the traditional dp on trees. |
65 | Cloud Retainer's Game | 2021 ICPC Nanjing | 2100 | DP | Idea from the mobile game World Flipper. |
64 | Paimon Sorting | 2021 ICPC Nanjing | 2100 | data structures | Idea from Hacker News. |
63 | Direction Setting | 2021 Sichuan Provincial | 2300 | flows | |
62 | Nihongo wa Muzukashii Desu | 2021 Sichuan Provincial | 800 | implementation | |
61 | Chuanpai | 2021 Sichuan Provincial | 800 | enumeration | |
60 | Degree of Spanning Tree | 2020 ICPC Nanjing | 2600 | greedy, constructive | |
59 | Evil Coordinate | 2020 ICPC Nanjing | 1700 | constructive | |
58 | Let's Play Curling | 2020 ICPC Nanjing | 1400 | greedy | I came up with the idea when watching a curling match on TV. |
57 | Portal | 2020 GPLT | 2600 | data structures | |
56 | Path to Infinity | 2019 Winter PAT Top Level | 2500 | meet in the middle | |
55 | Coolbits | 2019 Shaanxi Provincial | 1800 | bitmasks, greedy | |
54 | 0689 | 2019 Shaanxi Provincial | 1600 | enumeration | |
53 | Grid with Arrows | 2019 Shaanxi Provincial | 1400 | graphs | |
52 | K-hour Clock | 2019 Shaanxi Provincial | 1000 | number theory | |
51 | Digit Product | 2019 Shaanxi Provincial | 800 | implementation | |
50 | Heap | 2019 Shandong Provincial | 1900 | data structures | |
49 | Triangle City | 2019 Shandong Provincial | 1900 | shortest paths | |
48 | Game on a Graph | 2019 Shandong Provincial | 1000 | games, graphs | |
47 | Stones in the Bucket | 2019 Shandong Provincial | 1000 | greedy | |
46 | Sekiro | 2019 Shandong Provincial | 800 | implementation | |
45 | Calandar | 2019 Shandong Provincial | 800 | implementation | |
44 | Array in the Pocket | 2019 Zhejiang Provincial | 1900 | greedy, constructive | |
43 | Strings in the Pocket | 2019 Zhejiang Provincial | 2000 | palindromes | |
42 | Element Swapping | 2019 Zhejiang Provincial | 1700 | enumeration, math | |
41 | Sequence in the Pocket | 2019 Zhejiang Provincial | 1400 | sortings, enumeration | |
40 | Fibonacci in the Pocket | 2019 Zhejiang Provincial | 800 | math theory | |
39 | Lucky 7 in the Pocket | 2019 Zhejiang Provincial | 800 | enumeration | |
38 | Strange Function | 2019 ZJU School Contest | 2500 | data structures, enumeration | |
37 | Robot Cleaner II | 2019 ZJU School Contest | ? | genetic algorithm | Idea from the book Complexity: A Guided Tour Chapter 9. |
36 | Robot Cleaner I | 2019 ZJU School Contest | 1400 | bfs | Idea from the book Complexity: A Guided Tour Chapter 9. |
35 | Postman | 2019 ZJU School Contest | 1200 | greedy, sortings | |
34 | Potion | 2019 ZJU School Contest | 1000 | prefix sums | |
33 | Kawa Exam | 2018 ICPC Qingdao | 2500 | dsu on tree | A standard dsu on tree problem. I learned this algorithm for the first time when preparing for this problem. |
32 | Airdrop | 2018 ICPC Qingdao | 2000 | enumeration | |
31 | Sub-cycle Graph | 2018 ICPC Qingdao | 2300 | graphs, combinatorics | Almost all un-official tutorials use generating function, which you actually don't need. |
30 | Function and Function | 2018 ICPC Qingdao | 1000 | implementation | |
29 | Infinite Parenthesis Sequence | 2018 ICPC Qingdao Online | 2800 | binary search, dp | The standard solution is a very tedious $$$\mathcal{O}(n)$$$ solution, which I already forgot. The current tutorial uses jiangly's $$$\mathcal{O}(n\log n)$$$ method. |
28 | Red Black Tree | 2018 ICPC Qingdao Online | 2300 | trees, greedy, enumeration | |
27 | Traveling on the Axis | 2018 ICPC Qingdao Online | 1400 | enumeration, prefix sums | |
26 | Halting Problem | 2018 ICPC Qingdao Online | 1400 | bfs | |
25 | Virtual Singers | 2018 ZOJ June Monthly | 2800 | greedy | Idea from a UTAU song. The standard solution uses some data structures, Claris has a better greedy algorithm |
24 | How Many Palindromes | 2018 ZOJ June Monthly | 2200 | dp | |
23 | Peer Review | 2018 ZOJ June Monthly | 800 | greedy | |
22 | Game on a Tree | 2018 Zhejiang Provincial | 2500 | trees, dp | I came up with this idea when playing some interactive fiction game. However this problem coincides with another problem, with a larger constraint. |
21 | Sequence Swapping | 2018 Zhejiang Provincial | 1600 | DP | |
20 | Doki Doki Literature Club | 2018 Zhejiang Provincial | 1100 | strings, sorting | Idea from the game Doki Doki Literature Club!. |
19 | Lucky 7 | 2018 Zhejiang Provincial | 800 | enumeration | |
18 | Peak | 2018 Zhejiang Provincial | 800 | implementation | |
17 | Boolean Expression | 2018 ZJU School Contest | 2200 | expression parsing, dp | Due to the 8M stack size limit during the contest, this problem becomes a bit harder. |
16 | Traffic Light | 2018 ZJU School Contest | 1300 | bfs | |
15 | Mergeable Stack | 2018 ZJU School Contest | 1300 | linked lists | |
14 | PPAP | 2018 ZJU School Contest | 800 | implementation | Idea from the pop song PPAP and a meme complaining that the network in our university is bad. |
13 | Prime Set | 2017 CCPC Qinhuangdao | 2300 | bipartite matching | |
12 | Balloon Robot | 2017 CCPC Qinhuangdao | 1700 | enumeration | |
11 | String of CCPC | 2017 CCPC Qinhuangdao | 1200 | enumeration | |
10 | One-Dimensional Maze | 2017 CCPC Qinhuangdao | 800 | enumeration | |
9 | Card Game | 2017 Zhejiang Provincial | 2600 | convex-hull trick | Super boring, super standard dynamic convex-hull trick problem. |
8 | Binary Tree Restoring | 2017 Zhejiang Provincial | 2100 | trees, dfs, constructive | |
7 | Yet Another Game of Stones | 2017 Zhejiang Provincial | 2200 | asymmetric games | |
6 | Let's Chat | 2017 Zhejiang Provincial | 1200 | implementation, sorting | |
5 | Cooking Competition | 2017 Zhejiang Provincial | 800 | implementation | Idea from the anime Miss Kobayashi's Dragon Maid. |
4 | Fibonacci Sequence Chicken Edition | 2017 ZJU School Contest | 2200 | constructive | Calculate Fibonacci sequence with Chicken language. |
3 | Edge to the Root | 2017 ZJU School Contest | 2100 | trees, dfs | |
2 | How Many Nines | 2017 ZJU School Contest | 1200 | implementation, prefix sums | |
1 | Marjar Cola | 2017 ZJU School Contest | 1000 | implementation | My very first problem. |