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.
| # | Problem | Contest | Rating (Est.) | Tags | Comments |
|---|---|---|---|---|---|
| 125 | Bingo | 2024 ICPC Nanjing | 2500 | conbinatorics | 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 | 二分，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 stating 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. |
