The Highschool CPers (HSCP) Discord server was created in April 2022 by pwned, 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 pwned 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 pwned, 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, pwned finally reached master and submitted the round, and in May, the round began to be reviewed by our dear coordinator maomao90.

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@Bousou-P. Go give it a listen!

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

Consider the maximum number of pillars that can be left untouched instead.

Under what conditions can $$$k>1$$$ pillars be untouched?

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:
$$$O(n^2)$$$: (by ACGN) 291675590
Frequency array: (by pavement) 291676291
Map: (by newb_programmer) 291676566
Sequential approach: (by AlperenT) 291676646

• Good problem:
• Okay problem:
• Bad problem:
• Did not attempt:

Consider which permutations you can get by reversing the operations and starting from the identity permutation

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.

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 AlperenT) 291676758

• Good problem:
• Okay problem:
• Bad problem:
• Did not attempt:

Solve the problem for $$$n=2$$$ and for even $$$n$$$ in general.

For odd $$$n$$$, there exists a color that appears at least thrice. What does this mean?

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 ACGN) 291676952

• Good problem:
• Okay problem:
• Bad problem:
• Did not attempt:

Suppose that you have found the maximum height reachable from tree $$$i+1$$$. How do you find the maximum height reachable from tree $$$i$$$?

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$$$?

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 ACGN) 291677082

• Good problem:
• Okay problem:
• Bad problem:
• Did not attempt:

Consider the tree where root $$$1$$$ has $$$k$$$ children which are all leaves. What is its minimum depth?

Consider undoing the operations from the given tree back to the perfect binary tree. Where can each child of the tree go?

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

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.

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

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

Implementation: (by Dominater069) 291677365

Both transitions work in $$$O(k\log{k})$$$, leading to an overall time complexity of $$$O(n\log{n})$$$.

UPD: Thanks to shinlena for an $$$O(n)$$$ solution, refer to this thread. Thanks!!

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!

• Good problem:
• Okay problem:
• Bad problem:
• Did not attempt:

Querying $$$n - 2$$$ elements is very powerful.

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?

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 ACGN) 291677579

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 ACGN) 291677671

This solution is deterministic and uses $$$\frac{n}{2}+\log_2 n$$$ queries. Special thanks to SHZhang 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 SHZhang) 291677713

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.

• Good problem:
• Okay problem:
• Bad problem:
• Did not attempt:

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.

- ACGN

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 "Accepted" 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.