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)?
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!
How to solve A?
Calculate the number of solutions modulo prime number $$$p$$$.
I see, we tried that during the contest; however, one of the members in our team noticed that the probability of some number having a square root modulo $$$p$$$ is $$$1/2$$$ , so the probability of all numbers having square root is very small. How do you tackle the case where not all numbers have square roots modulo $$$p$$$?
On a side note, I saw some people implementing solutions using a different field than $$$\mathbb{Z}_p$$$ (supposedly one where all elements have square roots?). I am also curios in what that field is and how it works.
All $$$GF(p)$$$ elements have square roots in $$$GF(p^2)$$$ actually. This field can be perceived as set of elements $$$a+b\sqrt{x}$$$ with addition and multiplication similar to the one in complex numbers. Specifically if multiplication in complex numbers is done modulo $$$i^2=-1$$$, in this field multiplication is done modulo $$$(\sqrt{x})^2=x$$$. Here $$$x$$$ is some quadratic non-residue (doesn't matter which one specifically, all such fields are isomorphic).
If $$$t$$$ is a quadratic residue, you should take a root via $$$a=\sqrt{t}=t^{\frac{p+1}{4}}$$$, as $$$t^{p+1} \equiv t^2 \pmod p$$$, so taking $$$4$$$-th root of it is same as taking square root of $$$t$$$ itself (you should take $$$p$$$ such that $$$p\equiv 3 \pmod 4$$$ for this to work). Otherwise you should calculate $$$b=\sqrt{\frac{t}{x}}$$$, after this you'll find it that $$$\sqrt{t}=b\sqrt{x}$$$.