Hi everyone,
after Codeforces Round 889 (Div. 1), maybe it's time to collect all my problems here. For now, I've mainly invented easy-ish problems. I wish to invent a very hard problem sooner or later :)
Update after Pinely Round 3 I'm putting the story of each problem under spoiler, because it may contain parts of the solution. I invented many problems by just trying random setups until I came up with something solvable, but some problems (especially the harder ones, for example 1854D - Michael and Hotel) may have more interesting stories.
Fun facts:
- I struggled a lot to find a suitable div2A for Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round). I proposed a lot of problems that turned out to be unsuitable (for example, because they were too hard), then I used them somewhere else.
- While I was writing this blog, I realized that 1849E - Max to the Right of Min is identical to my problem preoii_allenamento - Allenamento su ChinaForces, and I could just copypaste the code. Unfortunately I realized this $$$20$$$ minutes after the start of the contest, and I couldn't get the first AC :D
- Sometimes, if you just remove parts of the statement, the problem becomes better (and sometimes harder)! For example, initially 1854D - Michael and Hotel and preoii_statue - Galleria d'arte were relatively easy problems with a slightly longer statement (e.g., in 1854D - Michael and Hotel it was guaranteed that the input had a special structure), but making the statement simpler also made these problems more interesting.
- Coming up with a good problem starting from the solution is really hard (at least for me). After failing to generate any difficult problem from the solution, I would say I fully agree with Um_nik's last pro tip.
Authored (roughly sorted by difficulty)
preoii_vm - Aggiornamento della macchina virtuale
cc PATHPAR - Path Parity
cc XORPERM - Xor Permutation
1909A - Distinct Buttons
1485A - Add and Divide
StoryFirst, I randomly came up with "given $$$a$$$, you can make $$$a := 2a$$$ or $$$a := \lfloor a/2 \rfloor$$$ any number of times, can you make $$$a = b$$$?" It was rejected because it's well-known. Then, I tried to generate a problem with the same solution.
cc SUMPRODSEG - Sum Product Segments
StoryAt some point, I wanted to make an IntervalForces div2 round, but I ended up using the problems on CodeChef because the queue for div2 was too long.
cc MXMODSUM - Maximum Pairwise Modular Sum
StoryYet another rejected problem A of Codeforces Round 778 (Div. 1 + Div. 2, основан на Финале Технокубка 2022).
The idea was "generate a problem where you have to find a pair of elements that maximizes something, and the key idea is that it's optimal to choose the maximum element". So, I was searching for some formula such that, if $$$c$$$ (one of the elements) is fixed, $$$x$$$ (the other element) should be the maximum, i.e., $$$f_c(x)$$$ is non-decreasing.
$$$f_c(x) = c+x+(c-x)\%m$$$ worked.
1855B - Longest Divisors Interval
terry 2023/3 - Dipingere i muri
StoryFirst, I proposed it on Codeforces, and it was accepted but we ended up using another problem. Then, I proposed it on CodeChef and it was rejected :D
I ended up using it for regional OI. The setup is very similar to 1329A - Dreamoon любит красить, but the solution is different.
1485B - Replace and Keep Sorted
StoryThis problem was inspired by real life. I saw someone erasing a name from a sorted list and putting his name instead, but the list became unsorted. Then, I wondered in how many ways you can keep the list sorted under certain constraints.
1928B - Equalize
cc SEGFAULT - Segmentation Fault
StoryYet another IntervalForces problem.
cc SUBARRAYLEN - Subarrays with length
Story"Count subarrays with some property" is an easy way to get decent problems.
terry 2023/4 - Viaggio intrigante
StoryThe intended solution is subquadratic (using sets, or binary search). Unfortunately, I forgot that the competition was output only with a TL of $$$10$$$ minutes (and no one seemed to notice it during testing), so $$$O(n^2)$$$ and even $$$O(n^2 \log n)$$$ passed :(
I'm sorry for making this year's regional OI ridiculously easy.
1909B - Make Almost Equal With Mod
StoryAfter proposing a lot of div2B problems which turned out to be too hard, I proposed this, suspecting it was also too hard. It turned out it wasn't.
1909C - Heavy Intervals
StoryI was thinking about how swapping the endpoints of two intervals to make them non-intersecting always makes one interval shorter (and possibly the other longer). Then I realized I could use rearrangement inequality on this setup.
cc ANTIKNAPSACK - Anti-knapsack
cc THROWTAKE - Throw and Take
ois_fibonacci - Fibonacci Sequences
StoryWhy didn't this problem exist before?
1854A2 - Dual (Hard Version)
StoryInspired by arc122_c - Calculator. The statement is nearly the same as 1746B - Восстание, but the solution is quite different.
I proposed this problem to UOI, but it wasn't used. So, I proposed it on Codeforces. The initial version had only one subtask with $$$35$$$ operations. Then we decided to make two subtasks with $$$50$$$ and $$$31$$$ operations to make the contest more balanced.
1909D - Split Plus K
StoryFirst, I proposed $$$k = 0$$$ as an easy problem for a local competition. Then, I realized $$$k = 1$$$ (and $$$a_i \geq 2$$$) makes sense and I proposed it as div2B. Then we used the version with generic $$$k$$$.
1485D - Multiples and Power Differences
StoryDuring testing we underestimated the difficulty of this problem, but it ended up to be quite tricky for many people.
1854B - Earn or Unlock
StoryI came up with this problem by playing Tanto Cuore and misunderstanding the rules. Only some time later I realized the solution can be optimized using a bitset. I was not sure about making the constraints bigger (and let only the bitset solution pass), but we decided to use this version mainly because a smaller $$$n$$$ could have spoiled that the intended solution is DP.
preoii_armadio - Evasione dall'armadio
StoryYet another standard problem, but it was used in a practice OI contest, so it doesn't matter.
UOI 2023/7 - Add Again
StoryInspired by arc122_c - Calculator. First, I found a solution with $$$1000$$$ operations, but someone told me the problem can be solved in $$$300$$$ operations :D
1485E - Move and Swap
StoryMy first problem! The solution is slightly annoying to write, and maybe the problem would have been better if we used a matrix (with vertical edges) instead of a generic tree, but the other setters and the coordinator preferred the tree version.
1485F - Copy or Prefix Sum
1909E - Multiple Lamps
StoryI proposed the problem with $$$t = 1$$$. While preparing the problem, I accidentally realized $$$t \leq 10^4$$$ makes the problem much harder.
cc NDANDANDOR - Non-decreasing AND and OR
1854C - Expected Destruction
StoryI was trying to calculate some expected values in an $$$n \times n$$$ grid with blocks. Suddenly I came up with 1854C - Ожидаемое разрушение and I realized you don't need to actually define the grid in the statement.
preoii_allenamento - Allenamento su ChinaForces
StoryYet another "count subarrays" problem. First, I came up with an $$$O(n \log n)$$$ solution. Then, a contestant found a different $$$O(n \log n)$$$ solution, and I realized it could become $$$O(n)$$$ by adding a few lines.
It's the only problem I know that uses this funny idea.
ois_aliga - A Day in Olbia
StoryThe statement was generated almost randomly, the solution is $$$O((n \log n)^{4/3})$$$.
cc PERMSEGMENTS - Permutation Segments
StoryEasy problem about Connected Components DP. Some contestants were able to invent Connected Components DP from scratch :D
1909F2 - Small Permutation Problem (Hard Version)
StoryInitially, I thought this problem was trivial and I tried to find harder variations. Later, tourist and Petr proved me wrong :D
1854D - Michael and Hotel
StoryThe story of this problem is quite weird.
First, I overkilled 1787D - Игра на оси, using the random solution from JOI 2019 — Virus Experiment. Then I tried to invent a problem with the same trick.
My initial idea was
- There are a red tree and a blue tree. So, if an ancestor of a node is red (blue), the node itself is red (blue). Let's say nodes $$$1$$$ and $$$2$$$ are the roots of the red and the blue tree, respectively.
- You want to find red nodes.
- Intended solution: random shuffle the nodes, and for each node ask its ancestors in order, until you find one whose color is already known. So, you ask $$$O(n \log n)$$$ ancestors on average.
Then, I realized that asking the same problem on functional graphs instead of trees looked much better (and had a completely different solution). The coordinator found another solution that worked on any functional graph, not necessarily with $$$2$$$ components, so it turned out that removing the first line of the statement made the problem even better.
Anyway, I still wanted to make a problem where the intended solution uses the random shuffle, basically because it required $$$\approx n (\ln n + 1)$$$ queries (on average), while the other solutions required $$$\approx n (\log_2 n - 1)$$$ queries (always). I tried a lot of modifications, including giving additional points for increasing subsequences of queries, and giving points according to the best case instead of the worst case. Unfortunately, all these variants turned out to be nonsense and / or have unintended easy solutions.
1909G - Pumping Lemma
StoryI proposed this problem for Italian team selection test with $$$n \leq 2 \cdot 10^5$$$. While preparing the problem, I realized a linear solution that seemed wrong was in fact correct, so I could raise $$$n$$$ to $$$10^7$$$.
1909I - Short Permutation Problem
StoryInspired by 1842H - Tenzing and Random Real Numbers (which is the hardest problem I solved during a Codeforces contest). The coordinator lowered the solution complexity from $$$O(n^3)$$$ to $$$O(n^2 \log n)$$$.
1909H - Parallel Swaps Sort
StoryI invented this problem (with $$$O(n \log n)$$$ operations) at 6 AM, a few hours before my algebra exam. During testing we realized you can solve the problem in $$$O(n)$$$ operations!
Partially authored (roughly sorted by difficulty)
1654A - Maximum Cake Tastiness
StoryInitially, the tastiness was defined as $$$\min( \{ |a_i - a_{i+1}| \} )$$$ and the goal was to minimize the tastiness. The coordinator suggested the current version, which is more natural and has exactly the same solution.
Fun fact: according to CLIST, 1654A - Maximum Cake Tastiness is the 9th easiest problem on Codeforces.
preoii_triplets - Comune di Alleib
StoryI proposed the problem on a general graph (but I didn't have an efficient solution). Then, my teammates realized that the problem makes sense on a tree.
Our initial solution was very overkill, but later we realized there exists a simple solution using the diameter. Fun fact: this problem and 1294F - Три пути в дереве have a different statement, but their solution is exactly the same.
1485C - Floor and Mod
StoryInitially, Codeforces Round 701 (Div. 2) didn't have this problem C. Fortunately, we decided to add it to make the contest more balanced (it turned out the old problem C has a rating of $$$2200$$$). Actually, I had proposed a slightly different statement, but the coordinator swapped some variables and made the current statement, which is better.
arc147_c - Min Diff Sum
StoryI invented this problem and donated it to a Codeforces round I tested, but in the meanwhile the same exact problem was proposed independently by other people on AtCoder, where it appeared first. Some people who tested the Codeforces round and took part in the AtCoder contest got AC just by copying my solution :D
preoii_permutazione2 - Trova la permutazione
StoryIt's basically "implement parallel binary search". The coordinator proposed the last subtask: "implement parallel square root decomposition".
preoii_sets - Insiemi nell'armadio
StoryI wanted to write a simple application of range DP. The actual solution is $$$O(n^3)$$$, but it can be made faster by using some heuristics and optimizations. Maybe this problem shouldn't exist.
oii_corridoi - Arte nei corridoi
StoryMy contribution to this problem is the last subtask. It was hard to convince organizers to use the last subtask (because "adding queries cannot make a problem better"), but contestants seemed to like it.
1762E - Tree Sum
StoryThe original version didn't include weights (you had to find the sum of $$$d(1, n)$$$ over all unweighted trees), but it could be found on OEIS. The authors tried to change the solution formula by giving different weights to even and odd subtrees, and I found out a natural way to achieve it (i.e., the current statement).
I thought this would have made the problem just slightly more difficult (I estimated rating $$$1900$$$), but it turned out to be much harder.
preoii_statue - Galleria d'arte
StoryThis is one of my favorite problems.
I initially proposed the problem with $$$M \leq \frac{N}{2}$$$ and $$$O(1)$$$ queries, and you were also given the indices of the maximum / minimum subarray. Then, my teammates made the statement more natural and the problem became much more difficult and funny.
UOI 2023/4 - Array and prefix sums
StoryI had proposed "make the elements nonnegative in $$$5$$$ moves" with different types of moves. Then, the UOI organizers made the problem impossible (now, it requires a D&C of convex hulls).
1654H - Three Minimums
StoryFirst, I proposed the problem with $$$n \leq 2000$$$ and $$$m = 0$$$, and the intended solution was Connected Components DP. Then, the coordinator made the problem impossible (now, it requires generating functions and a differential equation).