By adamant, history, 3 weeks ago, ,

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!

• +126

 » 2 weeks ago, # |   -43 is it rated?
•  » » 2 weeks ago, # ^ |   +15 Yes
 » 2 weeks ago, # |   +8 How to solve B?
•  » » 2 weeks ago, # ^ |   +16 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: Add or remove number $x$ to/from the structure, Calculate how much numbers are there in the structure which are co-prime with $x$. 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.
 » 12 days ago, # |   +39 Thank you for sharing! Could you share ghosts' results as well?
•  » » 8 days ago, # ^ |   +31 Yep, it's done! Sorry for delay, that was a bit hard to do.