Thank you for waiting! I hope you've enjoyed the problems. Let me know what you think in the comments!↵
↵
Some problems may still not appear as the export from Polygon works kinda slowly. Refresh the page once in a while and everything should appear eventually.↵
↵
I'll be adding stuff to this editorial, like Russian translation, challenges and notes on my preparation experience (it was, let's say, interesting). Stay tuned!↵
↵
[tutorial:1368A]↵
↵
[tutorial:1368B]↵
↵
[tutorial:1368C]↵
↵
[tutorial:1368D]↵
↵
[tutorial:1368E]↵
↵
[tutorial:1368F]↵
↵
[tutorial:1368G]↵
↵
[tutorial:1368H2]I almost forgot but here are some notes, as well as challenges for all problems. For a lot of them I don't have a solution and would be happy to hear your ideas.↵
↵
[tutorial:1368A]↵
↵
<spoiler summary="Challenge (awful)">↵
Find a closed formula for the answer. For simplicity assume $a \leq b$,↵
</spoiler>↵
↵
[tutorial:1368B]↵
↵
<spoiler summary="Challenge (?)">↵
As mentioned above, the problem is not that easy in general case when there are a lot of repeated letters. Still, is it possible to do? Any solution faster than brute-force would be interesting, or even some ideas or observations.↵
</spoiler>↵
↵
<spoiler summary="Notes">↵
I find it much harder to create a good easy problem than a good hard problem. This position in paricular gave me a lot of trouble, we had to scratch three or four other versions. Not to say the result is very inspiring, but the previous ones were even worse...↵
↵
What do you except to see in a good easy problem, say, up to Div1A? What are you favourite easy problems of this level? I would especially appreciate answers from high-rated coders.↵
</spoiler>↵
↵
[tutorial:1368C]↵
↵
<spoiler summary="Challenge (probably doable)">↵
How to minimize the total number of squares for a given $n$? The squares-on-a-diagonal construction in the first picture is pretty efficient, but e.g. for $n=4$ the picture in the sample has fewer squares. How does the minimum-square picture look in general?↵
</spoiler>↵
↵
[tutorial:1368D]↵
↵
<spoiler summary="Challenge (?)">↵
How to find the smallest number of operations we need to make until there are no more we can make? Any solution polynomial in $n$ and $\log_2 \max A$ would be interesting.↵
</spoiler>↵
↵
[tutorial:1368E]↵
↵
<spoiler summary="Challenge (???)">↵
It's not hard to construct a test where $n/2$ spots have to be closed. However, I could not find a test where more that $n/2$ spots need to be closed, nor do I know of a solution that closes less than $4n/7$ spots in the worst case.↵
In other words, if $\alpha$ is the optimal constant such that $\alpha n + o(n)$ spots need to be closed, we know that $1/2 \leq \alpha \leq 4/7$. Can I find better bounds for $\alpha$, or even find its precise value?↵
</spoiler>↵
↵
<spoiler summary="Notes">↵
↵
Huge thanks to our tester [user:kocko,2020-06-24] for pointing out many mistakes in an old version of this problem's statement, and even proposing a revision of a big part of the statement which we've adopted. Sadly, many other parts of the statement still were not very clear...↵
↵
</spoiler>↵
↵
[tutorial:1368F]↵
↵
<spoiler summary="Challenge (probably doable)">↵
If the first player wants to minimize the number of turns until $R(n)$ lamps are lit, and the second player wants to maximize it, what is the resulting number of turns $T(n)$ is going to be? Precise formula would be awesome, but asymptotics or interesting bounds for $T(n)$ would be interesting too.↵
</spoiler>↵
↵
[tutorial:1368G]↵
↵
<spoiler summary="Challenge (?)">↵
What are the minimum and maximum possible answers among all tilings of the board of given dimensions $n$ and $m$?↵
</spoiler>↵
↵
[tutorial:1368H2]↵
↵
<spoiler summary="Challenge (running out of ideas)">↵
Can you solve the same problem in 3D? The breadboard is now an $n \times m \times k$ parallelepiped, and there are $2(nm + nk + mk)$ adjacent ports.↵
</spoiler>↵
↵
↵
↵
I'll be adding stuff to this editorial, like Russian translation, challenges and notes on my preparation experience (it was, let's say, interesting). Stay tuned!↵
↵
[tutorial:1368A]↵
↵
[tutorial:1368B]↵
↵
[tutorial:1368C]↵
↵
[tutorial:1368D]↵
↵
[tutorial:1368E]↵
↵
[tutorial:1368F]↵
↵
[tutorial:1368G]↵
↵
[tutorial:1368H2]
↵
[tutorial:1368A]↵
↵
<spoiler summary="Challenge (awful)">↵
Find a closed formula for the answer. For simplicity assume $a \leq b$,↵
</spoiler>↵
↵
[tutorial:1368B]↵
↵
<spoiler summary="Challenge (?)">↵
As mentioned above, the problem is not that easy in general case when there are a lot of repeated letters. Still, is it possible to do? Any solution faster than brute-force would be interesting, or even some ideas or observations.↵
</spoiler>↵
↵
<spoiler summary="Notes">↵
I find it much harder to create a good easy problem than a good hard problem. This position in paricular gave me a lot of trouble, we had to scratch three or four other versions. Not to say the result is very inspiring, but the previous ones were even worse...↵
↵
What do you except to see in a good easy problem, say, up to Div1A? What are you favourite easy problems of this level? I would especially appreciate answers from high-rated coders.↵
</spoiler>↵
↵
[tutorial:1368C]↵
↵
<spoiler summary="Challenge (probably doable)">↵
How to minimize the total number of squares for a given $n$? The squares-on-a-diagonal construction in the first picture is pretty efficient, but e.g. for $n=4$ the picture in the sample has fewer squares. How does the minimum-square picture look in general?↵
</spoiler>↵
↵
[tutorial:1368D]↵
↵
<spoiler summary="Challenge (?)">↵
How to find the smallest number of operations we need to make until there are no more we can make? Any solution polynomial in $n$ and $\log_2 \max A$ would be interesting.↵
</spoiler>↵
↵
[tutorial:1368E]↵
↵
<spoiler summary="Challenge (???)">↵
It's not hard to construct a test where $n/2$ spots have to be closed. However, I could not find a test where more that $n/2$ spots need to be closed, nor do I know of a solution that closes less than $4n/7$ spots in the worst case.↵
In other words, if $\alpha$ is the optimal constant such that $\alpha n + o(n)$ spots need to be closed, we know that $1/2 \leq \alpha \leq 4/7$. Can I find better bounds for $\alpha$, or even find its precise value?↵
</spoiler>↵
↵
<spoiler summary="Notes">↵
↵
Huge thanks to our tester [user:kocko,2020-06-24] for pointing out many mistakes in an old version of this problem's statement, and even proposing a revision of a big part of the statement which we've adopted. Sadly, many other parts of the statement still were not very clear...↵
↵
</spoiler>↵
↵
[tutorial:1368F]↵
↵
<spoiler summary="Challenge (probably doable)">↵
If the first player wants to minimize the number of turns until $R(n)$ lamps are lit, and the second player wants to maximize it, what is the resulting number of turns $T(n)$ is going to be? Precise formula would be awesome, but asymptotics or interesting bounds for $T(n)$ would be interesting too.↵
</spoiler>↵
↵
[tutorial:1368G]↵
↵
<spoiler summary="Challenge (?)">↵
What are the minimum and maximum possible answers among all tilings of the board of given dimensions $n$ and $m$?↵
</spoiler>↵
↵
[tutorial:1368H2]↵
↵
<spoiler summary="Challenge (running out of ideas)">↵
Can you solve the same problem in 3D? The breadboard is now an $n \times m \times k$ parallelepiped, and there are $2(nm + nk + mk)$ adjacent ports.↵
</spoiler>↵
↵
