Codeforces Global Round 8: editorial
Difference between en1 and en2, changed 3,067 character(s)
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]
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:1368
BF]↵

[tutorial:1368C]↵

[tutorial:1368D]
<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:1368
EG]↵

[tutorial:1368F]<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:1368
GH2]↵

[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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Endagorion 2020-06-24 05:36:14 344
en3 English Endagorion 2020-06-24 05:34:44 181
en2 English Endagorion 2020-06-24 05:20:40 3067 Tiny change: 've adopted in the statement. Sadly, m' -> 've adopted. Sadly, m'
en1 English Endagorion 2020-06-19 05:08:12 623 Initial revision (published)