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
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:.
2031A - Penchick and Modern Monument
Idea: pwned
Preparation: HappyPacMan
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
2031B - Penchick and Satay Sticks
Idea: ACGN
Preparation: HappyPacMan
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)$$$
Idea & preparation: ACGN
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)$$$
2031D - Penchick and Desert Rabbit
Idea: AverageDiv1Enjoyer
Preparation: HappyPacMan
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)$$$
2031E - Penchick and Chloe's Trees
Idea & preparation: ACGN
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$$$.
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.
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.
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.
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).$$$
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)$$$.
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}$$$, which essentially serves to round up the sum to the nearest $$$2^{d_{c_i}}$$$. Then, increment $$$a$$$ to add $$$2^{d_{c_i}}$$$ to the sum. At the end of these operations, we have $$$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.
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.
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!
2031F - Penchick and Even Medians
Idea: trunkty
Solution & preparation: maomao90
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.
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$$$.
- $$$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.
- $$$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$$$.
- $$$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}$$$.
- $$$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$$$.
- $$$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}$$$.
- $$$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.
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.
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.
Round statistics
Fastest submission among all participants, and among rated participants:
A: tourist at 00:00:43, priyanshu.p at 00:00:56
B: tourist at 00:01:57, arnabmanna at 00:02:10
C: arvindf232 at 00:06:22, boboquack at 00:11:42
D: _Duck_Dot_Dot_Happy at 00:10:50
E: fzx at 00:11:27, Jack.YT at 00:20:38
F: peti1234 at 00:34:01, waiting_for_the_sunset 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!
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.
wow,the tutorial comes so fast!
like a wind :)
always by my side
Run Sora/Nobu :)
hint 1 for D is missing
great contest c is quite interesting
very easy for a C
Why the hints of D starts from Hint 2? By the way, good C&D.
numbering issue, sorry and has been fixed
why my code for C got wrong answer?
the $$$1$$$s at indices $$$1$$$ and $$$9$$$ are separated by a distance of $$$8$$$, which isn't a square.
ah thanks!
dist b/w first 1 and last 1 is not a perfect square
superfast editorial
C was great. The Pythagorean triples idea is so elegant.
thanks, it was my favorite problem!
Nice trick on C. Instead of creating this array
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
I create this
1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 13 13 1 12
That's the construction some of the testers used; there are many ways to construct a suitable array.
Same as mine, but to figure out that odd number still exists a way, that literally took me a while.
Exactly, I think that most of the people whose first solution got WA have submitted that for odd N, answer is -1 and after getting it wrong started to think about odd N.
another way $$$x=1e6$$$
x 1 2 3 4 5 6 7 8 x 12 11 11 13 13 14 14 1 2 3 4 5 6 7 8 x 12
I used a different array from both: 1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,10,10,11,11,12,12,13,13,2
i used 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 10 11 11 12 13 13 1 12 ..
Considering how many ways you could place the last odd value (having a distance of $$$9$$$ or $$$4$$$ or $$$16$$$, there are $$$2 \times (21 + 16 + 11)$$$ unique patterns. (neglecting the values of the individual element).
Instead of writing any hard-code, we can just write like this : 291682216
1,12,13,13,11,12,10,9,11,8,10,7,9,8,6,7,1,5,6,4,3,5,2,4,3,1,2 can this be a sequence for first 27 element in question c?
the fastest tutorial ever!
[1, 2, 3, 3, 1, 2, 4, 4, 1] is sollution for 9 which is less then 25 for problem C
distance is 1 for 3, 4 and 4 for 1, 2
this is wrong, the first and last 1 have a distance of 8.
distance between 1s at indices 1 and 9 is 8 which is not perfect square
No , 9 — 1 is 8 which is not a perfect square
A caught me off guard wtf
I find I always make problem more complex, like this div.2 D. I spent 30mins to solve ABC, but can't wock out D. What should I do to avoid??
What algorithm you think it should be applied in D?
I preprocessed out the position of the largest number and sorted it by numerical size and position. Then use a monotonic stack to maintain a suffixed minimum value from back to front. When I want to compute the answer, find the position of this minimum and find the answer before it. The time complexity is $$$O(n\log{n})$$$ because I need to make a binary search inside the stack to find this rearmost minimum.
At first, I thought the same thing however I notice that I can create mountains (*mountain is an decreasing array), so a mountain will have a peak (the largest value) and a down (the smallest value).
For example: 2 4 1 6 3 8 5 7 -> (2), (4, 1), (6, 3), (8, 5), (7)
And then I save the largest and smallest of each mountain
(2), (4, 1), (6, 3), (8, 5), (7) -> (2, 2), (4, 1), (6, 3), (8, 5), (7, 7)
Here's another example 2 5 3 1 6 2 10 9 8 -> (2), (5, 3, 1), (6, 2), (10, 9, 8)
Then (2), (5, 3, 1), (6, 2), (10, 9, 8) -> (2, 2), (5, 1), (6, 2), (10, 8)
And I notice that if there exist 2 mountains i and j so that i.peak > j.down then the rabbit can jump from mountain i to mountain j. I sort these mountains with the peak decreasing and I find out that the problem now looks like a graph (more like DSU).
Here's my solution 291628412
Thanks.
I use this algorithm too!
Can D be solved with dsu?
Yep. For each point, merge it with the point to the left of this point and with the highest height, and also merge it with the point to the right that is farthest away from it and with a height smaller than it. It can be shown that this merging is optimal.
How do you keep track of highest height to the left and the points which are farthest away with a height smaller than it?
binary search + suffix min
so why my code for D is wrong?
Lmaooooo I already knew that tons would vote "Bad Problem" in the feedback for C. This community can be so predictable at times.
C is an EXCELLENT problem, yall are just haters
Yes, many of them don't think about the odd amount of elements can have a solution
So true bestie
What is the purpose of samples in such problems? They always must have funny non generalizable construction.
Well of course it has to be non-generalizable, otherwise it would spoil the problem haha
Regardless, it does still serve the following purposes:
For example in this problem, what does |i — j| = a perfect square mean? Should it be the 1st and 9th buns that match, or the 1st and 10th? We know it should be 1 and 10, but it's a reasonable misunderstanding to make, especially in the heat of a contest.
But the answer is easily, totally unambiguous because you can very easily just check the sample output to see which interpretation is correct.
Typo: In Problem F Solution 1 Part 1 line 2: and the other is strictly larger than $$$\frac n2$$$ -> larger than $$$\frac n2 +1$$$.
if you know Pythagoras theorem,you can solve C easily
no bro it is still difficult to guess the correct solution
Penguins! A very nice contest :D
Though I stuck on C for nearly an hour(because of my poor math), I still think C is a beautiful problem conbined maths and constructive algorithms excellently. This is the best problem in this type I've ever met.
Can someone point out the mistake —
Consider
2 2 1 1
I couldn't solve A and B. My penchick is getting skinny Edit: Yay! I am now newbie!
For C, isn't
[1, 2, 2, 4, 4, 5, 5, 3, 6, 1, 7, 7, 6, 1, 9, 9, 3]
for 17?No, the first 1 and the last 1's distance is not a perfect square (13).
the $$$1$$$s at indices $$$1$$$ and $$$14$$$ differ by $$$13$$$, which is not a square.
dist between first 1 and last 1 is 13
Thanks for the fast editorial. Elegant problemsetting for C, now I learn.
What's wrong with this case for n=27 in Problem C? 13 1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 1
distance between your 2 first 1s is 8
you werw so close though that is the idea. but it's the even length you need to pad
No, I think its 9 only, 1s are on 1st and 10th index in the case you're mentioning.
So actually, I have put 1's on index 1, 10, 26 13s on index 0 and 25 Rest I just generated.
Oh yeah mb. Checked your last submit you're printing "13 1 \n" in the end arent you ? Maybe thats the issue ?
Got this: wrong answer Color 1 used only once (test case 1), but don't know which test case it could be on.
ans for n=1 is -1. no filings can be used a single time so n=1 has no valid answer.
Ohh man...crying myself to sleep. :((....Thanks dude!!
Dont ! Double checking minor mistakes is the easy part. Finding this idea for C i bet you get cyan in less than 5 contests !
ACGN pwned how to join the server?
Unfair time constraints for B, my correct solution [O(N) in PyPy] is giving tle on test 3, kindly accept this in system testing. (https://mirror.codeforces.com/contest/2031/submission/291630383) Wasted the whole contest in figuring out a logn or constant time solution for this, I didn't even try using C++ cause never do I expect a simple O(N) problem to give tle just because its python, also got like extra -200 because of trying shorter solutions for B out of frustration, so sad
Python's
input()
is slow (at least on the judge server); always usesys.stdin.readline().rstrip()
instead ofinput()
.oh okay, thanks a lot!
Calling
input()
in Python flushes stdout. Even in C++ you easily get the same kind of TLE if you forgetcin.tie(0)
. Repeatedly flushing stdout is very slow.For the future, put this into your template. Then you won't ever get this kind of TLE again.
omg the python god himself, thank you so much will use it from now on
Hmm for some reason python3 works but not pypy 291718850
In Problem D first example
4
2 3 1 4
o/p --> 3 3 3 4
how can rabbit jump from 2 to 3 because question clearly states that forward jump can be made iff the next guy is smaller.
2 -> 1 -> 3
The rabbit jump from 2 to 1 (because 1 < 2 and 1 stand after 2)
Then the rabbit jump from 1 to 3 (because 3 < 1 and 3 stand before 1)
Great problem C, good choice of samples as well, any more samples might've given away the solution.
E can be solved in $$$O(N)$$$
how so? I'm interested
Please have a look at 291664548
Basically, we just count the leaves needed for each subtree. The # can be large so we use a binary array.
Since the count added from each children is a power of two, by potential method the amortized time to do addition of all children is $$$O(#children)$$$.
Then we can just choose smallest $$$k$$$ such that $$$2^k$$$ leaves is enough.
Edit: I've just noticed the code above has a mistake: It has an unnecessary loop in
dfs
of O(d)However it can easily be fixed, as in 291671084
I'm sorry, I really can't understand the code; can you explain it in more detail and pseudocode? thankss
Sure,
dfs(u)
returns depth of perfect binary tree needed to build subtree ofu
in original tree.Let's call this value
dp[u]
.To calculate
dp[u]
, first we calculatedp[v]
for every childv
. The intuition is ifv
requires perfect binary search tree of depthdp[v]
, it will "consume"2^{dp[v] - 1}
leaves.We add the amount of leaves needed for each child node of
u
to get the total amount of leaves needed foru
's subtree.But the amount can be very large, so we use something similar to bigint in base 2.
(There might be some off-by-one error in this comment)
The complexity of bigint operations:
The bigint is stored as array where each element can be
0
or1
Since the value we add to it is always power of 2.
We can let potential of the array be count of digits with
1
in it.Each value we add will increase the potential by at most
1
Hence, amortized over all children of node
u
, the complexity isO(count of children of u)
Ohh wow, I didn't expect it to be possible to implement bigint this way; I overlooked the possibilty of implementing these bigints "on top" of each other, and thought that each bigint would need $$$O(n)$$$ space. Thanks for the insight!!
Nice solution.
I have been trying this form of dfs for 2 hours, but have failed to do so. Even using python, I get a runtime error. I will try your implementation for bigint. it is really fun
One can visualize the big int as a bitset of n bits right?
Yep
Nice
it will "consume" 2^{dp[v] — 1} leaves. what do you mean :( can you please explain
ACGN i can't view the implementation of problems,can you make them public?
I think the implementation are only viewable after system testing has concluded; sorry for the inconvenience.
Cool,thanks.
if this round didnt have samples, nothing would have changed
I finished ABCD for the second time!
I can not access the implementation of problem D !!!
Why are there so many pretests in Problem E?
Thanks for creating this round!All of the problems are awesome!
In the solution for D Shouldn't it be:
ansi=max(a1,a2,…ai)=pi
instead of
ansi=max(a1,a2,…an)=pi
my oversight, sorry!
Damn. C was just Fire. Though couldn't finished in time
Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).
In D ansi=max(a1,a2,…an)=pi. should be ansi=max(a1,a2,…ai)=pi.
C was a great question. I was very close to figuring it out, but couldn't solve it in the end :(
in A if i assume if n == 1, the answer will always be 0, but due to this i got the wrong answer, why is that? my answer got accepted after i removed this condition
Because you are not reading the input that comes after, so you are getting wrong input for the next testcase.
thanks
Can someone assist me in determining the first minimum element from the back of an array for each element in the array?
Thank you!
What an incredible journey! The blend of creativity, dedication, and unique themes makes this round truly special. Kudos to the team for bringing it to life!
Can someone help me figure out why 291650692 failed with RTE, while 291666454 passed? The only difference is that the priority_queue is declared local in the former and global in the latter. Is this because $$$10^6$$$ ints is too much for a stack allocated std::priority_queue?
good luck on your medicine journey. amazing story!
I think the definition of rooted tree isomorphism given in 2031-E - Penchick and Chloe's Trees is slightly wrong.
Here $$$u$$$ and $$$v$$$ are in the first tree, and $$$p_u$$$ and $$$p_v$$$ are nodes in the second tree. But then $$$r_1=p_{r_2}$$$ makes no sense since $$$p:$$$ first tree $$$\rightarrow$$$ second tree. The correct statement is $$$p_{r_1}=r_2$$$
Yep got me confused for a while.
i still dont understand this till now , i thought the definition of isomorphism is that there exists a root in the second tree where choosing it results in the first tree appearing but that doesnt seem the case in this problem for example take this tree
1 — 2 — 3 — 4 — 5 — 6 — 7
a binary tree of dep 3 aka 2 ^ 3 has a diameter of length 7 but for some reason the answer for the tree above is 6 ?
Both the trees have fixed roots. The problem used rooted isomorphism and not normal isomorphism. You should read statements correctly.
i didnt blame the problem author i legit didn't know what rooted isomorphism even meant so chill down , aside from that yes the definition was poorly written
I didnt say you blamed the author either....fyi, I (and I guess most participants) also did not know the definition of rooted isomorphism before solving the problem
no worries could have been better but atleast didnt get it in a rated contest
My bad. I'll fix it. Thanks for the catch!
I solved F with a solution with success rate of around $$$0.998$$$.
Denote $$$A$$$ as the set of candidates for $$$\frac{n}{2}$$$ (initially $$$ {1, 2, \dots, n}$$$). Similarly denote $$$B$$$ as the set of candidates for $$$\frac{n}{2} + 1$$$. We also maintain the third set $$$C$$$ of candidates for both $$$\frac{n}{2}$$$ and $$$\frac{n}{2} + 1$$$ (we will update it a bit differently, so it won't be just $$$A \cup B$$$).
Query a random subset $$$S$$$ of $$$C$$$ of size $$$10$$$. Let $$$x$$$ and $$$y$$$ be the result. If $$$x = \frac{n}{2}$$$ or $$$y = \frac{n}{2}$$$, there is $$$\frac{n}{2}$$$ in $$$S$$$, so we can set $$$A = A \cap S$$$. Similarly do for $$$B$$$. If $$$x = \frac{n}{2}$$$ and $$$y = \frac{n}{2} + 1$$$, then we can set $$$A = A \cap S \cap (A \cup B)$$$ and $$$B = B \cap S \cap (A \cup B)$$$ (actually, that does nothing).
We don't wanna keep $$$C$$$ too big, but also don't want to make it too small to have a higher chance to reduce the sizes of $$$A$$$ and $$$B$$$. What I do is: if $$$x < \frac{n}{2}$$$, $$$\frac{n}{2} + 1 < y$$$ and $$$|C| - |S| \ge 12$$$, set $$$C = C \setminus S$$$. Otherwise, do nothing.
Terminate the search when $$$|A \cup B| = 2$$$.
Out of $$$10000$$$ random tests with $$$n = 100$$$, it manages to solve around $$$9980$$$. Submission: 291665018
Is the implementaion of D visible?
Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).
why my code for C got wrong answer?
You were adding too many pairs of "i i" at the end of your loop in the odd case; replacing the last
i++
byi+=2
gives AC. 291678666How is it that suddenly 2000+ people solved C problem in the last 20-30 mins? Hope the cheaters are found and removed!!
for me, problem E much more easy then D))
C was so beautiful, was not able to solve it in the contest but the solution is elegant!
W problem @ACGN, keep it up!
I think D is easier than everything
Note that we don't need to dfs in Problem E since 1..n is a topo seq of the tree
I supposed the extra overhead of the unnecessary dfs would fail given the large tree, but it doesn't.
It's a bit of an implementation detail: the idea is still somewhat DFS, but I did implement it directly on the array, treating it as regular DP. The TL should? be generous enough to allow DFS as well.
The best C I've ever done 有生之年做过最好的C题
Problem B also can be solved by brute force, because one number can never be swapped more than twice, so we just need to check the array two times and swap two numbers if we can, time complexity $O(n)$。
code:
for problem A, what if all the elements are unequal and already organised but the first, does that mean we'll have to count all the "equal" numbers ?
D is a cute problem. Thanks.
why i am the only one who solve b with segment tree :(
https://mirror.codeforces.com/contest/2031/submission/291825632
Can any body explain why my code is wrong ?
Problem D : 291848242
I didn't undertand your code even after converting into cpp, also it's not compiling but i can give you 2 good test cases :
8
6 7 3 6 8 8 9 10
ans : 7 7 7 7 8 8 9 10
10
6 7 3 6 8 8 9 4 10 11
ans : 9 9 9 9 9 9 9 9 10 11
Please someone help me with this,why my 291854656 is WA ? Below code seems to be correct to me. Please provide a testcase where it fails . Thanks
1
4
1 4 2 3
Hope this helps. Answer should be NO
what would be the rating of C and D?
The last method given by the answer to question A if the test case is 1 5 4 4 1 4 shouldn't the output be 2? Why is its code output 3
Not sure about what input format you're using, but in any case this does not seem like a valid input. The input array must be non-increasing.
There is something wrong with the LaTex of problem E claim 1's proof. Please fix it. Thank you!
fixed!
Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).
Perhaps there is something wrong with the first way to slove E in your tutorial. After reading your code, maybe we should replace $$$a$$$ by $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil + 1$$$ but not $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil$$$
In Simplified Chinese: 楼主你E题第一种解法好像有个地方写的有问题。我看了你的代码之后,觉得有个地方教程里写的和你代码写的不符:我们应该把 $$$a$$$ 改成 $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil + 1$$$ ,而不是 $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil$$$
bug fixed
Good problem C.
what is wrong in this logic for problem B. Getting WA on 2nd test case.
292214260,2031B - Penchick and Satay Sticks
Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).
can anyone explain for me the dsu approach in D please?
We can you simple rangeMax segtree to solve problem D,
we just have to simulate , first go to max element in the left , then for every possible value from 1 to maxelement , take the value from previously element we have jumped
link: link
C was harder than D, but both were very easy compared to standard div2c's and d's
Could anyone give me a small test where my code for E fails? Thanks in advance
A tree with 9 leaves:
Your solution gives $$$3$$$, while the answer is $$$4$$$. Making one small change makes your code correct: 293581182
Thanks a lot!