1368.md (3414B)
1 Source: https://codeforces.com/blog/entry/79027 2 3 Thank you for waiting! I hope you've enjoyed the problems. Let me know what you think in the comments! 4 5 **UPD**: 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. 6 7 Tutorial is loading... 8 9 **Challenge (awful)** 10 11 Find a closed formula for the answer. For simplicity assume $a \leq b$, 12 13 Tutorial is loading... 14 15 **Challenge (?)** 16 17 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. 18 19 **Notes** 20 21 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... 22 23 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. 24 25 Tutorial is loading... 26 27 **Challenge (probably doable)** 28 29 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? 30 31 Tutorial is loading... 32 33 **Challenge (?)** 34 35 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. 36 37 Tutorial is loading... 38 39 **Challenge (???)** 40 41 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? 42 43 **Notes** 44 45 Huge thanks to our tester [kocko](/profile/kocko "Specialist kocko") 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... 46 47 Tutorial is loading... 48 49 **Challenge (probably doable)** 50 51 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. 52 53 Tutorial is loading... 54 55 **Challenge (?)** 56 57 What are the minimum and maximum possible answers among all tilings of the board of given dimensions $n$ and $m$? 58 59 **Notes** 60 61 The final version of this problem is due to [300iq](/profile/300iq "Legendary Grandmaster 300iq") who proposed an interesting modification to my initial idea. 62 63 Tutorial is loading... 64 65 **Challenge (running out of ideas)** 66 67 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.