adamant's blog

By adamant, history, 3 weeks ago, In English,

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!

 
 
 
 
  • Vote: I like it
  • +126
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -43 Vote: I do not like it

is it rated?

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve B?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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, # |
  Vote: I like it +39 Vote: I do not like it

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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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