Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

adamant's blog

By adamant, history, 3 months 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
  • +138
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it -43 Vote: I do not like it

is it rated?

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve B?

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it +39 Vote: I do not like it

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

  • »
    »
    3 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?Please Money Sharing

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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".

»
4 days ago, # |
Rev. 4   Vote: I like it +24 Vote: I do not like it

How to solve D (and F)?

Spoiler (D)
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    7 hours ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.