### RubenAshughyan's blog

By RubenAshughyan, history, 3 weeks ago, , This blog is to discuss the problems of Northwestern Russia Regional Contest round 2019 held on October 26. Comments (11)
•  » » » 9 days ago, # ^ | ← Rev. 2 →   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)$.
•  » » 7 days ago, # ^ | ← Rev. 2 →   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  » 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$50000x$in$[0, 4 \times 10^7]\$.