↵
↵
<spoiler summary="A little backstory about the round (ACGN)">The Highschool CPers (HSCP) Discord server was created in April 2022 by [user:pwned,2024-11-14], which over time grew into a close-knit community of highschool competitive programmers. I joined in the same month of its creation, and in the next month I approached [user:pwned,2024-11-14] about the possibility of setting a contest. Thus the HSCP round concept was born.↵
↵
Over the next month or so, the initial problems were born; the current problems A and F were produced in June-July 2022. We had several problem ideas by then, enough to set a div.2 round. However, as I was going to be busy in my 5th year of high school, and may not be that responsive to coordinators, the contest was in the ownership of [user:pwned,2024-11-14], who needed to wait until he reached master in order to propose the set on Codeforces.↵
↵
However, this step took almost 1.5 years as he would stay at candidate master for 57 consecutive contests, even hitting 2099 rating. Eventually, in January 2024, [user:pwned,2024-11-15] finally reached master and submitted the round, and in May, the round began to be reviewed by our dear coordinator [user:maomao90,2024-11-14].↵
↵
It took 3 months (totally not procrastinating) to prepare all the problems, and testing commenced in August. However, the difficulty gap between problems quickly became apparent. The original problems A, C, E became the current A, D, F, and three new problems (for B, C, and E) had to be devised. Therefore, I started coming up with problems in the dead of night, hoping to finish the contest as soon as possible.↵
↵
Eventually, in October, all the gaps were filled, and thus the current problem set was born.↵
↵
Originally, I wanted to theme this round based on the game Hatsune Miku: Colorful Stage!, and in particular the current problem E was inspired by the song Hatsune Creation Myth by cosMo<wbr>@Bousou-P. [Go give it a listen!](https://www.youtube.com/watch?v=8J6SMoVd5BY)↵
↵
Ultimately, less than a week before the round, we chose to settle on a "geographical" theme, since the authors of this contest hail from different nations. We also chose Penchick, a traveling penguin chick, as the main character, but we kept a essence of the game Hatsune Miku: Colorful Stage!: Kohane (Azusawa Kohane, appearing in problem B and C) is one of the game characters, and was featured on one of my early profile pictures (before I even started playing the game). Nowadays, Kohane has been immortalized in the HSCP server as an "anime character", receiving a dedicated emoji :kohane:. ↵
</spoiler>↵
↵
[problem:2031A]↵
↵
Idea: [user:pwned,2024-11-14]<br>↵
Preparation: [user:HappyPacMan,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Consider the maximum number of pillars that can be left untouched instead.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Under what conditions can $k>1$ pillars be untouched?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Note that if pillars $i$ and $j$ with different heights are both untouched, then the first pillar must be taller than the second, which contradicts the fact that the heights must be non-decreasing after the adjustment. Thus, all unadjusted pillars must be of the same height.↵
↵
Therefore, the required number of pillars to adjust is $n-k$, where $k$ is the maximum number of pillars with the same height $h$. This bound is reachable by, for example, adjusting all pillars to height $h$.↵
↵
To find $k$, we can go through each index $i$ and find the number of pillars with the same height as $i$; this gives $O(n^2)$ time complexity, which is good enough for this problem. Alternatively, you can use a frequency array or `std::map`, or sequentially go through the list and find the longest sequence of equal terms, all of which have better time complexities.↵
↵
Implementation:<br>↵
$O(n^2)$: (by [user:ACGN,2024-11-16]) [submission:291675590]<br>↵
Frequency array: (by [user:pavement,2024-11-14]) [submission:291676291]<br>↵
Map: (by [user:newb_programmer,2024-11-14]) [submission:291676566]<br>↵
Sequential approach: (by [user:AlperenT,2024-11-14]) [submission:291676646]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:1,option1]↵
- Okay problem: [likes:1,option2]↵
- Bad problem: [likes:1,option3]↵
- Did not attempt: [likes:1,option4]↵
</spoiler>↵
↵
[problem:2031B]↵
↵
Idea: [user:ACGN,2024-11-14]<br>↵
Preparation: [user:HappyPacMan,2024-11-14]↵
↵
<spoiler summary="Hint 1">Consider which permutations you can get by reversing the operations and starting from the identity permutation</spoiler>↵
↵
↵
<spoiler summary="Hint 2">After $p_i$ and $p_{i+1}$ have been swapped, i.e. $p_i=i+1$ and $p_{i+1}=i$, neither of them can then be involved in another different swap.</spoiler>↵
↵
↵
<spoiler summary="Solution">Suppose we begin with the identity permutation. Consider what happens after swapping $p_i=i$ and $p_{i+1}=i+1$. After this swap, elements $p_1$ to $p_{i-1}$ will consist of $1$ to $i-1$, and $p_{i+2}$ to $p_n$ will consist of $i+2$ to $n$. Thus, it is impossible for $p_i=i+1$ to swap with $p_{i-1}\lt i$, or for $p_{i+1}=i$ to swap with $p_{i+2}\gt i+1$.↵
↵
Therefore, the swaps made must be independent of each other; in other words, the indices $i$ chosen in the process must differ from each other than at least $2$. These permutations satisfy the following: for each index $i$,↵
↵
- $p_i=i$, or↵
- $p_i=i+1$ and $p_{i+1}=i$, or↵
- $p_i=i-1$ and $p_{i-1}=i$.↵
↵
One way to check for this is to iterate for $i$ from $1$ to $n$. If $p_i=i$ then continue, and if $p_i=i+1$ then check if $p_{i+1}=i$, then swap $p_i$ and $p_{i+1}$. Otherwise, the permutation cannot be sorted.↵
↵
Time complexity: $O(n)$↵
↵
Implementation: (by [user:AlperenT,2024-11-13]) [submission:291676758]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:2,option1]↵
- Okay problem: [likes:2,option2]↵
- Bad problem: [likes:2,option3]↵
- Did not attempt: [likes:2,option4]↵
</spoiler>↵
↵
[problem:2031C]↵
↵
Idea & preparation: [user:ACGN,2024-11-14]↵
↵
<spoiler summary="Hint 1">Solve the problem for $n=2$ and for even $n$ in general.</spoiler>↵
↵
↵
<spoiler summary="Hint 2">For odd $n$, there exists a color that appears at least thrice. What does this mean?</spoiler>↵
↵
↵
<spoiler summary="Solution">Note that $1$ is a square number; thus, for even $n$, the construction $1~1~2~2~3~3\ldots\frac{n}{2}~\frac{n}{2}$ works. ↵
↵
For odd $n$, note that there exists a color that appears at least thrice, say at positions $x\lt y \lt z$. Then $y-x$, $z-y$ and $z-x$ are all square numbers. Note that $z-x=(z-y)+(y-x)$, which has the smallest solution being $z-x=5^2=25$, and $\{z-y,y-x\}=\{9,16\}$. Therefore, there is no solution if $n\le 25$. ↵
↵
We devise a solution for $n=27$. By the above, we have the following posts filled in:↵
↵
$1\text{ (8 blanks) }1\text{ (15 blanks) }1~\underline{ }$↵
↵
We can use the same color for positions $11$ and $27$, to obtain the following:↵
↵
$1\text{ (8 blanks) }1~2\text{ (14 blanks) }1~2$↵
↵
The remaining even-length blanks can be filled in similar to above. The result is as follows and can be hard-coded:↵
↵
$\mathtt{1~3~3~4~4~5~5~6~6~1~2~7~7~8~8~9~9~10~10~11~11~12~12~13~13~1~2}$↵
↵
Then, for odd $n\ge 27$, add $\frac{n-27}{2}$ pairs with distance $1$ to complete the construction.↵
↵
Note that there are different ways to construct this starting array for $n=27$ as well.↵
↵
Time complexity: $O(n)$↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291676952]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:3,option1]↵
- Okay problem: [likes:3,option2]↵
- Bad problem: [likes:3,option3]↵
- Did not attempt: [likes:3,option4]↵
</spoiler>↵
↵
↵
[problem:2031D]↵
↵
Idea: [user:AverageDiv1Enjoyer,2024-11-15]<br>↵
Preparation: [user:HappyPacMan,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Suppose that you have found the maximum height reachable from tree $i+1$. How do you find the maximum height reachable from tree $i$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let $p$ be the **highest** height among trees indexed from $1$ to $i$, and $s$ be the **lowest** height among trees indexed from $i+1$ to $n$. When can tree $i$ be reachable from tree $i+1$? ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First, observe that a rabbit at tree $n$ can reach the highest tree; if the tree has index $i<n$, then the rabbit can jump from tree $n$ to $i$. Let $ans_k$ denote the tallest height reachable from tree $k$, then $ans_n=\max(a_1,a_2,\ldots a_n)$.↵
↵
We iteratively look at trees $n-1$ to $1$. Suppose we have found the tallest height $ans_{i+1}$ reachable from tree $i+1$. Note that from tree $i$ we can reach the tallest tree with index between $1$ and $i$, and from tree $i+1$ we can reach the shortest tree with index between $i+1$ and $n$. Let $a_x=p_i=\max(a_1,a_2,\ldots a_i)$ and $a_y=s_i=\min(a_{i+1},a_{i+1},\ldots a_n)$. ↵
↵
Then if $p_i>s_i$ then tree $i+1$ is reachable from tree $i$ by the sequence $i\leftrightarrow x\leftrightarrow y\leftrightarrow i+1$. Thus, any tree reachable from tree $i$ is reachable from tree $i+1$, and vice versa; thus, $ans_i=ans_{i+1}.$↵
↵
On the other hand, if $p_i\le s_i$, then for any $r\le i$ and $s\ge i+1$, we have $r<s$ and $a_r\le p_i\le s_i\le a_s$. Thus, **no tree** between index $i+1$ and $n$ inclusive is reachable from any tree from $1$ and $i$ inclusive. Similar to the first paragraph, we have $ans_i=\max(a_1,a_2,\ldots a_i)=p_i$.↵
↵
Time complexity: $O(n)$↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677082]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:4,option1]↵
- Okay problem: [likes:4,option2]↵
- Bad problem: [likes:4,option3]↵
- Did not attempt: [likes:4,option4]↵
</spoiler>↵
↵
[problem:2031E]↵
↵
Idea & preparation: [user:ACGN,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Consider the tree where root $1$ has $k$ children which are all leaves. What is its minimum depth?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Consider undoing the operations from the given tree back to the perfect binary tree. Where can each child of the tree go? ↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
As in Hint 2, suppose that there exists a finite sequence of operations that convert a perfect binary tree $T_d$ of depth $d$ to our target tree $T$. We consider where each child of vertex $1$ in $T$ is mapped to the binary tree; specifically, for each such child $c$, let $c'$ be the highest vertex in $T_d$ that maps to $c$ under the operations. Then we can see that the subtree rooted at $c'$ in $T_d$ maps to the subtree rooted at $c$ in $T$.↵
↵
Suppose that the minimum depth required for the subtree rooted at $c$ in $T$ is $d_c$. ↵
↵
Claim 1: $2^d\ge \sum_{c}2^{d_c}$, where the sum is taken across all children $c$ of $1$.↵
↵
<spoiler summary="Proof">↵
Note that no two of the $v_c$ are ancestors or descendants of each other; otherwise, if $v_{c_1}$ is an ancestor of $v_{c_2}$, then $c_1$ would be an ancestor of $c_2$.↵
↵
Consider the $2^d$ leaves of $T_d$. Of them, for each $c$, $2^{d_c}$ of them are descendants of $v_c$. As no leaf can be descendants of two $v_c$'s, the inequality follows.↵
</spoiler>↵
↵
Claim 2: If $1$ has only one child $c$, then $d=d_c+1$; otherwise, $d$ is the least integer that satisfies the inequality of Claim 1.↵
↵
<spoiler summary="Proof">↵
Suppose $1$ only has one child $c$. Then $d\le d_c$ clearly does not suffice, but $d=d_c+1$ does as we can merge the entire right subtree into the root $1$.↵
↵
Suppose now that $1$ has multiple children $c_1,c_2,\ldots c_k$, sorted by descending $d_c$. For each child $c_i$ from $c_1$ to $c_k$, allocate $v_{c_i}$ to be the leftmost possible vertex at a height of $d_{c_i}$. Then the leaves that are ancestors of $c_i$ form a contiguous segment, so this construction ensures that each child $c_i$ can be placed on the tree.↵
</spoiler>↵
↵
Thus, we can apply tree dp with the transition function from $d_{c_i}$ to $d$ described by Claim 2. However, naively implementing it has a worst-case time complexity of $O(n^2).$↵
↵
<spoiler summary="Example of worst-case time complexity">↵
Consider a tree constructed this way: $2$ and $3$ are children of $1$, $4$ and $5$ are children of $3$, $6$ and $7$ are children of $5$, and so on; the odd-numbered vertices form a chain with the even-numbered vertices being leaves. ↵
↵
In such a graph, the depth $d$ is the length of the odd-numbered chain. Thus, during the computation of $d$, we would have to evaluate $2^x+1$ for $x$ from $1$ to $d\approx\frac{n}{2}.$ However, evaluating $2^x+1$ naively requires at least $O(x)$ time, so the algorithm runs in $O(n^2)$.↵
</spoiler>↵
↵
There are several ways to improve the time complexity of the dp transition.↵
↵
For example, sort $d_{c_i}$ in increasing order, then maintain the sum as $a\times 2^b$, where initially $a=b=0$. For each $c_i$ in order, replace $a$ by $\lceil \frac{a}{2^{d_{c_i}-b}}\rceil$ and replace $b$ by $d_{c_i}$. Then finally, $d=\lceil \log_2 a\rceil+b$.↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677229]↵
↵
Another way to do so is to "merge" terms from smallest to largest; importantly, since we just need to crudely bound $S=\sum_{c}2^{d_c}$, we can replace $2^x+2^y$ by $2^{max(x,y)+1}$. Then we can repeat this process until only one element remains.↵
↵
<spoiler summary="Why does this work?">↵
Suppose that $x>y$. Then the above operation rounds up $S$ to the nearest $2^x$. Since $2^d\ge S>2^x$, rounding up $S$ will not cause it to exceed the next power of $2$, so $2^d\ge S$ remains true after the operation.↵
</spoiler>↵
↵
Implementation: (by [user:Dominater069,2024-11-15]) [submission:291677365]↵
↵
Both transitions work in $O(k\log{k})$, leading to an overall time complexity of $O(n\log{n})$.↵
↵
**UPD: Thanks to [user:shinlena,2024-11-15] for an $O(n)$ solution, refer to [this thread.](https://codeforces.net/blog/entry/136260?#comment-1218776) Thanks!!**↵
</spoiler>↵
↵
↵
<spoiler summary="About Problem E">↵
The idea of the problem came from thinking about the "creation of the world" while vibing to Hatsune Creation Myth; in particular, our rooted tree is the "world" now, and the binary tree was the "original world" yet to be refined by compressing its edges.↵
↵
The problem came to life during a break in my lecture, when I was experimenting with "creating" a tree. Hope you liked it!↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:5,option1]↵
- Okay problem: [likes:5,option2]↵
- Bad problem: [likes:5,option3]↵
- Did not attempt: [likes:5,option4]↵
</spoiler>↵
↵
[problem:2031F]↵
↵
Idea: [user:trunkty,2024-11-14]<br>↵
Solution & preparation: [user:maomao90,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Querying $n - 2$ elements is very powerful.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Try to find two indices $x$ and $y$ such that one of $p_x, p_y$ is strictly smaller than $\frac{n}{2}$ and the other is strictly greater than $\frac{n}{2} + 1$. What can you do after finding these two elements?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 1">↵
_This solution is non-deterministic and uses $\frac{n}{2} + O(1)$ queries_↵
↵
**Part 1**↵
↵
Suppose we select all elements except for two indices $1 \le i, j \le n$ to be used in the query. Let the result we receive be $(a, b)$ where $a \lt b$. If $a = \frac{n}{2}$ and $b = \frac{n}{2} + 1$, it means that one of $p_i, p_j$ is strictly smaller than $\frac{n}{2}$ and the other is strictly larger than $\frac{n}{2}$.↵
↵
If we do the above query randomly, there is around $50\%$ chance of getting the above outcome. So we can just randomly select two indices to exclude from the query until we get the above result.↵
↵
**Part 2**↵
↵
Now that we have two elements $x$ and $y$ such that one of $p_x, p_y$ is strictly smaller than $\frac{n}{2}$ and the other is strictly greater than $\frac{n}{2} + 1$, we can query $[x, y, i, j]$. The median of $[p_x, p_y, p_i, p_j]$ will include $\frac{n}{2}$ if and only if one of $p_i, p_j$ is equal to $\frac{n}{2}$. The same is true for $\frac{n}{2} + 1$. We can iterate through all $\frac{n}{2} - 1$ pairs to find the two pairs that contain the median, then iterate through all $4\choose 2$ combinations of median to find the answer.↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677579]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
_This solution is deterministic and uses $\frac{3n}{4}$ queries_↵
↵
To make the solution deterministic, we need to find a deterministic solution to **Part 1**. **Part 2** is already deterministic so we can just use the same solution.↵
↵
Let us analyse all the possible cases if we select all elements except for two indices $1 \le i, j \le n$ to be used in the query. Let the result we receive be $(a, b)$ where $a \lt b$.↵
↵
↵
1. $a = \frac{n}{2}$ and $b = \frac{n}{2} + 1$. In this case, one of $p_i, p_j$ is strictly smaller than $\frac{n}{2}$ and the other is strictly larger than $\frac{n}{2}$, which is exactly what we wanted to find.↵
2. $a = \frac{n}{2}$ and $b = \frac{n}{2} + 2$. In this case, one of $p_i, p_j$ is strictly smaller than $\frac{n}{2}$ and the other is equal to $\frac{n}{2} + 1$.↵
3. $a = \frac{n}{2} - 1$ and $b = \frac{n}{2} + 1$. In this case, one of $p_i, p_j$ is strictly larger than $\frac{n}{2} + 1$ and the other is equal to $\frac{n}{2}$.↵
4. $a = \frac{n}{2} - 1$ and $b = \frac{n}{2}$. In this case, both of $p_i, p_j$ are larger than or equal to $\frac{n}{2} + 1$.↵
5. $a = \frac{n}{2} + 1$ and $b = \frac{n}{2} + 2$. In this case, both $p_i, p_j$ are smaller than or equal to $\frac{n}{2}$.↵
6. $a = \frac{n}{2} - 1$ and $b = \frac{n}{2} + 2$. In this case, $p_i$ and $p_j$ are the two medians.↵
\end{enumerate}↵
↵
If we have two queries such that one query is type 4 and another is type 5, then we can use one element from each pair to form the desired $x$ and $y$. We have to use one additional query to make sure that the chosen elements are not part of the median. We will only ask at most $\frac{n}{4}$ queries before there is at least one query of type 4 and one query of type 5. Types 2 and 3 can be treated together with types 4 and 5 with some careful handling. ↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677671]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 3">↵
_This solution is deterministic and uses $\frac{n}{2}+\log_2 n$ queries. Special thanks to [user:SHZhang,2024-11-10] for discovering this solution._↵
↵
Call the elements of the permutation less than or equal to $\frac{n}{2}$ lower elements, and call the rest upper elements. Pair up the permutation's elements (we can just pair index 1 with index 2, index 3 with index 4, and so on). Do $\frac{n}{2}$ queries where the $i$-th query consists of all elements except those in the $i$-th pair. This lets us determine whether (1) both elements in the pair are lower elements, (2) both are upper elements, or (3) there is one lower and one upper element in the pair. In case (3), we can also tell if the pair contains one or both of the desired medians (Take a look at solution 2 for a more in-depth case analysis).↵
↵
Our goal now is to identify the pairs that the lower and upper medians belong to. It suffices to be able to find them from the pairs of type (1) and (2), since we have already found the ones in type (3) pairs. This can be done with binary search on the type (1) and (2) pairs, by balancing the number of pairs of both types and checking if the median is in the result (The two binary searches can be performed simultaneously). This is similar to **Part 2** of solution 1, but instead of just using $4$ elements, we can generalise to use more elements if there is an equal number of lower and upper elements.↵
↵
After figuring out which pair each median is in, there are four possibilities remaining for the answer. For each one, make a query consisting of all the elements but the two candidates for the two medians that we are checking. When we see $\left(\frac{n}{2} - 1, \frac{n}{2} + 2\right)$ as the response, we know we found the answer.↵
↵
Implementation: (by [user:SHZhang,2024-11-15]) [submission:291677713]↵
</spoiler>↵
↵
↵
<spoiler summary="Challenge">↵
Code an adaptive grader that can kill the following solution: Use the same solution as "Solution 1". However, before the start of the actual algorithm, ask a few (around 10) random queries.↵
↵
This problem originally used an adaptive grader, but I didn't know how to kill the above scam as the random queries added too much restriction to the permutation that I can no longer force the randomised solution to use more queries.↵
↵
I think you will probably need to solve the following problem in polynomial time in order to kill the solution: Determine whether there exists a permutation that satisfies all the given queries and results so far.↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:6,option1]↵
- Okay problem: [likes:6,option2]↵
- Bad problem: [likes:6,option3]↵
- Did not attempt: [likes:6,option4]↵
</spoiler>↵
↵
#### Round statistics↵
Fastest submission among all participants, and among rated participants:<br>↵
A: [user:tourist,2024-11-15] at 00:00:43, [user:priyanshu.p,2024-11-15] at 00:00:56<br>↵
B: [user:tourist,2024-11-15] at 00:01:57, [user:arnabmanna,2024-11-15] at 00:02:10<br>↵
C: [user:arvindf232,2024-11-15] at 00:06:22, [user:boboquack,2024-11-15] at 00:11:42<br>↵
D: [user:_Duck_Dot_Dot_Happy,2024-11-15] at 00:10:50<br>↵
E: [user:fzx,2024-11-15] at 00:11:27, [user:Jack.YT,2024-11-15] at 00:20:38<br>↵
F: [user:peti1234,2024-11-15] at 00:34:01, [user:waiting_for_the_sunset,2024-11-15] at 00:54:34↵
↵
More round statistics to be updated!↵
↵
That's it for this round, and we hope you had fun with all the problems!↵
↵
<spoiler summary="A few serious words from ACGN - about problemsetting, MathForces, and more">↵
Note that all of these have been written **before** the contest.↵
↵
When I reached master in 2022, I had a bunch of problem ideas that I compiled as unpublished problem proposals — around 30 of them. I looked through my old proposals — problems written by me 2 years ago.↵
↵
After 2 years of essentially quitting CP, and focusing on studies and math, I concluded that a lot of them were... garbage, or what might be most aptly described as "uninsightful mashups of number theory with random stuff".↵
↵
Yet more of them were too straightforward applications or "routine problems", and simply didn't feel interesting enough to me. Again, I'm on my own.↵
↵
Over the course of these 2 years, I've been a bit more strict with myself in terms of problem ideas. To create a good problemset requires a lot of time, effort, energy, possibly coffee. And still, the problemset might not be good enough.↵
↵
Throughout problemsetting, I've always had the concern of the round potentially being "mathforces". In particular, after I set a math-related problem C, my choices were B were limited. It's not easy to balance problem types, especially when I tend to lean towards math problems.↵
↵
Before the review process started, I was hoping for this contest to have the most ideal, interesting problems — just as every problemsetter would. However, issues happen in testing, and the final problemset wasn't exactly what I hoped for. While I still hope you all enjoyed the contest thoroughly, I've learnt just how difficult coming up with a round is — not only does a problem have to get through coordinators, it also can't create a too large or small difficulty gap — it's a very delicate balance.↵
↵
So, thank you to everyone on this 2-year journey towards creating these problems, and we hope you enjoyed the culmination of our efforts.↵
↵
\- [user:ACGN,2024-11-14]↵
</spoiler>↵
↵
↵
<spoiler summary = "and from my own heart...">↵
the 3ish years of my CP journey has been nothing but fun. From making it to the IOI within my first year, to meeting amazing people online and getting to know (part of) the community, it has been an amazing ride with all of you. Even as I continue to study medicine and embark on another journey, I will never forget the thrills of coming up with an idea to solve a problem, debugging the code for literally days, frantically reloading the judge for a verdict, and seeing the green sacred "<span style="color:#00aa00;font-weight:bold">Accepted</span>" texts. ↵
↵
Now that this might very well be my formal retirement, I don't know if I'll come back to bring more joy (and problems) to the CF community. I sure have some treats left in store, but it's perhaps time to cherish the memories I've made with all of you: doing surprisingly well in Codeton 1, "grinding" math 3500s and such for fun, to ACing IOI22-circuit to save a bronze medal, solving difficult problems have always been extremely stimulating, thrilling, and exciting for me. That's why I've had so much fun in the CP world, even though I've only been here for a short time, and still don't really know how to code DFS. So, thank you to everyone on this journey, and I wish you all peace.↵
</spoiler>↵
↵
↵
<spoiler summary="A little backstory about the round (ACGN)">The Highschool CPers (HSCP) Discord server was created in April 2022 by [user:pwned,2024-11-14], which over time grew into a close-knit community of highschool competitive programmers. I joined in the same month of its creation, and in the next month I approached [user:pwned,2024-11-14] about the possibility of setting a contest. Thus the HSCP round concept was born.↵
↵
Over the next month or so, the initial problems were born; the current problems A and F were produced in June-July 2022. We had several problem ideas by then, enough to set a div.2 round. However, as I was going to be busy in my 5th year of high school, and may not be that responsive to coordinators, the contest was in the ownership of [user:pwned,2024-11-14], who needed to wait until he reached master in order to propose the set on Codeforces.↵
↵
However, this step took almost 1.5 years as he would stay at candidate master for 57 consecutive contests, even hitting 2099 rating. Eventually, in January 2024, [user:pwned,2024-11-15] finally reached master and submitted the round, and in May, the round began to be reviewed by our dear coordinator [user:maomao90,2024-11-14].↵
↵
It took 3 months (totally not procrastinating) to prepare all the problems, and testing commenced in August. However, the difficulty gap between problems quickly became apparent. The original problems A, C, E became the current A, D, F, and three new problems (for B, C, and E) had to be devised. Therefore, I started coming up with problems in the dead of night, hoping to finish the contest as soon as possible.↵
↵
Eventually, in October, all the gaps were filled, and thus the current problem set was born.↵
↵
Originally, I wanted to theme this round based on the game Hatsune Miku: Colorful Stage!, and in particular the current problem E was inspired by the song Hatsune Creation Myth by cosMo<wbr>@Bousou-P. [Go give it a listen!](https://www.youtube.com/watch?v=8J6SMoVd5BY)↵
↵
Ultimately, less than a week before the round, we chose to settle on a "geographical" theme, since the authors of this contest hail from different nations. We also chose Penchick, a traveling penguin chick, as the main character, but we kept a essence of the game Hatsune Miku: Colorful Stage!: Kohane (Azusawa Kohane, appearing in problem B and C) is one of the game characters, and was featured on one of my early profile pictures (before I even started playing the game). Nowadays, Kohane has been immortalized in the HSCP server as an "anime character", receiving a dedicated emoji :kohane:. ↵
</spoiler>↵
↵
[problem:2031A]↵
↵
Idea: [user:pwned,2024-11-14]<br>↵
Preparation: [user:HappyPacMan,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Consider the maximum number of pillars that can be left untouched instead.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Under what conditions can $k>1$ pillars be untouched?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Note that if pillars $i$ and $j$ with different heights are both untouched, then the first pillar must be taller than the second, which contradicts the fact that the heights must be non-decreasing after the adjustment. Thus, all unadjusted pillars must be of the same height.↵
↵
Therefore, the required number of pillars to adjust is $n-k$, where $k$ is the maximum number of pillars with the same height $h$. This bound is reachable by, for example, adjusting all pillars to height $h$.↵
↵
To find $k$, we can go through each index $i$ and find the number of pillars with the same height as $i$; this gives $O(n^2)$ time complexity, which is good enough for this problem. Alternatively, you can use a frequency array or `std::map`, or sequentially go through the list and find the longest sequence of equal terms, all of which have better time complexities.↵
↵
Implementation:<br>↵
$O(n^2)$: (by [user:ACGN,2024-11-16]) [submission:291675590]<br>↵
Frequency array: (by [user:pavement,2024-11-14]) [submission:291676291]<br>↵
Map: (by [user:newb_programmer,2024-11-14]) [submission:291676566]<br>↵
Sequential approach: (by [user:AlperenT,2024-11-14]) [submission:291676646]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:1,option1]↵
- Okay problem: [likes:1,option2]↵
- Bad problem: [likes:1,option3]↵
- Did not attempt: [likes:1,option4]↵
</spoiler>↵
↵
[problem:2031B]↵
↵
Idea: [user:ACGN,2024-11-14]<br>↵
Preparation: [user:HappyPacMan,2024-11-14]↵
↵
<spoiler summary="Hint 1">Consider which permutations you can get by reversing the operations and starting from the identity permutation</spoiler>↵
↵
↵
<spoiler summary="Hint 2">After $p_i$ and $p_{i+1}$ have been swapped, i.e. $p_i=i+1$ and $p_{i+1}=i$, neither of them can then be involved in another different swap.</spoiler>↵
↵
↵
<spoiler summary="Solution">Suppose we begin with the identity permutation. Consider what happens after swapping $p_i=i$ and $p_{i+1}=i+1$. After this swap, elements $p_1$ to $p_{i-1}$ will consist of $1$ to $i-1$, and $p_{i+2}$ to $p_n$ will consist of $i+2$ to $n$. Thus, it is impossible for $p_i=i+1$ to swap with $p_{i-1}\lt i$, or for $p_{i+1}=i$ to swap with $p_{i+2}\gt i+1$.↵
↵
Therefore, the swaps made must be independent of each other; in other words, the indices $i$ chosen in the process must differ from each other than at least $2$. These permutations satisfy the following: for each index $i$,↵
↵
- $p_i=i$, or↵
- $p_i=i+1$ and $p_{i+1}=i$, or↵
- $p_i=i-1$ and $p_{i-1}=i$.↵
↵
One way to check for this is to iterate for $i$ from $1$ to $n$. If $p_i=i$ then continue, and if $p_i=i+1$ then check if $p_{i+1}=i$, then swap $p_i$ and $p_{i+1}$. Otherwise, the permutation cannot be sorted.↵
↵
Time complexity: $O(n)$↵
↵
Implementation: (by [user:AlperenT,2024-11-13]) [submission:291676758]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:2,option1]↵
- Okay problem: [likes:2,option2]↵
- Bad problem: [likes:2,option3]↵
- Did not attempt: [likes:2,option4]↵
</spoiler>↵
↵
[problem:2031C]↵
↵
Idea & preparation: [user:ACGN,2024-11-14]↵
↵
<spoiler summary="Hint 1">Solve the problem for $n=2$ and for even $n$ in general.</spoiler>↵
↵
↵
<spoiler summary="Hint 2">For odd $n$, there exists a color that appears at least thrice. What does this mean?</spoiler>↵
↵
↵
<spoiler summary="Solution">Note that $1$ is a square number; thus, for even $n$, the construction $1~1~2~2~3~3\ldots\frac{n}{2}~\frac{n}{2}$ works. ↵
↵
For odd $n$, note that there exists a color that appears at least thrice, say at positions $x\lt y \lt z$. Then $y-x$, $z-y$ and $z-x$ are all square numbers. Note that $z-x=(z-y)+(y-x)$, which has the smallest solution being $z-x=5^2=25$, and $\{z-y,y-x\}=\{9,16\}$. Therefore, there is no solution if $n\le 25$. ↵
↵
We devise a solution for $n=27$. By the above, we have the following posts filled in:↵
↵
$1\text{ (8 blanks) }1\text{ (15 blanks) }1~\underline{ }$↵
↵
We can use the same color for positions $11$ and $27$, to obtain the following:↵
↵
$1\text{ (8 blanks) }1~2\text{ (14 blanks) }1~2$↵
↵
The remaining even-length blanks can be filled in similar to above. The result is as follows and can be hard-coded:↵
↵
$\mathtt{1~3~3~4~4~5~5~6~6~1~2~7~7~8~8~9~9~10~10~11~11~12~12~13~13~1~2}$↵
↵
Then, for odd $n\ge 27$, add $\frac{n-27}{2}$ pairs with distance $1$ to complete the construction.↵
↵
Note that there are different ways to construct this starting array for $n=27$ as well.↵
↵
Time complexity: $O(n)$↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291676952]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:3,option1]↵
- Okay problem: [likes:3,option2]↵
- Bad problem: [likes:3,option3]↵
- Did not attempt: [likes:3,option4]↵
</spoiler>↵
↵
↵
[problem:2031D]↵
↵
Idea: [user:AverageDiv1Enjoyer,2024-11-15]<br>↵
Preparation: [user:HappyPacMan,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Suppose that you have found the maximum height reachable from tree $i+1$. How do you find the maximum height reachable from tree $i$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let $p$ be the **highest** height among trees indexed from $1$ to $i$, and $s$ be the **lowest** height among trees indexed from $i+1$ to $n$. When can tree $i$ be reachable from tree $i+1$? ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First, observe that a rabbit at tree $n$ can reach the highest tree; if the tree has index $i<n$, then the rabbit can jump from tree $n$ to $i$. Let $ans_k$ denote the tallest height reachable from tree $k$, then $ans_n=\max(a_1,a_2,\ldots a_n)$.↵
↵
We iteratively look at trees $n-1$ to $1$. Suppose we have found the tallest height $ans_{i+1}$ reachable from tree $i+1$. Note that from tree $i$ we can reach the tallest tree with index between $1$ and $i$, and from tree $i+1$ we can reach the shortest tree with index between $i+1$ and $n$. Let $a_x=p_i=\max(a_1,a_2,\ldots a_i)$ and $a_y=s_i=\min(a_{i+1},a_{i+1},\ldots a_n)$. ↵
↵
Then if $p_i>s_i$ then tree $i+1$ is reachable from tree $i$ by the sequence $i\leftrightarrow x\leftrightarrow y\leftrightarrow i+1$. Thus, any tree reachable from tree $i$ is reachable from tree $i+1$, and vice versa; thus, $ans_i=ans_{i+1}.$↵
↵
On the other hand, if $p_i\le s_i$, then for any $r\le i$ and $s\ge i+1$, we have $r<s$ and $a_r\le p_i\le s_i\le a_s$. Thus, **no tree** between index $i+1$ and $n$ inclusive is reachable from any tree from $1$ and $i$ inclusive. Similar to the first paragraph, we have $ans_i=\max(a_1,a_2,\ldots a_i)=p_i$.↵
↵
Time complexity: $O(n)$↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677082]↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:4,option1]↵
- Okay problem: [likes:4,option2]↵
- Bad problem: [likes:4,option3]↵
- Did not attempt: [likes:4,option4]↵
</spoiler>↵
↵
[problem:2031E]↵
↵
Idea & preparation: [user:ACGN,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Consider the tree where root $1$ has $k$ children which are all leaves. What is its minimum depth?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Consider undoing the operations from the given tree back to the perfect binary tree. Where can each child of the tree go? ↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
As in Hint 2, suppose that there exists a finite sequence of operations that convert a perfect binary tree $T_d$ of depth $d$ to our target tree $T$. We consider where each child of vertex $1$ in $T$ is mapped to the binary tree; specifically, for each such child $c$, let $c'$ be the highest vertex in $T_d$ that maps to $c$ under the operations. Then we can see that the subtree rooted at $c'$ in $T_d$ maps to the subtree rooted at $c$ in $T$.↵
↵
Suppose that the minimum depth required for the subtree rooted at $c$ in $T$ is $d_c$. ↵
↵
Claim 1: $2^d\ge \sum_{c}2^{d_c}$, where the sum is taken across all children $c$ of $1$.↵
↵
<spoiler summary="Proof">↵
Note that no two of the $v_c$ are ancestors or descendants of each other; otherwise, if $v_{c_1}$ is an ancestor of $v_{c_2}$, then $c_1$ would be an ancestor of $c_2$.↵
↵
Consider the $2^d$ leaves of $T_d$. Of them, for each $c$, $2^{d_c}$ of them are descendants of $v_c$. As no leaf can be descendants of two $v_c$'s, the inequality follows.↵
</spoiler>↵
↵
Claim 2: If $1$ has only one child $c$, then $d=d_c+1$; otherwise, $d$ is the least integer that satisfies the inequality of Claim 1.↵
↵
<spoiler summary="Proof">↵
Suppose $1$ only has one child $c$. Then $d\le d_c$ clearly does not suffice, but $d=d_c+1$ does as we can merge the entire right subtree into the root $1$.↵
↵
Suppose now that $1$ has multiple children $c_1,c_2,\ldots c_k$, sorted by descending $d_c$. For each child $c_i$ from $c_1$ to $c_k$, allocate $v_{c_i}$ to be the leftmost possible vertex at a height of $d_{c_i}$. Then the leaves that are ancestors of $c_i$ form a contiguous segment, so this construction ensures that each child $c_i$ can be placed on the tree.↵
</spoiler>↵
↵
Thus, we can apply tree dp with the transition function from $d_{c_i}$ to $d$ described by Claim 2. However, naively implementing it has a worst-case time complexity of $O(n^2).$↵
↵
<spoiler summary="Example of worst-case time complexity">↵
Consider a tree constructed this way: $2$ and $3$ are children of $1$, $4$ and $5$ are children of $3$, $6$ and $7$ are children of $5$, and so on; the odd-numbered vertices form a chain with the even-numbered vertices being leaves. ↵
↵
In such a graph, the depth $d$ is the length of the odd-numbered chain. Thus, during the computation of $d$, we would have to evaluate $2^x+1$ for $x$ from $1$ to $d\approx\frac{n}{2}.$ However, evaluating $2^x+1$ naively requires at least $O(x)$ time, so the algorithm runs in $O(n^2)$.↵
</spoiler>↵
↵
There are several ways to improve the time complexity of the dp transition.↵
↵
For example, sort $d_{c_i}$ in increasing order, then maintain the sum as $a\times 2^b$, where initially $a=b=0$. For each $c_i$ in order, replace $a$ by $\lceil \frac{a}{2^{d_{c_i}-b}}\rceil$ and replace $b$ by $d_{c_i}$. Then finally, $d=\lceil \log_2 a\rceil+b$.↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677229]↵
↵
Another way to do so is to "merge" terms from smallest to largest; importantly, since we just need to crudely bound $S=\sum_{c}2^{d_c}$, we can replace $2^x+2^y$ by $2^{max(x,y)+1}$. Then we can repeat this process until only one element remains.↵
↵
<spoiler summary="Why does this work?">↵
Suppose that $x>y$. Then the above operation rounds up $S$ to the nearest $2^x$. Since $2^d\ge S>2^x$, rounding up $S$ will not cause it to exceed the next power of $2$, so $2^d\ge S$ remains true after the operation.↵
</spoiler>↵
↵
Implementation: (by [user:Dominater069,2024-11-15]) [submission:291677365]↵
↵
Both transitions work in $O(k\log{k})$, leading to an overall time complexity of $O(n\log{n})$.↵
↵
**UPD: Thanks to [user:shinlena,2024-11-15] for an $O(n)$ solution, refer to [this thread.](https://codeforces.net/blog/entry/136260?#comment-1218776) Thanks!!**↵
</spoiler>↵
↵
↵
<spoiler summary="About Problem E">↵
The idea of the problem came from thinking about the "creation of the world" while vibing to Hatsune Creation Myth; in particular, our rooted tree is the "world" now, and the binary tree was the "original world" yet to be refined by compressing its edges.↵
↵
The problem came to life during a break in my lecture, when I was experimenting with "creating" a tree. Hope you liked it!↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:5,option1]↵
- Okay problem: [likes:5,option2]↵
- Bad problem: [likes:5,option3]↵
- Did not attempt: [likes:5,option4]↵
</spoiler>↵
↵
[problem:2031F]↵
↵
Idea: [user:trunkty,2024-11-14]<br>↵
Solution & preparation: [user:maomao90,2024-11-14]↵
↵
<spoiler summary="Hint 1">↵
Querying $n - 2$ elements is very powerful.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Try to find two indices $x$ and $y$ such that one of $p_x, p_y$ is strictly smaller than $\frac{n}{2}$ and the other is strictly greater than $\frac{n}{2} + 1$. What can you do after finding these two elements?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 1">↵
_This solution is non-deterministic and uses $\frac{n}{2} + O(1)$ queries_↵
↵
**Part 1**↵
↵
Suppose we select all elements except for two indices $1 \le i, j \le n$ to be used in the query. Let the result we receive be $(a, b)$ where $a \lt b$. If $a = \frac{n}{2}$ and $b = \frac{n}{2} + 1$, it means that one of $p_i, p_j$ is strictly smaller than $\frac{n}{2}$ and the other is strictly larger than $\frac{n}{2}$.↵
↵
If we do the above query randomly, there is around $50\%$ chance of getting the above outcome. So we can just randomly select two indices to exclude from the query until we get the above result.↵
↵
**Part 2**↵
↵
Now that we have two elements $x$ and $y$ such that one of $p_x, p_y$ is strictly smaller than $\frac{n}{2}$ and the other is strictly greater than $\frac{n}{2} + 1$, we can query $[x, y, i, j]$. The median of $[p_x, p_y, p_i, p_j]$ will include $\frac{n}{2}$ if and only if one of $p_i, p_j$ is equal to $\frac{n}{2}$. The same is true for $\frac{n}{2} + 1$. We can iterate through all $\frac{n}{2} - 1$ pairs to find the two pairs that contain the median, then iterate through all $4\choose 2$ combinations of median to find the answer.↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677579]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
_This solution is deterministic and uses $\frac{3n}{4}$ queries_↵
↵
To make the solution deterministic, we need to find a deterministic solution to **Part 1**. **Part 2** is already deterministic so we can just use the same solution.↵
↵
Let us analyse all the possible cases if we select all elements except for two indices $1 \le i, j \le n$ to be used in the query. Let the result we receive be $(a, b)$ where $a \lt b$.↵
↵
↵
1. $a = \frac{n}{2}$ and $b = \frac{n}{2} + 1$. In this case, one of $p_i, p_j$ is strictly smaller than $\frac{n}{2}$ and the other is strictly larger than $\frac{n}{2}$, which is exactly what we wanted to find.↵
2. $a = \frac{n}{2}$ and $b = \frac{n}{2} + 2$. In this case, one of $p_i, p_j$ is strictly smaller than $\frac{n}{2}$ and the other is equal to $\frac{n}{2} + 1$.↵
3. $a = \frac{n}{2} - 1$ and $b = \frac{n}{2} + 1$. In this case, one of $p_i, p_j$ is strictly larger than $\frac{n}{2} + 1$ and the other is equal to $\frac{n}{2}$.↵
4. $a = \frac{n}{2} - 1$ and $b = \frac{n}{2}$. In this case, both of $p_i, p_j$ are larger than or equal to $\frac{n}{2} + 1$.↵
5. $a = \frac{n}{2} + 1$ and $b = \frac{n}{2} + 2$. In this case, both $p_i, p_j$ are smaller than or equal to $\frac{n}{2}$.↵
6. $a = \frac{n}{2} - 1$ and $b = \frac{n}{2} + 2$. In this case, $p_i$ and $p_j$ are the two medians.↵
\end{enumerate}↵
↵
If we have two queries such that one query is type 4 and another is type 5, then we can use one element from each pair to form the desired $x$ and $y$. We have to use one additional query to make sure that the chosen elements are not part of the median. We will only ask at most $\frac{n}{4}$ queries before there is at least one query of type 4 and one query of type 5. Types 2 and 3 can be treated together with types 4 and 5 with some careful handling. ↵
↵
Implementation: (by [user:ACGN,2024-11-16]) [submission:291677671]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 3">↵
_This solution is deterministic and uses $\frac{n}{2}+\log_2 n$ queries. Special thanks to [user:SHZhang,2024-11-10] for discovering this solution._↵
↵
Call the elements of the permutation less than or equal to $\frac{n}{2}$ lower elements, and call the rest upper elements. Pair up the permutation's elements (we can just pair index 1 with index 2, index 3 with index 4, and so on). Do $\frac{n}{2}$ queries where the $i$-th query consists of all elements except those in the $i$-th pair. This lets us determine whether (1) both elements in the pair are lower elements, (2) both are upper elements, or (3) there is one lower and one upper element in the pair. In case (3), we can also tell if the pair contains one or both of the desired medians (Take a look at solution 2 for a more in-depth case analysis).↵
↵
Our goal now is to identify the pairs that the lower and upper medians belong to. It suffices to be able to find them from the pairs of type (1) and (2), since we have already found the ones in type (3) pairs. This can be done with binary search on the type (1) and (2) pairs, by balancing the number of pairs of both types and checking if the median is in the result (The two binary searches can be performed simultaneously). This is similar to **Part 2** of solution 1, but instead of just using $4$ elements, we can generalise to use more elements if there is an equal number of lower and upper elements.↵
↵
After figuring out which pair each median is in, there are four possibilities remaining for the answer. For each one, make a query consisting of all the elements but the two candidates for the two medians that we are checking. When we see $\left(\frac{n}{2} - 1, \frac{n}{2} + 2\right)$ as the response, we know we found the answer.↵
↵
Implementation: (by [user:SHZhang,2024-11-15]) [submission:291677713]↵
</spoiler>↵
↵
↵
<spoiler summary="Challenge">↵
Code an adaptive grader that can kill the following solution: Use the same solution as "Solution 1". However, before the start of the actual algorithm, ask a few (around 10) random queries.↵
↵
This problem originally used an adaptive grader, but I didn't know how to kill the above scam as the random queries added too much restriction to the permutation that I can no longer force the randomised solution to use more queries.↵
↵
I think you will probably need to solve the following problem in polynomial time in order to kill the solution: Determine whether there exists a permutation that satisfies all the given queries and results so far.↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:6,option1]↵
- Okay problem: [likes:6,option2]↵
- Bad problem: [likes:6,option3]↵
- Did not attempt: [likes:6,option4]↵
</spoiler>↵
↵
#### Round statistics↵
Fastest submission among all participants, and among rated participants:<br>↵
A: [user:tourist,2024-11-15] at 00:00:43, [user:priyanshu.p,2024-11-15] at 00:00:56<br>↵
B: [user:tourist,2024-11-15] at 00:01:57, [user:arnabmanna,2024-11-15] at 00:02:10<br>↵
C: [user:arvindf232,2024-11-15] at 00:06:22, [user:boboquack,2024-11-15] at 00:11:42<br>↵
D: [user:_Duck_Dot_Dot_Happy,2024-11-15] at 00:10:50<br>↵
E: [user:fzx,2024-11-15] at 00:11:27, [user:Jack.YT,2024-11-15] at 00:20:38<br>↵
F: [user:peti1234,2024-11-15] at 00:34:01, [user:waiting_for_the_sunset,2024-11-15] at 00:54:34↵
↵
More round statistics to be updated!↵
↵
That's it for this round, and we hope you had fun with all the problems!↵
↵
<spoiler summary="A few serious words from ACGN - about problemsetting, MathForces, and more">↵
Note that all of these have been written **before** the contest.↵
↵
When I reached master in 2022, I had a bunch of problem ideas that I compiled as unpublished problem proposals — around 30 of them. I looked through my old proposals — problems written by me 2 years ago.↵
↵
After 2 years of essentially quitting CP, and focusing on studies and math, I concluded that a lot of them were... garbage, or what might be most aptly described as "uninsightful mashups of number theory with random stuff".↵
↵
Yet more of them were too straightforward applications or "routine problems", and simply didn't feel interesting enough to me. Again, I'm on my own.↵
↵
Over the course of these 2 years, I've been a bit more strict with myself in terms of problem ideas. To create a good problemset requires a lot of time, effort, energy, possibly coffee. And still, the problemset might not be good enough.↵
↵
Throughout problemsetting, I've always had the concern of the round potentially being "mathforces". In particular, after I set a math-related problem C, my choices were B were limited. It's not easy to balance problem types, especially when I tend to lean towards math problems.↵
↵
Before the review process started, I was hoping for this contest to have the most ideal, interesting problems — just as every problemsetter would. However, issues happen in testing, and the final problemset wasn't exactly what I hoped for. While I still hope you all enjoyed the contest thoroughly, I've learnt just how difficult coming up with a round is — not only does a problem have to get through coordinators, it also can't create a too large or small difficulty gap — it's a very delicate balance.↵
↵
So, thank you to everyone on this 2-year journey towards creating these problems, and we hope you enjoyed the culmination of our efforts.↵
↵
\- [user:ACGN,2024-11-14]↵
</spoiler>↵
↵
↵
<spoiler summary = "and from my own heart...">↵
the 3ish years of my CP journey has been nothing but fun. From making it to the IOI within my first year, to meeting amazing people online and getting to know (part of) the community, it has been an amazing ride with all of you. Even as I continue to study medicine and embark on another journey, I will never forget the thrills of coming up with an idea to solve a problem, debugging the code for literally days, frantically reloading the judge for a verdict, and seeing the green sacred "<span style="color:#00aa00;font-weight:bold">Accepted</span>" texts. ↵
↵
Now that this might very well be my formal retirement, I don't know if I'll come back to bring more joy (and problems) to the CF community. I sure have some treats left in store, but it's perhaps time to cherish the memories I've made with all of you: doing surprisingly well in Codeton 1, "grinding" math 3500s and such for fun, to ACing IOI22-circuit to save a bronze medal, solving difficult problems have always been extremely stimulating, thrilling, and exciting for me. That's why I've had so much fun in the CP world, even though I've only been here for a short time, and still don't really know how to code DFS. So, thank you to everyone on this journey, and I wish you all peace.↵
</spoiler>↵
↵
