Done :D

After inventing 1485A - Add and Divide and 1485B - Replace and Keep Sorted, I tried to invent "Add and Keep Sorted".

Some months later, 1667A - Make it Increasing appeared in a contest. It's basically the same problem with an extra step, and it looks much cooler than preoii_vm - Aggiornamento della macchina virtuale.

I came up with this problem while trying to find a div2A for Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round).

Yet another rejected problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round).

Basically, it's terry 2023/4 - Viaggio intrigante with $$$3$$$ distinct buttons instead of $$$2$$$. The solution turns out to be quite different.

First, 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.

At 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.

Yet another rejected problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round).

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.

It was problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) for a long time during testing, but eventually we decided to change it because it looked too hard.

I proposed it in a Turing machine competition (since the implementation is doable), but it turned out I could use it in Codeforces Round 889 (Div. 2), so I withdrew the proposal.

First, 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 Likes Coloring, but the solution is different.

This 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.

Invented the same day as 1909B - Make Almost Equal With Mod, while looking for a div2B. We didn't use it in Pinely Round 3 (Div. 1 + Div. 2), but it filled a difficulty gap in Codeforces Round 924 (Div. 2).

Yet another IntervalForces problem.

"Count subarrays with some property" is an easy way to get decent problems.

The 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.

After 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.

I 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.

Yet another proposal for problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) (rejected because too hard). In fact, its rating on CodeChef is 2566 :D

Standard but educational problem.

Challenge: solve arc155_d - Coprime Game. If you are stuck, solve cc THROWTAKE - Throw and Take and 1731E - Graph Cost first.

Why didn't this problem exist before?

Inspired by arc122_c - Calculator. The statement is nearly the same as 1746B - Rebellion, 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.

First, 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$$$.

During testing we underestimated the difficulty of this problem, but it ended up to be quite tricky for many people.

I 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.

Yet another standard problem, but it was used in a practice OI contest, so it doesn't matter.

Inspired 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

My 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.

It's one of my favorite problems, mainly because it's a "programming" problem (not a math problem) with an extremely short solution code. Inspired by 1144G - Two Merged Sequences: I gradually made changes to the statement until finding 1485F - Copy or Prefix Sum.

I proposed the problem with $$$t = 1$$$. While preparing the problem, I accidentally realized $$$t \leq 10^4$$$ makes the problem much harder.

Inspired by 1329B - Dreamoon Likes Sequences: I gradually made changes to the statement until finding cc NDANDANDOR - Non-decreasing AND and OR.

I was trying to calculate some expected values in an $$$n \times n$$$ grid with blocks. Suddenly I came up with 1854C - Expected Destruction and I realized you don't need to actually define the grid in the statement.

Yet 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.

The statement was generated almost randomly, the solution is $$$O((n \log n)^{4/3})$$$.

Easy problem about Connected Components DP. Some contestants were able to invent Connected Components DP from scratch :D

Initially, I thought this problem was trivial and I tried to find harder variations. Later, tourist and Petr proved me wrong :D

The story of this problem is quite weird.

First, I overkilled 1787D - Game on Axis, 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.

I 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$$$.

Inspired 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)$$$.

I 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!

Initially, 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.

I 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 - Three Paths on a Tree have a different statement, but their solution is exactly the same.

Initially, 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.

I 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

It's basically "implement parallel binary search". The coordinator proposed the last subtask: "implement parallel square root decomposition".

I 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.

My 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.

The 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.

This 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.

I 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).

First, 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).