ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2095. Scrum

Solution is very intuitive.
Posted by Mahilewets 18 Jul 2017 21:30
Count numbers X and Y of quiet days for vacations given by intervals [1;r] and [1;l-1].

The answer to the problem would be ANS=X-Y.
How to count X and Y?

In the first step,  we eliminate every 2th.

That is,  CNT_0=r and and CNT_1=r//2

In the second step,  CNT_2=CNT_1//3.

And so on.

Until CNT > 0.

Last non-zero  CNT is the answer.

Re: Solution is very intuitive.
Posted by Anier Velasco Sotomayor 2 Jan 2021 20:06
Yes, but you should prove that the number of steps is short enough.
Here is some sketch of the proof. After deleting all 2nd numbers we are with $\frac{n}{2}$  numbers, after erasing all 3rd numbers we are with $\frac{2}{3}\cdot \frac{n}{2} = \frac{n}{3}$ numbers, after erasing all 4th numbers we are with $\frac{3}{4}\cdot \frac{n}{3} = \frac{n}{4}$ numbers and so on, after erasing every $k$-th number we are left with $\frac{n}{k}$ numbers, and we stop when $\frac{n}{k} < (k+1)\implies k \approx \sqrt{n}$, so after $O(\sqrt{n})$ steps the algorithm stops.

Edited by author 02.01.2021 20:07

Edited by author 02.01.2021 20:07

Edited by author 02.01.2021 20:09