Блог пользователя RubenAshughyan

Автор RubenAshughyan, история, 4 года назад, По-английски

This blog is to discuss the problems of Northwestern Russia Regional Contest round 2019 held on October 26.

The problems: https://neerc.ifmo.ru/archive/2019/northern/northwest-russia-2019-statements.pdf

What was your approach on problem B (Bad Treap) ?

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Any mirror where we can submit problems?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

L? How to solve faster than O(N*(logN)^3). We found solution with suffix automat, heavy-light and convex hull :'(.

And D please

Thanks in andvance!

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain your approach using suffix automat, heavy-light and convex hull? We tried something similar with suffix tree, centroid decomposition and FFT but didn't succeed.

    Thanks in advance!

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

      Our solution uson suffix automaton was as follows:

      For the solution, you can argue that you want to get a balance between a small period and a big length. Take each node in the suffix automaton, and its endpos set $$$S$$$. The smallest period that you can obtain is the smallest difference between two elements in $$$S$$$ (try to prove to yourself why that is). You can compute the smallest period for each node in $$$O(n \log^2{n})$$$ using min-max merge of suffix link tree. Then you just update a global maximum with $$$(len(node) + mind(node))/ mind(node)$$$.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

    Problem D:

    Firstly, we ignore some redundant strings, and we define $$$R(n)$$$ equals to the number of palindrome or concatenation of two palindromes. We can iterate the length of first palindrome (length maybe 0), and $$$R(n)=\sum_{i=0}^{n-1} k^{\lceil \frac{i}{2} \rceil} k^{\lceil \frac{n-i}{2} \rceil }$$$.

    But some strings may be calculated multi times, like $$$abaaba$$$. We can assume that it is a palindrom or the concatenation of $$$aba$$$.

    There is concolusion that a palindrome has two or more concatenation plans if and only if the palindrome $$$s$$$ has a period $$$p$$$ ($$$\forall i+p<|s|, s[i]=s[i+p]$$$) and $$$|s|$$$ can be divided by $$$p$$$. The number of plans is $$$|s|/p$$$ ($$$p$$$ is the period with minimum length of $$$s$$$).

    So, we define $$$D(n)$$$ equals to the number of palindroms or strings that have only one kind of concatenation plan like $$$caba$$$. We need to substract the number of extra strings. With the concolusion above, we only need to iterate all the factors $$$l$$$ of $$$n$$$(except $$$n$$$ itself), and $$$D(n)=R(n)-\sum_{l|n \land l<n} \frac{n}{l} D(l)$$$.

    Finally, the anser is $$$\sum_{i=1}^n \sum_{l|i} D(l)$$$. The time complexity is $$$O(n\sqrt{n})$$$ or $$$O(n\log n)$$$.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For B, we took such $$$x$$$ that $$$\sin x_{i+1} < \sin x_i$$$ and $$$\sin x_i - \sin x_{i+1} < \epsilon$$$ where $$$\epsilon = 9 \times 10^{-5}$$$ (we chose it by trial and error :p). This seemed to generate $$$50000$$$ $$$x$$$ in $$$[0, 4 \times 10^7]$$$.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Also, the editorial is here in Russian: https://neerc.ifmo.ru/archive/2019/northern/nwrrc-2019-tutorials.pdf

Any English version? I am having hard time reading F. :3

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

anybody can help me !!!!i don't know how to solve e,thx!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The node you are looking for will be always on the center of the path between any team city and the fartest node from that team city. If that node doesn't satisfy the condition, then the answer is NO

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell how to solve H?

Thanks in advance. :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Store the prefix sum array and binary search on the t_i values for each query. Store the result of every query. You can prove that this works in less than A_i * logN * log(A_i).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Bad Treap, first take some approximation for $$$\pi=\frac{p}{q}$$$. Then, to find $$$\arcsin(\theta)$$$ by an integer (which for small $$$\theta$$$ is the whole goal), we can think of getting some non-integer $$$\theta$$$ and setting up the following equation, $$$\theta = x-2\pi k$$$ for some integer $$$k$$$. But we said $$$\pi=\frac{p}{q}$$$, so we have $$$\theta = x-2\frac{p}{q} k$$$, and we multiply out to get $$$q\theta = qx-2pk$$$. Then, if we set left side to $$$1$$$, and if $$$q$$$ is big, then that will find us an integer that is equivalent to a really small angle (because then $$$\theta=\frac{1}{q}$$$). If we also pick some approximation in which $$$q$$$ is odd, $$$1 = qx-2pk$$$ wil have solution and can be solved just with normal extended euclidean for $$$x$$$. To get all the angles, we can just think of multiplying $$$\theta$$$ by large negative value, and gradually increasing by adding $$$\theta$$$. But this can be done with just $$$x$$$ instead of $$$\theta$$$ and it will be the same because they are equivalent modulo $$$2\pi$$$.