Today there were two nice contests in a row: AtCoder Regular Contest 149 and Codeforces Round 824 (Div. 2). I participated in both of them.
My participation in AtCoder Regular Contest 149 was quite a failure, I neither speedforced nor solved any of the harder problems. The video is already on my channel: https://youtu.be/3D1IbPtrLWg
My participation in Codeforces Round #824 (Div. 2) wasn't a failure, I even finished second! (And this is my by far the most successful participation in an unrated round.) The video is uploaded but still processing, so soon you will be able to watch it. As always, a nice bonus is a detailed editorial in the end of the video: https://youtu.be/fbFAg1th5oM
Subscriptions, comments, likes, watches and other ways of expressing feedback are welcome!
UPD. Now both videos are watchable. Enjoy!
Auto comment: topic has been updated by orz (previous revision, new revision, compare).
In Codeforces Round #824 (Div. 2) problem B, how did you come up with the idea that a0 the smallest element will not change, you solved the problem very fast.
Thank you for the video!!
Well, I am not even sure how I came up with this idea. During the contest I just intuitively (or semiintuitively) realized that it must be true.
One way of coming up is as follows. One asks themselves, “What is my goal”? The goal is that in the end the minimum piece $$$m$$$ and maximum piece $$$M$$$ satisfy $$$M\leqslant2m-1$$$ (for now, this is not necessarily true that $$$a_0=m$$$, possibly one has to divide it and other pieces even in smaller ones). So, given this goal and fixed $$$m$$$, how can we achieve this goal? Well, we have to divide all pieces into parts of size between $$$m$$$ and $$$2m-1$$$. And this is kinda intuitively clear (you can watch the formal proof in the video) that the minimum number of operations for this piece is $$$\left\lceil\frac{a_i}{2m-1}\right\rceil-1$$$. Having that in mind, one has to sum up all numbers $$$\left\lceil\frac{a_i}{2m-1}\right\rceil-1$$$. What is the optimal answer then? The bigger $$$m$$$ we take, the less the answer gets. But we cannot take $$$m>a_0$$$ because no piece can grow in size. So the best we can hope for is $$$\left\lceil\frac{a_i}{2a_0-1}\right\rceil-1$$$.
Maybe less strict, but more intuitive way is this. First step is as in the previous paragraph: we need all parts sized between $$$m$$$ and $$$2m-1$$$. And since this segment is quite wide, the lower bound $$$m$$$ won't be a problem as long as $$$m\leqslant a_0$$$ (I didn't even notice that $$$a_i$$$ in the input are sorted during the contest, rofl). The harder part is to make all pieces at most $$$2m-1$$$, and if one does it reasonably well, then they will be at least $$$m$$$ automatically. (The reasonable algorithm is as follows: if the piece $$$a_i$$$ is at most $$$2m-1$$$, one doesn't touch it. If the piece is at least $$$4m-3$$$, one just cuts off a piece of size $$$2m-1$$$ and repeats. Else one cuts it into pieces of sizes $$$\left\lfloor\frac{a_i}2\right\rfloor$$$ and $$$\left\lceil\frac{a_i}2\right\rceil$$$.) That said, all one needs is to make all pieces at most $$$2m-1$$$. And it's obvious that the greater the $$$2m-1$$$, the easier the task, so one wishes to maximize their $$$m$$$, thus, one just takes $$$m=a_0$$$ because it's impossible to take it any greater.
Thanks for the video, but can you explain what we are trying to do in problem B?
In the test case (1 2 3 4 5) why do all pieces need to be of size 1?
In the test case (600 900 1300 2000 2550) why are 600 and 900 not split?
I didn't understand what the question wants us to do.
For every two pieces, we need the ratio of their sizes to be less than two. In testcase $$$[1,2,3,4,5]$$$ every number except 1 is twice, thrice,... larger than 1. So unless you divide each number into ones, you'll have two numbers whose ratio is at least two, which means you have to move on.
In $$$[600, 900, 1300, 2000, 2550]$$$ the ratio between 900 and 600 is already $$$900/600=1.5<2$$$, therefore if you just divide everything else into pieces of size between $$$600$$$ and $$$1199=2\cdot600-1$$$ you will be fine.
Many thanks.
You should look into Microsoft Whiteboard instead of MS Paint for drawing.
Thank you! I'll try it.
Microsoft Whiteboard is really comfortable to use! Thank you again, I no more use MS Paint for solving problems.
I appreciate your reply, thank you!