Author of the problem [problem:2031C] here, hope you enjoyed the contest yesterday!↵
↵
Looking at the votes on [the editorial](https://codeforces.net/blog/entry/136260), it's obvious that it's a very polarizing problem: an hour or so after the contest, the problem had roughly equal numbers of "likes" and "dislikes", and now (as of writing) there are around 320 likes to 200 dislikes. Of course, this is completely predictable: the opinions on this problem were quite polarized for a few reasons:↵
↵
1. Troll and WA trap: it's **very** easy to fall into the trap of thinking that there is no solution for all odd $n$; thus, **over 12,900** (!) WA on pretest 2 solutions were received, as compared to only 4,700ish Accepted solutions. This ratio seems a bit extreme for a problem C; in the previous Div.2's problem C ([problem:2028C]), there were 3,500ish Rejected solutions to 2,500ish Accepted ones. ↵
2. The construction: hard-coding the case $n=27$ seems weird and mundane, and with such a "big" base case, it may be annoying (and ugly) to figure out. Some testers said they were "disappointed" by the solution. ↵
3. In general, constructive math problems are going to attract two-sided opinions: people who solve it would love it and find it cute, people who don't solve it would be upset. This is especially true for a problem C, as most people can solve A, B and few people can solve E, F, and thus C and D are the biggest "choke points".↵
↵
With these negative opinions, including during testing, why was this problem still adopted?↵
↵
1. There was no compelling reason to do so; a good number of testers liked it, and in general it received decent reviews across the community.↵
2. There was no good alternative problem, especially as the problemset had already been changed once (see the editorial).↵
3. I think a round with only conventional problems would be boring, and had always enjoyed constructive problems, and of course would love to share the problem with everyone of you!↵
↵
This problem reminds me of another "troll", controversial C: **IMO 2024 C4, adopted as [Problem 5 on the contest](https://artofproblemsolving.com/wiki/index.php/2024_IMO_Problems/Problem_5)**, otherwise known as the infamous Turbo problem. Without spoiling too much, there are some funny similarities:↵
↵
1. Both are constructives; the IMO problem could quite reasonably be translated to a ~2500 rated interactive problem on Codeforces.↵
2. Both have quite unexpected solutions that many people do not expect, which contributes to its troll-ness. Once again, no spoiling the solution here!↵
3. Both were proposed by a Hongkonger!↵
4. Both received very polarized opinions. During the IMO, many participants, especially from stronger teams, resented it; many relatively strong teams scored poorly on it compared to a typical problem 5. I remember reading on AOPS all the negative comments regarding this problem; this is to be expected, given that some people may have trained for an entire year, risen above their peers, only to be hit with such a problem 5 and lose out on a good score and a medal?↵
↵
But this is a core part of the competition process; you're gonna get trolled.↵
↵
<spoiler summary="Me, my team and Problem 5">↵
I was part of the Hong Kong team at IMO 2024, and after Day 2 when we heard that the proposer was none other than our former teammate, we did the most Hong Kong thing ever: curse at the problemsetter, who was our teammate just a year ago, of course! Funnily, I was not a victim of P5, as during the contest I simply decided to skip P5 in favor of P6...↵
</spoiler>↵
↵
What makes the comparison between the two problems even funnier is that they are "opposites" in some way:↵
1. The IMO problem was tricky in that its solution was simpler than expected, while this problem was more complicated than expected, with the $n\ge 27$ case coming as a "surprise";↵
2. On the IMO, teams from stronger countries tended to hate the problem more, while here on Codeforces, our C seems more popular among the unrated contestants than the rated ones.↵
↵
During problemsetting, I immediately associated this problem with Turbo, and felt that this would be an immensely fun and funny problem; this is the biggest reason for keeping it. And I hope you all had fun being trolled!↵
↵
### some challenges?↵
A comment yesterday triggered my thoughts on variants of the problem. One of which is as follows.↵
↵
#### Squares except 1↵
↵
If $1$ is **not** allowed as a valid distance, what would the constructions be? For which $n$ is the problem no longer possible?↵
↵
<spoiler summary="Solution"> ↵
This is possible for all even $n\ge 8$ and all odd $n\ge 27$. To see this, note that evidently $n=2,4,6$ cannot work. For $n=8$, the construction $1~2~3~4~1~2~3~4$ works. For larger even $n$, we need to use distances of $9$: $n=10$ requires pairs $1-10$, $n=14$ requires the pair $3-12$, and $n=12$ requires both aforementioned pairs, after which the remaining elements can be covered by pairs of distance $4$. ↵
↵
For the odd case, my construction for $n=27$ in the editorial automatically lends itself to a construction in this case, using the constructions for $n=8$ and $n=14$:↵
↵
$1~[\text{case for }8]~1~2~[\text{case for }14]~1~2$↵
↵
For $n=29, 31, 33$, we use more pairs of distance $16$:↵
↵
$1~[\text{case for }8]~1~2\ldots(n-25)~[\text{case for }(41-n)]~1~2\ldots(n-25)$↵
↵
With this, the problem is solved for all odd $n\ge 27$ by iteratively appending cases for $n=8$.↵
</spoiler>↵
↵
#### Minimum number of flavors needed↵
In the original problem, we did not limit the number of flavors. What if we want to minimize the number of flavors $F(n)$ chosen? Specifically, how well can we bound the growth of $F(n)$?↵
↵
We introduce the shorthand $C_x(k)$ to mean the construction for the case $n=k$ using the method in level $x$, with $x=0$ being the base level (i.e. the original solution).↵
The trivial estimate is $F(n)\le \frac{n}{2}$, based on our existing solutions. ↵
↵
Think about the problem for a bit!↵
↵
<spoiler summary="Improvements">↵
↵
<spoiler summary="Level 1. F(n)<13n/27+O(1)">↵
Repeat $C_0(27)$ for as long as possible until the remainder is short enough. More specifically, combine $\floor\left(\frac{n}{27}-1\right)$ copies of $C_0(27) to $C_0(n%27+27)$.↵
</spoiler>↵
↵
<spoiler summary="Level 2. F(n)<0.34n+O(1)">↵
In the above, we used repeating units of size $27$. Here, we use repeating units of size $200$. ↵
↵
First, cover a region of size $50$, except for positions $9$ and $42$, using $9-16-25$ triplets: $1\ldots 8~X~1\ldots 16~1\ldots 16~X~9\ldots 16$. Then assemble $4$ of these regions, and pair up the gaps as follows: $9-109,42-142,59-159,92-192$. This uses $68$ colors.↵
↵
Covering the array of length $n$ with such units of size $200$ produces the desired bound. ↵
↵
This concept of "stacking" regions of $50$ to give a region of $200$, for which we will fill up the gaps for, is important for later. ↵
</spoiler>↵
↵
<spoiler summary="Level 3. F(n)<n/3+o(n)">↵
We refer to **[IMO 2001 C4](https://artofproblemsolving.com/wiki/index.php/2001_IMO_Shortlist_Problems/C4) (link contains solution)**. The problem statement is as follows:↵
↵
A triplet of nonnegative integers $\{x,y,z\}$ (with $x<y<z$) is *historic* if $\{y-x,z-y\}=\{1776,2001\}$. Prove that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets. ↵
↵
The solution does not rely on properties of $1776$ and $2001$ other than the fact that they are distinct. Thus, replace $1776$ by $9$ and $2001$ by $16$, and "nonnegative" by "positive" by shifting by $1$, and we obtain a coloring of the infinite array using triplets.↵
↵
We cut off the array at $n$, and almost all integers are covered by a triplet within the range $1$ to $n$. However, if $k>n-25$, it is possible that $k$ is covered by a triplet that "overflows". If colors were allowed to be used once only, this problem would have been solved, and we would have $F(n)\le \frac{n-25}{3}+25<\frac{n}{3}+17$. ↵
↵
However, the "gaps" must be filled, and we don't know where they are. Thus, similar to level $2$, we take $n=m^2$, and fill in the remaining gaps with pairs with distance $m^2$. Thus, this gives for $n=2m^2$, $F(n)\le 2\cdot\frac{m^2-25}{3}+25<\frac{n}{3}+9$.↵
↵
For general $n$, let $m$ be the greatest integer such that $n-27\ge 2m^2$. Then we can cover the array of length $n$ with the above construction for $2m^2$, and an additional $C(n-2m^2)$. Note that $n-2m^2=O(\sqrt{n})$. Thus, the expression is $F(n)\le \frac{2m^2}{3}+9+O(\sqrt{n})=\frac{n}{3}+O(\sqrt{n})$.↵
</spoiler>↵
↵
<spoiler summary="Level 4: F(n)<n/3+C">↵
We need to get rid of the $O(\sqrt{n})$ error; however, trying to simply cover the remaining region with iteratively smaller squares cannot yield a constant number of squares, and would yield a complexity of $O(\log\log n)$.↵
↵
Instead, we use Lagrange's four-square theorem: any integer $k$ is the sum of four squares, $k=a^2+b^2+c^2+d^2$. Then let $x$ be $27$ if $n$ is odd, and $0$ if $n$ is even. Write $n=2k+x=2a^2+2b^2+2c^2+2d^2+x$. Appending $C_3(2a^2)$ to $C_3(2d^2)$ as well as $C_0(x)$, we can cover the array in no more than $\frac{2a^2}{3}+\frac{2b^2}{3}+\frac{2c^2}{3}+\frac{2d^2}{3}+36+13\le \frac{n}{3}+49$ colors. Thus, $C=50$ suffices.↵
</spoiler>↵
↵
<spoiler summary="Level 5: F(n)<cn+O(1), c<1/3">↵
It turns out that there can be quadruplets with the same color: let $(a,b,c)=(153^2,104^2,672^2)$, then $a^2+b^2=185^2$ and $b^2+c^2=680^2$, while $a^2+b^2+c^2=697^2<490000$. Let $C=490000$ and $n=CM=700^2M$. Thus, start with an array of length $C$. Fill in the elements $1,1+a^2,1+a^2+b^2,1+a^2+b^2+c^2$ with the same color, leaving $C-4$ "gaps". We arrange $M$ arrays in a row, considering each residue class mod $C$, except $1,1+a^2,1+a^2+b^2,1+a^2+b^2+c^2$, and fill in the other residue classes using $C_4(M)$ expanded by a factor of $C=700^2$.↵
↵
This gives, for $n=CM$, $F(n)\le (C-4)F(M)+M<(C-4)\left(\frac{n/C}{3}+50\right)+\frac{n}{C}<\frac{(C-1)n}{3C}+50C$. For general $n$, add an extra $F(C+27)<C$ to give $F(n)<\frac{(C-1)n}{3C}+51C$.↵
</spoiler>↵
↵
↵
<spoiler summary="Level 6: F(n)<n/4+o(n)">↵
We use the construction above but add on multiple "layers". For some $k$, let $n=C^kM$, and start with an array of length $C^k$, and for each $x$ consider the base $C$ expansion of $x$: $x=c_1c_2\ldots c_k$, where $c_i$ are allowed to be $0$. Then if $i$ is the least index such that $c_i\in\{0,a^2,a^2+b^2,a^2+b^2+c^2\}$, then $x$ is in the quadruplet with the three integers resulting from replacing $c_i$ with the other $3$ elements of the set $\{0,a^2,a^2+b^2,a^2+b^2+c^2\}$. This leaves $(C-4)^k$ gaps, which are filled in similar to Level $5$. Then we have $F(C^kM)\le (C-4)^kF(M)+\frac{C^k-(C-4)^k}{4}\cdot M<\left(\frac{C^k}{4}+↵
\frac{(C-4)^k}{12}\right)M+50C^k$. In other words, for general $n$, we have $F(n)<\left(\frac{1}{4}+\frac{1}{12}\left(1-\frac{4}{C}\right)^k\right)n+51C^k$.↵
↵
For $n>C^4$, choose $k$ such that $C^{2k}\le n\le C^{3k}$. Let $1-\frac{4}{C}=C^{-3\epsilon}$. Then we get $F(n)<\frac{n}{4}+\frac{1}{12}C^{-3\epsilon k}n+51C^k\le\frac{n}{4}+\frac{1}{12}(C^{3k})^{-\epsilon}n+O(\sqrt{n})<\frac{n}{4}+O(n^{1-\epsilon})$, thus we are done.↵
</spoiler>↵
↵
This is the best I can get to. If there's someone willing to try it, see if you can provide an answer to these questions:↵
↵
<div>283883dc96308e212590c9dbbf4cdaea</div>↵
↵
</spoiler>↵
↵
↵
Looking at the votes on [the editorial](https://codeforces.net/blog/entry/136260), it's obvious that it's a very polarizing problem: an hour or so after the contest, the problem had roughly equal numbers of "likes" and "dislikes", and now (as of writing) there are around 320 likes to 200 dislikes. Of course, this is completely predictable: the opinions on this problem were quite polarized for a few reasons:↵
↵
1. Troll and WA trap: it's **very** easy to fall into the trap of thinking that there is no solution for all odd $n$; thus, **over 12,900** (!) WA on pretest 2 solutions were received, as compared to only 4,700ish Accepted solutions. This ratio seems a bit extreme for a problem C; in the previous Div.2's problem C ([problem:2028C]), there were 3,500ish Rejected solutions to 2,500ish Accepted ones. ↵
2. The construction: hard-coding the case $n=27$ seems weird and mundane, and with such a "big" base case, it may be annoying (and ugly) to figure out. Some testers said they were "disappointed" by the solution. ↵
3. In general, constructive math problems are going to attract two-sided opinions: people who solve it would love it and find it cute, people who don't solve it would be upset. This is especially true for a problem C, as most people can solve A, B and few people can solve E, F, and thus C and D are the biggest "choke points".↵
↵
With these negative opinions, including during testing, why was this problem still adopted?↵
↵
1. There was no compelling reason to do so; a good number of testers liked it, and in general it received decent reviews across the community.↵
2. There was no good alternative problem, especially as the problemset had already been changed once (see the editorial).↵
3. I think a round with only conventional problems would be boring, and had always enjoyed constructive problems, and of course would love to share the problem with everyone of you!↵
↵
This problem reminds me of another "troll", controversial C: **IMO 2024 C4, adopted as [Problem 5 on the contest](https://artofproblemsolving.com/wiki/index.php/2024_IMO_Problems/Problem_5)**, otherwise known as the infamous Turbo problem. Without spoiling too much, there are some funny similarities:↵
↵
1. Both are constructives; the IMO problem could quite reasonably be translated to a ~2500 rated interactive problem on Codeforces.↵
2. Both have quite unexpected solutions that many people do not expect, which contributes to its troll-ness. Once again, no spoiling the solution here!↵
3. Both were proposed by a Hongkonger!↵
4. Both received very polarized opinions. During the IMO, many participants, especially from stronger teams, resented it; many relatively strong teams scored poorly on it compared to a typical problem 5. I remember reading on AOPS all the negative comments regarding this problem; this is to be expected, given that some people may have trained for an entire year, risen above their peers, only to be hit with such a problem 5 and lose out on a good score and a medal?↵
↵
But this is a core part of the competition process; you're gonna get trolled.↵
↵
<spoiler summary="Me, my team and Problem 5">↵
I was part of the Hong Kong team at IMO 2024, and after Day 2 when we heard that the proposer was none other than our former teammate, we did the most Hong Kong thing ever: curse at the problemsetter, who was our teammate just a year ago, of course! Funnily, I was not a victim of P5, as during the contest I simply decided to skip P5 in favor of P6...↵
</spoiler>↵
↵
What makes the comparison between the two problems even funnier is that they are "opposites" in some way:↵
1. The IMO problem was tricky in that its solution was simpler than expected, while this problem was more complicated than expected, with the $n\ge 27$ case coming as a "surprise";↵
2. On the IMO, teams from stronger countries tended to hate the problem more, while here on Codeforces, our C seems more popular among the unrated contestants than the rated ones.↵
↵
During problemsetting, I immediately associated this problem with Turbo, and felt that this would be an immensely fun and funny problem; this is the biggest reason for keeping it. And I hope you all had fun being trolled!↵
↵
### some challenges?↵
A comment yesterday triggered my thoughts on variants of the problem. One of which is as follows.↵
↵
#### Squares except 1↵
↵
If $1$ is **not** allowed as a valid distance, what would the constructions be? For which $n$ is the problem no longer possible?↵
↵
<spoiler summary="Solution"> ↵
This is possible for all even $n\ge 8$ and all odd $n\ge 27$. To see this, note that evidently $n=2,4,6$ cannot work. For $n=8$, the construction $1~2~3~4~1~2~3~4$ works. For larger even $n$, we need to use distances of $9$: $n=10$ requires pairs $1-10$, $n=14$ requires the pair $3-12$, and $n=12$ requires both aforementioned pairs, after which the remaining elements can be covered by pairs of distance $4$. ↵
↵
For the odd case, my construction for $n=27$ in the editorial automatically lends itself to a construction in this case, using the constructions for $n=8$ and $n=14$:↵
↵
$1~[\text{case for }8]~1~2~[\text{case for }14]~1~2$↵
↵
For $n=29, 31, 33$, we use more pairs of distance $16$:↵
↵
$1~[\text{case for }8]~1~2\ldots(n-25)~[\text{case for }(41-n)]~1~2\ldots(n-25)$↵
↵
With this, the problem is solved for all odd $n\ge 27$ by iteratively appending cases for $n=8$.↵
</spoiler>↵
↵
#### Minimum number of flavors needed↵
In the original problem, we did not limit the number of flavors. What if we want to minimize the number of flavors $F(n)$ chosen? Specifically, how well can we bound the growth of $F(n)$?↵
↵
We introduce the shorthand $C_x(k)$ to mean the construction for the case $n=k$ using the method in level $x$, with $x=0$ being the base level (i.e. the original solution).↵
The trivial estimate is $F(n)\le \frac{n}{2}$, based on our existing solutions. ↵
↵
Think about the problem for a bit!↵
↵
<spoiler summary="Improvements">↵
↵
<spoiler summary="Level 1. F(n)<13n/27+O(1)">↵
Repeat $C_0(27)$ for as long as possible until the remainder is short enough. More specifically, combine $\floor\left(\frac{n}{27}-1\right)$ copies of $C_0(27) to $C_0(n%27+27)$.↵
</spoiler>↵
↵
<spoiler summary="Level 2. F(n)<0.34n+O(1)">↵
In the above, we used repeating units of size $27$. Here, we use repeating units of size $200$. ↵
↵
First, cover a region of size $50$, except for positions $9$ and $42$, using $9-16-25$ triplets: $1\ldots 8~X~1\ldots 16~1\ldots 16~X~9\ldots 16$. Then assemble $4$ of these regions, and pair up the gaps as follows: $9-109,42-142,59-159,92-192$. This uses $68$ colors.↵
↵
Covering the array of length $n$ with such units of size $200$ produces the desired bound. ↵
↵
This concept of "stacking" regions of $50$ to give a region of $200$, for which we will fill up the gaps for, is important for later. ↵
</spoiler>↵
↵
<spoiler summary="Level 3. F(n)<n/3+o(n)">↵
We refer to **[IMO 2001 C4](https://artofproblemsolving.com/wiki/index.php/2001_IMO_Shortlist_Problems/C4) (link contains solution)**. The problem statement is as follows:↵
↵
A triplet of nonnegative integers $\{x,y,z\}$ (with $x<y<z$) is *historic* if $\{y-x,z-y\}=\{1776,2001\}$. Prove that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets. ↵
↵
The solution does not rely on properties of $1776$ and $2001$ other than the fact that they are distinct. Thus, replace $1776$ by $9$ and $2001$ by $16$, and "nonnegative" by "positive" by shifting by $1$, and we obtain a coloring of the infinite array using triplets.↵
↵
We cut off the array at $n$, and almost all integers are covered by a triplet within the range $1$ to $n$. However, if $k>n-25$, it is possible that $k$ is covered by a triplet that "overflows". If colors were allowed to be used once only, this problem would have been solved, and we would have $F(n)\le \frac{n-25}{3}+25<\frac{n}{3}+17$. ↵
↵
However, the "gaps" must be filled, and we don't know where they are. Thus, similar to level $2$, we take $n=m^2$, and fill in the remaining gaps with pairs with distance $m^2$. Thus, this gives for $n=2m^2$, $F(n)\le 2\cdot\frac{m^2-25}{3}+25<\frac{n}{3}+9$.↵
↵
For general $n$, let $m$ be the greatest integer such that $n-27\ge 2m^2$. Then we can cover the array of length $n$ with the above construction for $2m^2$, and an additional $C(n-2m^2)$. Note that $n-2m^2=O(\sqrt{n})$. Thus, the expression is $F(n)\le \frac{2m^2}{3}+9+O(\sqrt{n})=\frac{n}{3}+O(\sqrt{n})$.↵
</spoiler>↵
↵
<spoiler summary="Level 4: F(n)<n/3+C">↵
We need to get rid of the $O(\sqrt{n})$ error; however, trying to simply cover the remaining region with iteratively smaller squares cannot yield a constant number of squares, and would yield a complexity of $O(\log\log n)$.↵
↵
Instead, we use Lagrange's four-square theorem: any integer $k$ is the sum of four squares, $k=a^2+b^2+c^2+d^2$. Then let $x$ be $27$ if $n$ is odd, and $0$ if $n$ is even. Write $n=2k+x=2a^2+2b^2+2c^2+2d^2+x$. Appending $C_3(2a^2)$ to $C_3(2d^2)$ as well as $C_0(x)$, we can cover the array in no more than $\frac{2a^2}{3}+\frac{2b^2}{3}+\frac{2c^2}{3}+\frac{2d^2}{3}+36+13\le \frac{n}{3}+49$ colors. Thus, $C=50$ suffices.↵
</spoiler>↵
↵
<spoiler summary="Level 5: F(n)<cn+O(1), c<1/3">↵
It turns out that there can be quadruplets with the same color: let $(a,b,c)=(153^2,104^2,672^2)$, then $a^2+b^2=185^2$ and $b^2+c^2=680^2$, while $a^2+b^2+c^2=697^2<490000$. Let $C=490000$ and $n=CM=700^2M$. Thus, start with an array of length $C$. Fill in the elements $1,1+a^2,1+a^2+b^2,1+a^2+b^2+c^2$ with the same color, leaving $C-4$ "gaps". We arrange $M$ arrays in a row, considering each residue class mod $C$, except $1,1+a^2,1+a^2+b^2,1+a^2+b^2+c^2$, and fill in the other residue classes using $C_4(M)$ expanded by a factor of $C=700^2$.↵
↵
This gives, for $n=CM$, $F(n)\le (C-4)F(M)+M<(C-4)\left(\frac{n/C}{3}+50\right)+\frac{n}{C}<\frac{(C-1)n}{3C}+50C$. For general $n$, add an extra $F(C+27)<C$ to give $F(n)<\frac{(C-1)n}{3C}+51C$.↵
</spoiler>↵
↵
↵
<spoiler summary="Level 6: F(n)<n/4+o(n)">↵
We use the construction above but add on multiple "layers". For some $k$, let $n=C^kM$, and start with an array of length $C^k$, and for each $x$ consider the base $C$ expansion of $x$: $x=c_1c_2\ldots c_k$, where $c_i$ are allowed to be $0$. Then if $i$ is the least index such that $c_i\in\{0,a^2,a^2+b^2,a^2+b^2+c^2\}$, then $x$ is in the quadruplet with the three integers resulting from replacing $c_i$ with the other $3$ elements of the set $\{0,a^2,a^2+b^2,a^2+b^2+c^2\}$. This leaves $(C-4)^k$ gaps, which are filled in similar to Level $5$. Then we have $F(C^kM)\le (C-4)^kF(M)+\frac{C^k-(C-4)^k}{4}\cdot M<\left(\frac{C^k}{4}+↵
\frac{(C-4)^k}{12}\right)M+50C^k$. In other words, for general $n$, we have $F(n)<\left(\frac{1}{4}+\frac{1}{12}\left(1-\frac{4}{C}\right)^k\right)n+51C^k$.↵
↵
For $n>C^4$, choose $k$ such that $C^{2k}\le n\le C^{3k}$. Let $1-\frac{4}{C}=C^{-3\epsilon}$. Then we get $F(n)<\frac{n}{4}+\frac{1}{12}C^{-3\epsilon k}n+51C^k\le\frac{n}{4}+\frac{1}{12}(C^{3k})^{-\epsilon}n+O(\sqrt{n})<\frac{n}{4}+O(n^{1-\epsilon})$, thus we are done.↵
</spoiler>↵
↵
This is the best I can get to. If there's someone willing to try it, see if you can provide an answer to these questions:↵
↵
<div>283883dc96308e212590c9dbbf4cdaea</div>↵
↵
</spoiler>↵
↵
