Since competitive programming is dying, and I'm almost retired, so it's time to review the problems I authored.
Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs, by antontrygubO_o, by adamant and by tibinyte. This is not a super-comprehensive list. I set many shit problems that I don't want to share for some local contests.
It can be long, and I'm not sure if I have finished half of them yet.
The number of asterisks after the label indicates the recommendation levels. One asterisk means this problem is worth reading. Two asterisks mean this problem is one of my favorite problems, Three asterisks mean this problem is one of my best problems.
| # | Date | Problem | Contest | Comment |
|---|---|---|---|---|
| -1 | ??? 2009 | Given a sequence $$$a_i$$$, you need to split them into $$$k$$$ parts and minimize the maximum absolute difference of each part. | One of the problems I set in a training contest when I was in 7th grade, which is the first contest I made as far as I can remember. It's a textbook binary search problem. I can't tell if it's made by myself or just copied from elsewhere, but it doesn't really matter. | |
| -0.75 | August 2013 | Given a sequence, answer the query "how many numbers appear at least $$$k$$$ times in a range". | Mock Contest for NOIp in school | I don't remember whether problems are made by me or copied from elsewhere. If it's not made by me, I will say sorry to the author. I don't know why I wrote such a textbook Mo algorithm problem in the contest, and for the first problem. |
| -0.5 | August 2013 | Given a complete bipartite graph with $$$k(k \leq 20)$$$ edges removed. Every edge has a weight. Find the number of perfect matchings, and the sum of the weights of perfect matchings. Weights of perfect matchings are the sum of the weight of edges here. | Mock Contest for NOIp in school | An easy PIE problem. It should be an easy version for a Codeforces problem (problem 18 in the list) later. |
| -0.25 | August 2013 | Given a $$$n \times m (n, m\leq 700, 2|nm)$$$ binary matrix. You can choose a cell $$$(i, j)$$$, and flip all the cells in the same row or column. Find the minimum number of operations and the lexicographically smallest solution. | Mock Contest for NOIp in school | Not a bad problem in my opinion. |
| 0* | May 2014 | Triangle inscribed in ellipse | Project Euler | It's very recommended to click the link, and see wtf the problem is. It's a modern abstract art masterpiece of shit problems. However, to be honest, the intended solution is interesting. |
| 1 | August 2014 | 2048 | Yuhao Du Contest 1(aka 2014 Multi-University Training Contest 8) | Yuhao Du Contest 12346 do exist. It's the first ICPC contest I wrote. I remember I set the TL too tight for some problems and the statements for some problems are not very good. And it may be a common problem for many new problem-setters without the guidance of veterans. However, I am satisfied with the quality of the problems even from today's perspective. It doesn't contain many fancy problems, but it's very balanced and has moderate difficulty. |
| 2 | August 2014 | Area of Mushroom | Yuhao Du Contest 1 | |
| 3 | August 2014 | GCD Array | Yuhao Du Contest 1 | A good combination of number theory tricks and data structure tricks. I didn't see this kind of problem before. |
| 4 | August 2014 | Kingdom | Yuhao Du Contest 1 | |
| 5* | August 2014 | Light | Yuhao Du Contest 1 | My favorite problems in the set. It is not very difficult. |
| 6 | August 2014 | Monster | Yuhao Du Contest 1 | |
| 7 | August 2014 | Multiplication table | Yuhao Du Contest 1 | A fun easy problem. |
| 8 | August 2014 | Number Transformation | Yuhao Du Contest 1 | A fun easy problem. |
| 9 | August 2014 | Periodic Binary String | Yuhao Du Contest 1 | The hardest problem in the set. But I feel it's not too interesting. |
| 10 | August 2014 | Permanent | Yuhao Du Contest 1 | |
| 11 | August 2014 | Tree | Yuhao Du Contest 1 | |
| 11.5 | August 2014 | Find the number of pairs $$$(a, b)$$$ such that $$$a \bmod b = b \textrm{ div } a$$$, for $$$1\leq a, b\leq n(n\leq 10^{12})$$$ | Mock Contest for NOIp in school | A fun easy problem. |
| 12 | September 2014 | I Wanna Be the Guy | Codeforces Round #268 | My first and only single author Codeforces Round. Some ideas may come from preparing for the ICPC contest. I don't want to make the contest so hard deliberately, but the competitors frustrated me, sad. |
| 13 | September 2014 | Chat Online | Codeforces Round #268 | |
| 14 | September 2014 | 24 Game | Codeforces Round #268 | |
| 15 | September 2014 | Two Sets | Codeforces Round #268 | A fun easy problem. And I deliberately make the pretest very weak. I missed the old days when the hacking strategy is also a part of the contest. |
| 16* | September 2014 | Hack it! | Codeforces Round #268 | It has an unexpected beautiful solution that came up by the contestant during the contest. I think it is worth reading this beautiful solution. |
| 17 | September 2014 | Tree | Codeforces Round #268 | Is it that hard? :clown_face::clown_face::clown_face: |
| 18* | September 2014 | Permanent | Codeforces Round #268 | I also developed a technique that you can use a heuristic algorithm to find a good order to do state-compressed dp. It's not included in the tutorial of the contest but somehow spread secretly:thinking:. |
| $$$\frac{55}{3}$$$* | February 2015 | Given a permutation with $$$n (n\leq 10^5)$$$ elements, find $$$\sum P_i P_j P_k$$$ for triples $$$(i, j, k)$$$ where $$$(i, j) = (j, k) = (k, i) = 1$$$ | Mock Contest for Winter Camp | I developed a new trick to count coprime triples and wrote this problem. |
| $$$\frac{56}{3}$$$ | March 2015 | Find the $$$k$$$-th lexicographically largest [autocorrelations](https://en.wikipedia.org/wiki/Autocorrelation_(words)) with length $$$n$$$ $$$(n\leq 200, 1\leq k\leq 10^{18})$$$. | Mock Contest for ZJOI | I learned a powerful way to write shit problems — reading papers. |
| 19 | April 2015 | Product | Thesis of Chinese national training team | The problem itself is shit. I feel I didn't have good ideas in time so submitted this problem. But I developed a trick that does PIE on the symmetry group, which I think is fun. |
| 19.5 | June 2015 | Let $$$S$$$ be a string consisting of ab?, $$$f(S)$$$ be the number of different autocorrelations I can get if I replace every ? with a or b. Find the shortest, then lexicographically smallest string $$$S$$$, such that $$$f(S) = i$$$ for $$$i = 1, 2, \dots, 2000$$$. | Mock Contest for NOI | Uh, what the hell is this? |
| 20 | August 2015 | Expression | Yuhao Du Contest 2 (aka 2015 Multi-University Training Contest 9, Ptz Summer 2015 Day 2) | It is the second Yuhao Du contest, and is also used in the Petrozavodsk training camp. In that year, I remember I reached the top 10 on Codeforces with the id TooSimple, failed on IOI, and graduated from high school. The problems are harder than the previous one. I don't know how to describe my feeling about this problem set. I became a more experienced problem setter, and the problems are also good. But I feel more problems came from the way "let me develop this trick to a problem" or "let me make a data structure problem". |
| 21 | August 2015 | Hack it! | Yuhao Du Conest 2 | |
| 22 | August 2015 | GCD Tree | Yuhao Du Conest 2 | A fun problem. |
| 23 | August 2015 | Too Simple | Yuhao Du Contest 2 | |
| 24 | August 2015 | Arithmetic Sequence | Yuhao Du Contest 2 | |
| 25 | August 2015 | Persistent Link/cut Tree | Yuhao Du Contest 2 | |
| 26 | August 2015 | Travelling Salesman Problem | Yuhao Du Contest 2 | |
| 27 | August 2015 | Goldbach's Conjecture | Yuhao Du Contest 2 | A weird problem from the paper. |
| 28* | August 2015 | Random Inversion Machine | Yuhao Du Contest 2 | The hardest problem in the set. Inspired by misreading this problem, it's way harder. A little bit technical, but not bad. |
| 29 | August 2015 | Sometimes Naive | Yuhao Du Contest 2 | |
| 30** | Sepetember 2015 | You are given an empty graph with $$$n (n\leq 100)$$$ vertices, you are randomly choosing two numbers $$$u,v$$$, add an edge between $$$u$$$ and $$$v$$$. Compute the expected step to get a connected graph. | Local Contest | One of my best problems. I didn't remember where I used this problem and didn't remember the exact time. It may be not very hard from today's perspective. |
| 31 | November 2015 | Cycle Given $$$n (1\leq n\leq 2000)$$$ numbers form a cycle, divide them into $$$k$$$ parts, and maximize gcd of the sum of each part. Output the answer for $$$k = 1...n$$$ | HihoCoder #16 | HihoCoder used to be a Chinese competitive programming platform, but died. It's an okayish easy problem. |
| 32 | November 2015 | Field Given a tree with $$$n (1\leq n\leq 10^5)$$$ vertices, find the optimal heavy light decomposition when $$$u$$$ is the root for $$$u = 1, \dots, n$$$ | HihoCoder #16 | An fun easy problem. |
| 33 | November 2015 | Group Compute the number of subgroup with size $$$k$$$ of $$$S_n$$$. $$$k\leq 5, n\leq 10^5$$$. | HihoCoder #16 | It was later improved in this problem. Compute the number of subgroups of $$$S_n$$$ isomorphic to some specific group $$$G( |G| \leq 30)$$$. |
| 34* | January 2016 | Bamboo First, we define a string $$$p$$$ can be made by $$$s$$$ and $$$t$$$ iff $$$s$$$ is the prefix of $$$p$$$, $$$t$$$ is the suffix of $$$p$$$, and $$$|s|+|t| \geq |p|$$$. A string $$$p$$$ can be made by $$$s_1, s_2, \dots, s_k$$$ iff there are strings $$$p_1,p_2,\leq, p_k$$$, such that $$$p_1=s_1$$$, $$$p_i$$$ can be made by $$$p_{i-1}$$$ and $$$s_i$$$, and $$$p_k=p$$$. You are given a string $$$S(|S| \leq 10^6)$$$. Compute how many distinct lengths $$$x$$$ not exceeding $$$l (1\leq l\leq 10^{18})$$$ such that there are string $$$t$$$ with length $$$x$$$ that can be made by several copies of string $$$S$$$. | CNOI Winter Camp 2016 (Developed by Jianhao Wang) | The first problem I wrote for the official CNOI contest. I'm one coauthor. A combination of several tricks. Maybe the most interesting step is how to optimize $$$O(n \log^2 n)$$$ into $$$O(n\log n)$$$. |
| 35** | February 2016 | Map It’s a communication task. Alice has a map with $$$n$$$ items (key, value), key is in $$$[0,2^{32})$$$, value is in $$$[0,2^{10})$$$. She needs to compress it into a binary string with length no more than $$$12500$$$ bits and send it to Bob. Bob should answer queries, he should answer the corresponding value for the key. However, for a key not in the map, he can answer anything. | UOJ Goodbye Yiwei Contest (Developed by Kaifeng Lyu) | An interesting problem, recommended. |
| 36* | March 2016 | Random Tree Generator This problem is a Petr-ish problem. You are given four random algorithms to generate trees, and try to distinguish them. | ZJOI 2016 | ZJOI is Zhejiang provincial team selection contest. It's my first time leading write an official OI contest, and most problems are made by me. I follow the strategy that one data structure problem, one counting problem, and one problem in another genre. |
| 37 | March 2016 | Tourist You are asked to find the shortest path in the grid graph. | ZJOI 2016 | A little bit surprised that no one wrote it before. |
| 38** | March 2016 | Little Star You are given a tree $$$T$$$ and a graph $$$G$$$ with $$$n(n\leq 18)$$$ vertices, compute the number of embedding of the tree into the graph. (a permutation $$$p$$$ such that $$$(u,v) \in T$$$ $$$\Rightarrow$$$ $$$(p(u), p(v)) \in G$$$) | ZJOI 2016 | It may become a classical problem now. I learned that trick from computing the number of Hamilton paths but didn't see it used anywhere else before. You may be amazed when you see this trick for the first time. |
| 39* | April 2016 | Big Forest | ZJOI 2016 | I seldom wrote data structure problems. This one is interesting. |
| 40* | April 2016 | Circuit You are given a graph and compute how many pairs of vertices can be two terminals of a series-parallel graph. | ZJOI 2016 | An orthodox and hard graph problem. I'm a fan of this kind of problem. So I like it. |
| 41*** | May 2016 | Suffix Array Compute how many distinct suffix arrays can be constructed by a string with length $$$n $$$ and an alphabet with size $$$m (n, m\leq 500)$$$, the occurrence of $$$i$$$-th character should be no more than $$$c_i$$$. | CTSC 2016 | One of my best problem. This problem is very interesting in a very natural setting. I'm very proud of this problem. |
| 42 | August 2016 | Olympic Data Structure | UOJ Round #15 (Developed by ???) | It is said this problem is authored by me, but I have no idea why:clown_face: Maybe I just provided the idea that the Ukkonen algorithm can work on the multiple order-preserved patterns matching. But I have no idea about the details, and how it really works. |
| 43 | September 2016 | Emulator Given a graph, find a graph with the minimum number of edges that preserve the distances of all pairs of vertices. | HihoCoder #23 | It also appeared in later ABC as far as I remember. |
| 44 | September 2016 | Certificate Given a boolean formula of $$$n (n\leq 14)$$$ variables, compute the certificate with the smallest size for each input. | HihoCoder #23 | It seems I was a little interested in theoretical computer science then. |
| 45 | September 2016 | Tree Given a tree, answer the queries if we remove $$$k (\sum k \leq 10^5)$$$ edges from it, what is the diameter of each part. | HihoCoder #23 | |
| 46 | September 2016 | Automorphism Compute the number of unlabelled trees with size $$$n(n\leq 50)$$$ and automorphism no more than $$$k(\leq 10^9)$$$. | HihoCoder #23 | |
| 47 | Janurary 2017 | Rikka with Number I have a pair of number $$$(0, 1)$$$. In each step, you can add one number to another. You want to reach $$$n(n\leq 10^9)$$$ in $$$60$$$ steps. | HihoCoder #26 | A fun easy problem. |
| 48 | January 2017 | Rikka with Tree IV Given a tree with $$$n(n\leq 10^5)$$$ vertices, color each vertex such that every connected subgraph with size no more than $$$k$$$ has distinct colors. What is the minimum number of colors? | HihoCoder #26 | |
| 49* | January 2017 | Rikka with Cactus Given a graph, for each edge, check if the graph is a cactus after removing it. | HihoCoder #26 | An orthodox graph problem with heavy casework. I'm a fan of this kind of problem. So I like it. |
| 50 | January 2017 | Rikka with Flow Given a cost flow network, you can reduce the cost of some edges and want to make the cost of maximum cost circular flow less than $$$c$$$. What is the minimum total amount of cost you reduce? | HihoCoder #26 | A funny problem. |
| 51 | January 2017 | Isomorphism Checker You need to construct graphs to hack some graph isomorphism checker. | UOJ Goodbye Bingshen (Developed by Kaifeng Lyu) | Thank the developer for making this problem. I think I just gave the rough ideas of this problem. The intended solution is to construct the graph for each case. But it is overkilled by a specific class of graphs :clown_face: |
| 52 | February 2017 | Chessboard You are given an undirected graph with $$$n$$$ vertices and $$$m(n, m\leq 100)$$$ edges, there are $$$n-1$$$ chess with distinct labels on $$$n-1$$$ distinct vertices, and there are one empty vertex. In each step, you can move one chess to the adjacent empty vertex. There are $$$T(T\leq 1000)$$$ queries, Given the starting and ending configuration, you should determine whether it is possible to reach the ending configuration from the starting one. | CNOI Winter Camp 2017 | I found this problem can be reduced to a computational group theory problem, and felt it may be interesting to see the application of computational group theory algorithms in the combinatorial problem. I just found this problem was well-researched and only has one or two counterexamples. And it was about two days before the contest. Then I became a clown:clown_face: |
| 52 | February 2017 | Chessboard You are given an undirected graph with $$$n$$$ vertices and $$$m(n, m\leq 100)$$$ edges, there are $$$n-1$$$ chess with distinct labels on $$$n-1$$$ distinct vertices, and there are one empty vertex. In each step, you can move one chess to the adjacent empty vertex. There are $$$T(T\leq 1000)$$$ queries, Given the starting and ending configuration, you should determine whether it is possible to reach the ending configuration from the starting one. | CNOI Winter Camp 2017 | I found this problem can be reduced to a computational group theory problem, and felt it may be interesting to see the application of computational group theory algorithms in the combinatorial problem. I just found this problem was well-researched and only has one or two counterexamples. And it was about two days before the contest. Then I became a clown:clown_face: |
| 53** | February 2017 | Random Numbers | Deep Dark Fantasy Contest (Ptz Winter 2017 Day 5) | The problems in the contest are all developed by ICPCCamp Team. Thank you for developing them. This is the only contest written by my ICPC team. ICPC is a somehow painful journey for me. And I feel a bit sorrowful when looking back to these days. I think we promised to write a contest, but we didn't have enough ideas, or it was just made in a hurry. So the contest only has 9 problems, which is unusual. I think I authored at least 5 of them. Since for some problem, I can't really tell if it was written by me, or my teammates. To the problem itself, this one is interesting. And as far as I remember, Warsaw U Eagles(?) came up with an unexpected beautiful solution. |
| 54 | February 2017 | Eulerian Orientation | Deep Dark Fantasy Contest | Not a bad problem, but also not very impressive. |
| 55* | February 2017 | Tube Master II | Deep Dark Fantasy Contest | Many teams didn't pass the IQ test. |
| 56** | February 2017 | Palindrome | Deep Dark Fantasy Contest | I noticed the palindrome prefix structure can be merged in polylog time when solving a distributed task in PA (When can we have another distributed competitive programming contest? sad). And then I wrote this problem. I think I was ahead of the academics since I wrote a mail to some authors in CPM, and they said they didn't know that. Or they didn't notice we can use this trick and segment tree to maintain the palindrome structure of a string dynamically. |
| 57 | February 2017 | Territory Game | Deep Dark Fantasy Contest | It's a game theory problem in a quite natural setting. But the solution may have some casework. I remembered my initial idea is wrong, and it was fixed by the developer team. |
| 58 | March 2017 | Polynomial | ZJOI 2017 (Developed by Ruyi Ji) | ZJOI 2017 was not led by me, so I provided this idea. It's inspired by a problem in Project Euler. Hard, but technical and annoying. |
| 59 | April 2017 | Automorphism What is the maximum number of edges can a simple undirected graph with $$$n (n\leq 10^{100})$$$ vertices can have such that the graph doesn't have a non-trivial automorphism? | BJOI 2017 | It's used in Beijing team selection contest. I wrote two of them. The setting is quite natural, not a bad problem but not very impressive. |
| 60 | April 2017 | Driving Given a fixed sequence $$$b$$$, you need to maintain a sequence $$$a (|a| \leq 50000)$$$ to support modify $$$a_i$$$, and answer $$$\min_{p} \sum|a_i - b_{p_i}|$$$ where $$$p$$$ is a permtation here. | BJOI 2017 | It's passed by brute force. Sorry, I should stop creating data structure problems. |
| 61 | May 2017 | Square How many subsets of $$$[L, R] (1\leq L \leq R \leq 10^7)$$$ that the product of numbers is a square number? | THUSC 2017 (Developed by Jiayi Weng) | A pretty standard and boring problem. THUSC happened when I was in the World Final, very sad. |
| 62* | October 2017 | Stones There are two sets $$$A$$$ and $$$B$$$ and $$$n$$$ piles of stones. Alice and Bob take turns alternatively. Alice can choose a pile with size $$$s$$$ and split it into $$$a, s-a$$$ where $$$a\in A, 1\leq a < s$$$. Bob can split it into $$$b, s-b$$$. Who can't move loses. | Someone's Mock Contest for NOIp | A fun easy problem. A good start problem for the partisan game and surreal numbers. However, you don't have any knowledge of surreal numbers here. In another word, surreal numbers in the partisan game are actually more intuitive than nimmer, it simply defines how many steps Alice can perform more than Bob. But most tutorials to surreal numbers suck. |
| 63*** | October 2017 | Lollipop You are given an $$$n\times m (n\leq 5, m\leq 10000)$$$ grid graph, there is a cost $$$c_i$$$ for each edge, there is a range $$$[l_i,r_i]$$$ for each vertex, you need to write the number $$$f_i$$$ in each vertex such that $$$l_i\leq c_i\leq r_i$$$. The value of an edge is the absolute difference between the number in two vertices times the cost itself. The value of a graph is the sum of all the edges. You need to minimize the value of the graph. | Someone's Mock Contest for NOIp | One of my best problems. This problem may look a bit standard now. From a perspective back then, most ideas were novel. I'm really proud that I can come up with these ideas to write the problem. An easier version in CGR 11 two years ago. And stop sending your best problem to others in a random private contest. |
| 64 | January 2018 | Cube There is a rectangular box. An insect inside the box wants to fly from some place to another place. This insect can only fly inside the box including the surface, and speed strictly inside the box and speed on the surface are two different constants. Find the minimum time. | Yuhao Du Contest 3 | It's a contest used in a local training camp. And it may be prepared in 24 hours. So most problems are shit. Let me share some not-so-bad problems. It's a cute geometry problem. |
| 65 | January 2018 | Permutation Given a permutation of $$$1,2,\dots, n$$$. You can split it into at most $$$k$$$ continuous parts and rearrange these parts. Find the array you can get with minimum lexicographic order. | Yuhao Du Contest 3 | It seems to be a Div 2 B problem. But it may be a bit tricky since my first two versions of the model solution are both wrong. |
| 66* | January 2018 | Tree Given a tree with $$$n$$$ nodes. Alice and Bob take turns playing, starting with Alice. At first, Alice can choose any one node in the tree and color it. Then the player chooses an uncolored node adjacent to a node colored by Alice, and colors it. Who can't move loses. | Yuhao Du Contest 3 | A fun easy problem. I'm usually bad at writing ad-hoc problems. |
| 67 | January 2018 | Patterm Matching(I will fix the format later) Given a string $$$s(|s| \leq 10^6)$$$ and code counter = 0 for i in range(0, len(s)): for j in range(0, len(t)): if s[i+j] != t[j]: break counter += 1 Count the number of string with length not exceeding $$$l$$$, which would make counter is no less than $$$k (k\leq 10^{12})$$$. | Yuhao Du Contest 3 | A problem with a natural setting, nothing special though. |
Ugh nice finally a list of the problems from Yuhao Du
What was your rating when you made your first problems?
I mean do you think low rated coders can make good problems?
Never! Problem set by low rated coders are trash!!!
cope harder
what do you mean by low rated ? CMS, experts or specialists ?(with ranks less than too for sure)
I didn't CF then, I guess it would be low if I did, like 1200.
To be honest, and it may be politically incorrect and offensive. I think low rated coders can make good problems with a lower probability. There can be exceptions, for example, problem F and H is good in tibinyte's round.
What rating can be considered as "high"? black-red or red or orange?
4000 is high.
Ok, a serious answer: The world is not binary. High or low is just a relative concept. I just want to show a statistical fact, that the quality of problems can be positively related to the rating of authors. There can be many things related to the quality of problems, for example, how much effort you pay into the problems or the guidance of the coordinator. So I don't like questions like "what rating do you think is high".
my question is a little ambiguous. i want to know What rating can be considered as "high" enough to prepare a good contest.
The quality of problems depend on many things indeed. But what i want to know is that, to prepare a good contest(school contest etc.), what rating should i have at least? I think there may be some basic requirements for a good author.
CP is dying??
I think there's a typo in problem #5 (Light) at the link you provided:
Sorry, I was illiterate then.
The link for problem 39 is wrong. It should be https://uoj.ac/problem/195.
Fixed, thx
It's so sad to read this after so much waiting for your ICPC comeback :(
why problem 52 appeared twice?
Are there editorials to the previous Yuhao Du Contests?