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.

how to solve C?Please Money Sharing

It‘s greed.You can calculate the sum of prefix，add negative number in set，if the sum of prefix less than zero，you should erase the number in set from small and large and sum of prefix subtract you erase number. Last all number in set is "approved",negative number not in set is "declined", all positive number is "resupplied".

How to solve D (and F)?

Spoiler (D)From the AC solution I see that after $$$n=799039878$$$ the number of subsequences ending with $$$a$$$ becomes constant (but what's the motivation for looking for smth like this)?

How to solve E?

Wikipedia

Thanks

How to solve F?

Not sure about the official solution, but you can find the closest pairs of points for both sets and try setting them equal to each other.

Thanks!