Problems that I Authored So Far

Правка en2, от TsReaper, 2024-12-22 16:06:24

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 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.
Теги problem setter, problem list

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский TsReaper 2024-12-23 05:11:19 232 Tiny change: ' | 2100 | DP | Idea fr' -> ' | 2100 | dp | Idea fr'
en9 Английский TsReaper 2024-12-22 16:40:42 227
en8 Английский TsReaper 2024-12-22 16:27:59 10
en7 Английский TsReaper 2024-12-22 16:17:33 23
en6 Английский TsReaper 2024-12-22 16:15:35 2 Tiny change: 'anjing | 2500 | combi' -> 'anjing | 2600 | combi'
en5 Английский TsReaper 2024-12-22 16:14:08 0 (published)
en4 Английский TsReaper 2024-12-22 16:13:33 98
en3 Английский TsReaper 2024-12-22 16:12:39 84 (saved to drafts)
en2 Английский TsReaper 2024-12-22 16:06:24 1033 (published)
en1 Английский TsReaper 2024-12-22 15:55:52 22987 Initial revision (saved to drafts)