adamant's blog

Oleksandr Kulkov Contest 2 in gym
By adamant, history, 4 years 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

»
4 years ago, # |
  Vote: I like it -43 Vote: I do not like it

is it rated?

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?Please Money Sharing

→ Reply
  • »
    »
    4 years 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".

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +24 Vote: I do not like it

How to solve D (and F)?

Spoiler (D)
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve A?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Calculate the number of solutions modulo prime number $$$p$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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}$$$.

        → Reply