Hi everyone!

This summer I gave another contest in summer Petrozavodsk programming camp and (although a bit lately) I want to share it with codeforces community by adding it to codeforces gym: 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2. To make it more fun I scheduled it on Sunday, 5 january, 12:00 (UTC+3). Feel free to participate during scheduled time or, well, whenever you're up to. Good luck and have fun :)

Problems might be discussed here afterwards, I even may write some editorials for particular problems (per request, as I don't have them prepared beforehand this time).

UPD: 17h reminder before the start of the contest

UPD2: It wasn't an easy task to do, but I managed to add ghost participants to the contest! Enjoy!

is it rated?

Yes

How to solve B?

Sketch of the solution is as follows: If you may solve it for $$$k=1$$$, then you may find an answer for arbitrary $$$k$$$ with additional $$$\log n$$$ factor. This is due to the fact that for some specific $$$k$$$ you may consider only indices which are divisible by $$$k$$$, and solve problem for new arrays as if it was $$$k=1$$$.

Now for $$$k=1$$$ you should construct the data structure which is able to answer following queries:

This can be done with inclusion-exclusion principle by keeping amount of numbers which are divisible by some particular square-free number. This will work in $$$2^d$$$ where $$$d$$$ is the number of distinct prime divisors of the number $$$x$$$. On average $$$d \approx \log \log x$$$. In worst case it may go up to $$$\frac{\log x}{\log \log x}$$$ but we shouldn't be concerned about it because in our solution every $$$x$$$ is nearly same amount of time, thus amortized running time will be close to $$$O(\log x)$$$.

Now with this let's make a binary search on the answer. To check if it is possible to obtains answer which is not greater than some fixed number $$$m$$$, we may utilize sliding window of the size $$$m$$$ on all numbers. What we have to know is if there are co-prime numbers with distance at least $$$m$$$ in the array, which may be solved by the structure mentioned above. Overall running time is $$$O(n \log^2 n \log x)$$$ with a small constant.

Thank you for sharing! Could you share ghosts' results as well?

Yep, it's done! Sorry for delay, that was a bit hard to do.