[problem:569A]↵
↵
Пусть перед очередным запуском прогружено $S$ секунд песни, найдем, сколько будет прогружено перед следующим запуском. $\frac{x}{q} = \frac{x-S}{q-1}$. Отсюда $x=qS$.↵
↵
Тогда решение: будем умножать $S$ на $q$ пока $S<T$. Количество таких умножений — это ответ.↵
↵
Сложность — $O(\log T)$↵
↵
↵
[problem:569B]↵
↵
Подойдём к задаче с другой стороны: а сколько максимально можно оставить номеров, чтобы получилась перестановка? Очевидно, что эти номера должны быть от $1$ до $n$, причем среди них не должно быть повторяющихся. И понятно, что это условие необходимое и достаточное.↵
↵
Такую задачу можно решать жадным алгоритмом. Если мы встретили число, которого ещё не было, при этом оно от $1$ до $n$, то мы его оставим. Для реализации можно завести массив used, в котором отмечать уже использованные числа.↵
↵
Затем нужно ещё раз пройти по массиву и распределить неиспользованные числа.↵
↵
Сложность — $O(n)$.↵
↵
↵
[problem:568A]↵
↵
Известно, что количество простых чисел, не превосходящих $n$, — число порядка $\frac{n}{\log n}$.↵
↵
Если мы зафиксируем длину числа $k$, то количество палиндромных чисел такой длины будет порядка $10^{\lfloor \frac{k+1}{2} \rfloor}$. Это $O(\sqrt{n})$.↵
↵
Таким образом, количество простых чисел асимптотически больше количества палиндромных чисел, а значит для любой константы $A$ найдётся ответ. И для такого ответа $A \sim \frac{\sqrt{n}}{\log n}$. В нашем случае $n$ будут не больше $10^{7}$.↵
↵
Поэтому мы можем для всех чисел до $10^{7}$ проверить, являются ли они простыми (с помощью решета Эратосфена), а также являются ли они палиндромными (с помощью наивного алгоритма, или же можно динамикой считать зеркальное отображение числа). Затем мы посчитаем префиксные суммы, а потом линейным поиском найдём ответ.↵
↵
При $A \leq 42$ ответ не превышает $2 \cdot 10^{6}$.↵
↵
Сложность — $O(ans \cdot \log \log ans)$.↵
↵
↵
[problem:568B]↵
↵
Давайте сначала разберёмся, в чем же конкретно неправ Вовочка. В доказательстве хорошо всё, кроме того, что мы сразу взяли $a,b$ такие, что $a \overset{\rho}{\sim} b$. Если такие есть, то действительно $a \overset{\rho}{\sim} a$. А если их нет? Если для $a$ нет такого $b$, что $a \overset{\rho}{\sim} b$, то, очевидно, не $a \overset{\rho}{\sim} a$ (иначе мы бы взяли $b=a$).↵
↵
Отсюда понятно, что наше бинарное отношение — это какое-то отношение эквивалентности, к которому присоединили такие элементы $a$, что для всех них не существует таких $b$, что $a \overset{\rho}{\sim} b$.↵
↵
Тогда решение можно разбить на две части:↵
↵
1. Посчитать количество отношений эквивалентности на множествах размеров $0,1,...,n-1$↵
↵
2. Посчитать, сколькими способами туда можно добавить недостающие "пустые" элементы.↵
↵
Отношение эквивалентности можно задать разбиением на классы эквивалентности.↵
↵
Тогда первую часть задачи можно решить динамическим программированием: $dp[elems][classes]$ — кол-во способов разбить $elems$ первых элементов на $classes$ классов эквивалентности. Переход — каждый элемент мы можем либо отнести в один из уже существующих классов, тогда их количество не изменится, либо же создать новый класс, тогда их количество увеличится на $1$.↵
↵
Вторая часть задачи. Зафиксируем $m$ — размер множества, над которым мы посчитали количество отношений эквивалентности. Тогда нам нужно добавить к нему ещё $n-m$ "пустых" элементов. Позиции для них можно выбрать $C[n][n-m]$ способами, где $C[n][k]$ — биномиальные коэффициенты. Их можно заранее посчитать треугольником Паскаля.↵
↵
Тогда ответ — $\sum_{m=0}^{n-1} C[n][n - m] \cdot eq[m]$.↵
↵
Сложность — $O(n^2)$↵
↵
↵
[problem:568C]↵
↵
Пусть мы зафиксировали буквы на каких-то позициях, как проверить, что на остальные позиции можно расставить буквы так, чтобы получилось слово из языка? Ответ — 2-SAT. Действительно, для каждой позиции есть два взаимоисключающих варианта (гласная и согласная), а правила языка — это импликации. Таким образом, такую проверку мы можем сделать за $O(n+m)$.↵
↵
Будем уменьшать длину префикса, который мы оставляем таким же, как у слова $s$. Тогда следующая буква должна быть строго больше, чем в $s$, а весь дальнейший суффикс может быть любым. Переберём эту букву и проверим с помощью 2-SAT, есть ли решения. Как только мы обнаружили, что решения есть, мы нашли правильный префикс лексиграфически минимального ответа. Затем будем обратно наращивать префикс, какая-то из букв точно подойдёт. Мы получили решение за $O(nm\Sigma )$. $\Sigma$ из решения можно убрать, заметив, что каждый раз нам нужно проверять только минимальные подходящие гласную и согласную буквы.↵
↵
Также нужно не забыть случай, когда все буквы в языке одной гласности.↵
↵
Сложность — $O(nm)$↵
↵
↵
[problem:568D]↵
↵
Предположим, что решение есть. Если $n \leq k$, то мы можем на каждую дорогу поставить по столбу. Иначе рассмотрим любые $k+1$ дорогу. По принципу Дирихле среди них найдутся две, для которых будет общий указатель. Переберём эту пару дорог, поставим столб на их пересечение, уберем дороги, которые тоже проходят через эту точку. Мы свели задачу к меньшему числу столбов. Таким рекурсивным перебором мы решим задачу (если решение существует).↵
↵
Решение это работает за $O(n \cdot \frac{k!(k+1)!}{2^{k}})$. Если написать аккуратно, это может зайти.↵
↵
Но это решение можно ускорить. Заметим, что если у нас есть точка, через которую проходит хотя бы $k+1$ дорога, то мы обязаны поставить столб в эту точку. При достаточно больших $n$ (у меня в решении отсечка $n > 30k^{2}$) такая точка точно есть (если решение существует), причём её можно искать вероятностным алгоритмом. При условии, что решение существует, вероятность, что две произвольные дороги пересекаются в такой точке не меньше $\frac{1}{k}$, поэтому если попробовать $100$ раз, то с вероятностью $\quad 1-10^{-8}$ такая точка найдется, и мы сможем уменьшить $k$.↵
↵
Все проверки можно делать в целых числах.↵
↵
Сложность — $O(nk^{2} + k^{2} \cdot \frac{k!(k+1)!}{2^{k}})$.↵
↵
↵
[problem:568E]↵
↵
Будем поддерживать массив $c$: $c[len]$ — минимальное число, на которое может заканчиваться возрастающая подпоследовательность длины $len$ (Одно из двух стандартных решений задачи о наибольшей возрастающей подпоследовательности). ↵
Элементы этого массива возрастают и добавление очередного элемента $v$ к обработанной части последовательности сводится к нахождению такого $i$, что $c[i] \le v$ и $c[i + 1] \ge v$.↵
При обработке пропуска нам нужно попробовать вставить все числа из множества $b$. Предварительно их отсортировав и двигаясь двумя указателями вдоль массивов $b$ и $c$ мы можем проделать нужные обновления за $O(n + m)$.↵
↵
Авторами подразумевалось использование $O(n)$ памяти для восстановления ответа. Этого можно добиться следующим образом:↵
1. Параллельно с массивом $c$ будем хранить массив $c_index[len]$ — индекс элемента, на который заканчивается оптимальная НВП длины $len$. Если она заканчивается в пропуске — будем хранить, например, $-1$. ↵
2. Также сохраним для каждого не пропуска — длину НВП($lenLIS[pos]$), заканчивающейся в этой позиции (это несложно делается в процессе вычисления массива $c$) и позицию($prevIndex[pos]$) предыдущего элемента в этой НВП (если это пропуск, опять же $-1$).↵
↵
Теперь приступим к восстановлению ответа. Пока мы не наткнулись на пропуск — можно спокойно восстанавливать НВП с конца. Сложность обнаруживается, когда несколько следующих элементов последовательности попали в пропуски. Но можно несложно определить что это за пропуски и чем их заполнить. А именно: пусть сейчас мы стоим в позиции $r$. Нам нужно найти такую позицию $l$ (не пропуск), что мы сможем заполнить ровно $lenLIS[r] - lenLIS[l]$ пропусков между $l$ и $r$ возрастающими числами в интервале $(a[l]..a[r])$. Позицию $l$ можно итеративно перебирать от $r-1$ до $0$, параллельно насчитывая число пройденных пропусков. Проверку условия описанного выше можно несложно сделать с помощью пары бинпоисков.↵
↵
Немного подробнее и с деталями:↵
↵
1. Как узнать, что между позициями $l$ и $r$ можно заполнить пропуски так, чтобы не ухудшить генерируемый ответ? ↵
Пусть $countSkip(l, r)$ — количество пропусков на интервале $(l..r)$, а $countBetween(x, y)$ — количество различных чисел из множества $b$, лежaщих в интервале $(x..y)$. ↵
Тогда позиции $l$ и $r$ хорошие тогда и только тогда, когда $lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r]))$. $countSkip$ можно насчитывать в процессе уменьшения границы $l$, $countBetween(x, y) = max(0, lower\_bound(b, y) - upper\_bound(b, x))$. ↵
↵
2. Что делать, если НВП заканчивается или начинается в пропуске (тогда мы не знаем, откуда начать/где закончить)? ↵
Наиболее простым решением будет добавить $-\infty$ и $+\infty$ в начало и конец нашего массива соответственно. Это позволит избежать проблем с такими крайними случаями.↵
↵
Сложность — $O(n \log n + k(n+m))$ времени, $O(n+m)$ памятиSuppose we have downloaded $S$ seconds of the song and press the 'play' button. Let's find how many seconds will be downloaded when we will be forced to play the song once more. $\frac{x}{q} = \frac{x-S}{q-1}$. Hence $x=qS$.↵
↵
Solution: let's multiply $S$ by $q$ while $S<T$. The answer is the amount of operations.↵
↵
Complexity — $O(\log T)$↵
↵
↵
[problem:569B]↵
↵
Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from $1$ to $n$ and they are must be pairwise distinct. This condition is necessary and sufficient.↵
↵
This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between $1$ and $n$, we will leave this number unchanged. To implement this we can use array where we will mark used numbers.↵
↵
After that we will look over the array again and allocate numbers that weren't used.↵
↵
Complexity — $O(n)$.↵
↵
↵
[problem:568A]↵
↵
It is known that amount of prime numbers non greater than $n$ is about $\frac{n}{\log n}$.↵
↵
We can also found the amount of palindrome numbers with fixed length $k$ — it is about $10^{\lfloor \frac{k+1}{2} \rfloor}$ which is $O(\sqrt{n})$.↵
↵
Therefore the number of primes asymptotically bigger than the number of palindromic numbers and for every constant $A$ there is an answer. Moreover, for this answer $n$ the next condition hold: $A \sim \frac{\sqrt{n}}{\log n}$. In our case $n<10^{7}$.↵
↵
For all numbers smaller than $10^{7}$ we can check if they are primes (via sieve of Eratosthenes) and/or palindromes (via trivial algorithm or compute reverse number via dynamic approach). Then we can calculate prefix sums ($\pi(n)$ and $rub(n)$) and find the answer using linear search.↵
↵
For $A \leq 42$ answer is smaller than $2 \cdot 10^{6}$.↵
↵
Complexity — $O(ans \cdot \log \log ans)$.↵
↵
↵
[problem:568B]↵
↵
Let's find Johnny's mistake. It is all right in his proof except ``If $a \overset{\rho}{\sim} b$'' part. What if there is no such $b$ for an given $a$? Then obviously $a \overset{\rho}{\nsim} a$ otherwise we'll take $b=a$.↵
↵
We can see that our binary relation is some equivalence relation which was expanded by some "empty" elements. For "empty" element $a$ there is no such $b$ that $a \overset{\rho}{\sim} b$.↵
↵
Thus we can divide our solution into two parts:↵
↵
1. Count the number of equivalence relations on sets of size $0,1,...,n-1$↵
↵
2. For every size count the number of ways to expand it with some "empty" elements.↵
↵
We can define equivalence relation using its equivalence classes.↵
↵
So first part can be solved using dynamic programming: $dp[elems][classes]$ — the numbers of ways to divide first $elems$ elements to $classes$ equivalence classes. When we handle next element we can send it to one of the existing equivalence classes or we can create new class.↵
↵
Let's solve second part. Consider set of size $m$. We have found that there are $eq[m]$ ways to build equivalence relation on this set. We have to add $n-m$ "empty" elements to this set. The number of ways to choose their positions is $C_{n}^{k}$. We can calculate all the binomial coefficients using Pascal's triangle.↵
↵
So the answer to the problem is $\sum_{m=0}^{n-1} C[n][n - m] \cdot eq[m]$.↵
↵
Complexity — $O(n^2)$↵
↵
↵
[problem:568C]↵
↵
Suppose we have fixed letters on some positions, how can we check is there a way to select letters on other positions to build a word from the language? The answer is 2-SAT. Let's see: for every position there is two mutually exclusive options (vowel or consonant) and the rules are consequences. Therefore we can do this check in $O(n+m)$ time.↵
↵
Let's decrease the length of the prefix which will be the same as in $s$. Then the next letter must be strictly greater but all the next letters can be any. We can iterate over all greater letters and then check if we can made this word the word from the language (via 2-SAT). Once we have found such possibilty we have found the right prefix of the answer. After that we can increase the length of the fixed prefix in a similar way. This solution works in $O(nm\Sigma )$ time. We can divide this by $\Sigma$ simply try not all the letter but only the smallest possible vowel and the smallest possible consonant.↵
↵
And you should remember about the case when all the letters are vowel (or all the letters are consonant).↵
↵
Complexity — $O(nm)$↵
↵
↵
[problem:568D]↵
↵
Suppose, that solution exist. In case $n \leq k$ we can put one signpost on each road. In other case let's choose any $k+1$ roads. By the Dirichlet's principle there are at least two roads among selected, which have common signpost. Let's simple iterate over all variants with different two roads. After choosing roads $a$ and $b$, we will remove all roads, intersecting with $a$ and $b$ in common points and reduce $k$ in our problem. This recursive process solves the problem (if solution exist).↵
↵
Complexity of this solution — $O(n \cdot \frac{k!(k+1)!}{2^{k}})$. If implement this solution carefully — you will get AC =)↵
↵
But in case of TL we can add one improvement to our solution. Note, that if we find point, which belongs to $k+1$ or more roads, then we must include this point to out answer. For sufficiently large $n$ (for example, if $n > 30k^{2}$) this point always exist and we can find it using randomize algorithm. If solution exist, probability that two arbitrary roads are intersects in such a point not less than $\frac{1}{k}$. Because of it, if we $100$ times pick two random roads, then with probability $\quad 1-10^{-8}$ such a point will be found and we can decrease $k$.↵
↵
All operations better to do in integers.↵
↵
Complexity — $O(nk^{2} + k^{2} \cdot \frac{k!(k+1)!}{2^{k}})$.↵
↵
↵
[problem:568E]↵
↵
Let's calculate array $c$: $c[len]$ — minimal number that can complete ↵
increasing subsequence of length $len$. (This is one of the common solution ↵
for LIS problem).↵
↵
Elements of this array are increasing and we can add new element $v$ to ↵
processed part of sequence as follows:↵
↵
1. find such index $i$ that $c[i] \le v$ and $c[i + 1] \ge v$↵
↵
2. let $c[i + 1] = v$↵
↵
We can process this action in $O(\log n)$ time.↵
↵
When we handle a gap, we must try to insert all numbers from set $b$. If we ↵
sort elements of $b$ in advance, then we can move with two iterators along ↵
arrays $b$ and $c$ and relax all needed values as explained above. This case ↵
requires $O(n + m)$ time.↵
↵
Authors implied solution with $O(n)$ space complexity for answer restoring.↵
We can do this in the following way:↵
↵
1. Together with array $c$ we will store array $c_index[len]$ — index of ↵
element, which complete optimal increasing subsequence of length $len$. If this ↵
subsequence ends in a gap — we will store $-1$.↵
↵
2. Also, we will store for every not gap — length of LIS($lenLIS[pos]$), which ↵
ends in this position (this is simply calculating while processing array $c$) ↵
and position($prevIndex[pos]$) of previous element in this subsequence (if this ↵
elements is gap, we store $-1$)↵
↵
Now we will start recovery the answer with this information.↵
↵
While we are working with not gaps — it's all right. We can simply restore LIS ↵
with $prevIndex[pos]$ array. The main difficulty lies in processing gaps. If ↵
value of $prevIndex[pos]$ in current position equal to $-1$ — we know, that ↵
before this elements must be one or more gaps. And we can determine which gaps ↵
and what values from $b$ we must put in them as follows:↵
↵
Let suppose that we stand at position $r$ (and $prevIndex[r] = -1$). Now we ↵
want to find such position $l$ (which is not gap), that we can fill exactly ↵
$lenLIS[r] - lenLIS[l]$ gaps between $l$ with increasing numbers from interval ↵
$(a[l]..a[r])$. Position $l$ we can simply iterates from $r-1$ to $0$ and with ↵
it calculating gaps between $l$ and $r$. Check the condition described above we ↵
can produce via two binary search query to array $b$.↵
↵
Few details:↵
↵
1. How do we know, that between positions $l$ and $r$ we can fill gaps in ↵
such a way, that out answer still the best? ↵
Let $countSkip(l, r)$ — count gaps on interval $(l..r)$, $countBetween(x, y)$ — ↵
count different numbers from set $b$, lying in the range $(x..y)$. ↵
Then, positions $l$ and $r$ are good only if $ lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r])) $. $countSkip$ we can calculate while iterates position $l$, $countBetween(x, y) = max(0, lower\_bound(b, y) - upper\_bound(b, x))$.↵
↵
2. What to do, is LIS ends or begins in gaps? ↵
This case we can solve by simply adding $-\infty$ and $+\infty$ in begin and ↵
end of out array.↵
↵
Complexity — $O(n \log n + k(n+m))$.↵
Memory — $O(n+m)$.
↵
↵
Тогда решение: будем умножать $S$ на $q$ пока $S<T$. Количество таких умножений — это ответ.↵
↵
Сложность — $O(\log T)$↵
↵
↵
[problem:569B]↵
↵
Подойдём к задаче с другой стороны: а сколько максимально можно оставить номеров, чтобы получилась перестановка? Очевидно, что эти номера должны быть от $1$ до $n$, причем среди них не должно быть повторяющихся. И понятно, что это условие необходимое и достаточное.↵
↵
Такую задачу можно решать жадным алгоритмом. Если мы встретили число, которого ещё не было, при этом оно от $1$ до $n$, то мы его оставим. Для реализации можно завести массив used, в котором отмечать уже использованные числа.↵
↵
Затем нужно ещё раз пройти по массиву и распределить неиспользованные числа.↵
↵
Сложность — $O(n)$.↵
↵
↵
[problem:568A]↵
↵
Известно, что количество простых чисел, не превосходящих $n$, — число порядка $\frac{n}{\log n}$.↵
↵
Если мы зафиксируем длину числа $k$, то количество палиндромных чисел такой длины будет порядка $10^{\lfloor \frac{k+1}{2} \rfloor}$. Это $O(\sqrt{n})$.↵
↵
Таким образом, количество простых чисел асимптотически больше количества палиндромных чисел, а значит для любой константы $A$ найдётся ответ. И для такого ответа $A \sim \frac{\sqrt{n}}{\log n}$. В нашем случае $n$ будут не больше $10^{7}$.↵
↵
Поэтому мы можем для всех чисел до $10^{7}$ проверить, являются ли они простыми (с помощью решета Эратосфена), а также являются ли они палиндромными (с помощью наивного алгоритма, или же можно динамикой считать зеркальное отображение числа). Затем мы посчитаем префиксные суммы, а потом линейным поиском найдём ответ.↵
↵
При $A \leq 42$ ответ не превышает $2 \cdot 10^{6}$.↵
↵
Сложность — $O(ans \cdot \log \log ans)$.↵
↵
↵
[problem:568B]↵
↵
Давайте сначала разберёмся, в чем же конкретно неправ Вовочка. В доказательстве хорошо всё, кроме того, что мы сразу взяли $a,b$ такие, что $a \overset{\rho}{\sim} b$. Если такие есть, то действительно $a \overset{\rho}{\sim} a$. А если их нет? Если для $a$ нет такого $b$, что $a \overset{\rho}{\sim} b$, то, очевидно, не $a \overset{\rho}{\sim} a$ (иначе мы бы взяли $b=a$).↵
↵
Отсюда понятно, что наше бинарное отношение — это какое-то отношение эквивалентности, к которому присоединили такие элементы $a$, что для всех них не существует таких $b$, что $a \overset{\rho}{\sim} b$.↵
↵
Тогда решение можно разбить на две части:↵
↵
1. Посчитать количество отношений эквивалентности на множествах размеров $0,1,...,n-1$↵
↵
2. Посчитать, сколькими способами туда можно добавить недостающие "пустые" элементы.↵
↵
Отношение эквивалентности можно задать разбиением на классы эквивалентности.↵
↵
Тогда первую часть задачи можно решить динамическим программированием: $dp[elems][classes]$ — кол-во способов разбить $elems$ первых элементов на $classes$ классов эквивалентности. Переход — каждый элемент мы можем либо отнести в один из уже существующих классов, тогда их количество не изменится, либо же создать новый класс, тогда их количество увеличится на $1$.↵
↵
Вторая часть задачи. Зафиксируем $m$ — размер множества, над которым мы посчитали количество отношений эквивалентности. Тогда нам нужно добавить к нему ещё $n-m$ "пустых" элементов. Позиции для них можно выбрать $C[n][n-m]$ способами, где $C[n][k]$ — биномиальные коэффициенты. Их можно заранее посчитать треугольником Паскаля.↵
↵
Тогда ответ — $\sum_{m=0}^{n-1} C[n][n - m] \cdot eq[m]$.↵
↵
Сложность — $O(n^2)$↵
↵
↵
[problem:568C]↵
↵
Пусть мы зафиксировали буквы на каких-то позициях, как проверить, что на остальные позиции можно расставить буквы так, чтобы получилось слово из языка? Ответ — 2-SAT. Действительно, для каждой позиции есть два взаимоисключающих варианта (гласная и согласная), а правила языка — это импликации. Таким образом, такую проверку мы можем сделать за $O(n+m)$.↵
↵
Будем уменьшать длину префикса, который мы оставляем таким же, как у слова $s$. Тогда следующая буква должна быть строго больше, чем в $s$, а весь дальнейший суффикс может быть любым. Переберём эту букву и проверим с помощью 2-SAT, есть ли решения. Как только мы обнаружили, что решения есть, мы нашли правильный префикс лексиграфически минимального ответа. Затем будем обратно наращивать префикс, какая-то из букв точно подойдёт. Мы получили решение за $O(nm\Sigma )$. $\Sigma$ из решения можно убрать, заметив, что каждый раз нам нужно проверять только минимальные подходящие гласную и согласную буквы.↵
↵
Также нужно не забыть случай, когда все буквы в языке одной гласности.↵
↵
Сложность — $O(nm)$↵
↵
↵
[problem:568D]↵
↵
Предположим, что решение есть. Если $n \leq k$, то мы можем на каждую дорогу поставить по столбу. Иначе рассмотрим любые $k+1$ дорогу. По принципу Дирихле среди них найдутся две, для которых будет общий указатель. Переберём эту пару дорог, поставим столб на их пересечение, уберем дороги, которые тоже проходят через эту точку. Мы свели задачу к меньшему числу столбов. Таким рекурсивным перебором мы решим задачу (если решение существует).↵
↵
Решение это работает за $O(n \cdot \frac{k!(k+1)!}{2^{k}})$. Если написать аккуратно, это может зайти.↵
↵
Но это решение можно ускорить. Заметим, что если у нас есть точка, через которую проходит хотя бы $k+1$ дорога, то мы обязаны поставить столб в эту точку. При достаточно больших $n$ (у меня в решении отсечка $n > 30k^{2}$) такая точка точно есть (если решение существует), причём её можно искать вероятностным алгоритмом. При условии, что решение существует, вероятность, что две произвольные дороги пересекаются в такой точке не меньше $\frac{1}{k}$, поэтому если попробовать $100$ раз, то с вероятностью $\quad 1-10^{-8}$ такая точка найдется, и мы сможем уменьшить $k$.↵
↵
Все проверки можно делать в целых числах.↵
↵
Сложность — $O(nk^{2} + k^{2} \cdot \frac{k!(k+1)!}{2^{k}})$.↵
↵
↵
[problem:568E]↵
↵
Будем поддерживать массив $c$: $c[len]$ — минимальное число, на которое может заканчиваться возрастающая подпоследовательность длины $len$ (Одно из двух стандартных решений задачи о наибольшей возрастающей подпоследовательности). ↵
Элементы этого массива возрастают и добавление очередного элемента $v$ к обработанной части последовательности сводится к нахождению такого $i$, что $c[i] \le v$ и $c[i + 1] \ge v$.↵
При обработке пропуска нам нужно попробовать вставить все числа из множества $b$. Предварительно их отсортировав и двигаясь двумя указателями вдоль массивов $b$ и $c$ мы можем проделать нужные обновления за $O(n + m)$.↵
↵
Авторами подразумевалось использование $O(n)$ памяти для восстановления ответа. Этого можно добиться следующим образом:↵
1. Параллельно с массивом $c$ будем хранить массив $c_index[len]$ — индекс элемента, на который заканчивается оптимальная НВП длины $len$. Если она заканчивается в пропуске — будем хранить, например, $-1$. ↵
2. Также сохраним для каждого не пропуска — длину НВП($lenLIS[pos]$), заканчивающейся в этой позиции (это несложно делается в процессе вычисления массива $c$) и позицию($prevIndex[pos]$) предыдущего элемента в этой НВП (если это пропуск, опять же $-1$).↵
↵
Теперь приступим к восстановлению ответа. Пока мы не наткнулись на пропуск — можно спокойно восстанавливать НВП с конца. Сложность обнаруживается, когда несколько следующих элементов последовательности попали в пропуски. Но можно несложно определить что это за пропуски и чем их заполнить. А именно: пусть сейчас мы стоим в позиции $r$. Нам нужно найти такую позицию $l$ (не пропуск), что мы сможем заполнить ровно $lenLIS[r] - lenLIS[l]$ пропусков между $l$ и $r$ возрастающими числами в интервале $(a[l]..a[r])$. Позицию $l$ можно итеративно перебирать от $r-1$ до $0$, параллельно насчитывая число пройденных пропусков. Проверку условия описанного выше можно несложно сделать с помощью пары бинпоисков.↵
↵
Немного подробнее и с деталями:↵
↵
1. Как узнать, что между позициями $l$ и $r$ можно заполнить пропуски так, чтобы не ухудшить генерируемый ответ? ↵
Пусть $countSkip(l, r)$ — количество пропусков на интервале $(l..r)$, а $countBetween(x, y)$ — количество различных чисел из множества $b$, лежaщих в интервале $(x..y)$. ↵
Тогда позиции $l$ и $r$ хорошие тогда и только тогда, когда $lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r]))$. $countSkip$ можно насчитывать в процессе уменьшения границы $l$, $countBetween(x, y) = max(0, lower\_bound(b, y) - upper\_bound(b, x))$. ↵
↵
2. Что делать, если НВП заканчивается или начинается в пропуске (тогда мы не знаем, откуда начать/где закончить)? ↵
Наиболее простым решением будет добавить $-\infty$ и $+\infty$ в начало и конец нашего массива соответственно. Это позволит избежать проблем с такими крайними случаями.↵
↵
Сложность — $O(n \log n + k(n+m))$ времени, $O(n+m)$ памяти
↵
Solution: let's multiply $S$ by $q$ while $S<T$. The answer is the amount of operations.↵
↵
Complexity — $O(\log T)$↵
↵
↵
[problem:569B]↵
↵
Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from $1$ to $n$ and they are must be pairwise distinct. This condition is necessary and sufficient.↵
↵
This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between $1$ and $n$, we will leave this number unchanged. To implement this we can use array where we will mark used numbers.↵
↵
After that we will look over the array again and allocate numbers that weren't used.↵
↵
Complexity — $O(n)$.↵
↵
↵
[problem:568A]↵
↵
It is known that amount of prime numbers non greater than $n$ is about $\frac{n}{\log n}$.↵
↵
We can also found the amount of palindrome numbers with fixed length $k$ — it is about $10^{\lfloor \frac{k+1}{2} \rfloor}$ which is $O(\sqrt{n})$.↵
↵
Therefore the number of primes asymptotically bigger than the number of palindromic numbers and for every constant $A$ there is an answer. Moreover, for this answer $n$ the next condition hold: $A \sim \frac{\sqrt{n}}{\log n}$. In our case $n<10^{7}$.↵
↵
For all numbers smaller than $10^{7}$ we can check if they are primes (via sieve of Eratosthenes) and/or palindromes (via trivial algorithm or compute reverse number via dynamic approach). Then we can calculate prefix sums ($\pi(n)$ and $rub(n)$) and find the answer using linear search.↵
↵
For $A \leq 42$ answer is smaller than $2 \cdot 10^{6}$.↵
↵
Complexity — $O(ans \cdot \log \log ans)$.↵
↵
↵
[problem:568B]↵
↵
Let's find Johnny's mistake. It is all right in his proof except ``If $a \overset{\rho}{\sim} b$'' part. What if there is no such $b$ for an given $a$? Then obviously $a \overset{\rho}{\nsim} a$ otherwise we'll take $b=a$.↵
↵
We can see that our binary relation is some equivalence relation which was expanded by some "empty" elements. For "empty" element $a$ there is no such $b$ that $a \overset{\rho}{\sim} b$.↵
↵
Thus we can divide our solution into two parts:↵
↵
1. Count the number of equivalence relations on sets of size $0,1,...,n-1$↵
↵
2. For every size count the number of ways to expand it with some "empty" elements.↵
↵
We can define equivalence relation using its equivalence classes.↵
↵
So first part can be solved using dynamic programming: $dp[elems][classes]$ — the numbers of ways to divide first $elems$ elements to $classes$ equivalence classes. When we handle next element we can send it to one of the existing equivalence classes or we can create new class.↵
↵
Let's solve second part. Consider set of size $m$. We have found that there are $eq[m]$ ways to build equivalence relation on this set. We have to add $n-m$ "empty" elements to this set. The number of ways to choose their positions is $C_{n}^{k}$. We can calculate all the binomial coefficients using Pascal's triangle.↵
↵
So the answer to the problem is $\sum_{m=0}^{n-1} C[n][n - m] \cdot eq[m]$.↵
↵
Complexity — $O(n^2)$↵
↵
↵
[problem:568C]↵
↵
Suppose we have fixed letters on some positions, how can we check is there a way to select letters on other positions to build a word from the language? The answer is 2-SAT. Let's see: for every position there is two mutually exclusive options (vowel or consonant) and the rules are consequences. Therefore we can do this check in $O(n+m)$ time.↵
↵
Let's decrease the length of the prefix which will be the same as in $s$. Then the next letter must be strictly greater but all the next letters can be any. We can iterate over all greater letters and then check if we can made this word the word from the language (via 2-SAT). Once we have found such possibilty we have found the right prefix of the answer. After that we can increase the length of the fixed prefix in a similar way. This solution works in $O(nm\Sigma )$ time. We can divide this by $\Sigma$ simply try not all the letter but only the smallest possible vowel and the smallest possible consonant.↵
↵
And you should remember about the case when all the letters are vowel (or all the letters are consonant).↵
↵
Complexity — $O(nm)$↵
↵
↵
[problem:568D]↵
↵
Suppose, that solution exist. In case $n \leq k$ we can put one signpost on each road. In other case let's choose any $k+1$ roads. By the Dirichlet's principle there are at least two roads among selected, which have common signpost. Let's simple iterate over all variants with different two roads. After choosing roads $a$ and $b$, we will remove all roads, intersecting with $a$ and $b$ in common points and reduce $k$ in our problem. This recursive process solves the problem (if solution exist).↵
↵
Complexity of this solution — $O(n \cdot \frac{k!(k+1)!}{2^{k}})$. If implement this solution carefully — you will get AC =)↵
↵
But in case of TL we can add one improvement to our solution. Note, that if we find point, which belongs to $k+1$ or more roads, then we must include this point to out answer. For sufficiently large $n$ (for example, if $n > 30k^{2}$) this point always exist and we can find it using randomize algorithm. If solution exist, probability that two arbitrary roads are intersects in such a point not less than $\frac{1}{k}$. Because of it, if we $100$ times pick two random roads, then with probability $\quad 1-10^{-8}$ such a point will be found and we can decrease $k$.↵
↵
All operations better to do in integers.↵
↵
Complexity — $O(nk^{2} + k^{2} \cdot \frac{k!(k+1)!}{2^{k}})$.↵
↵
↵
[problem:568E]↵
↵
Let's calculate array $c$: $c[len]$ — minimal number that can complete ↵
increasing subsequence of length $len$. (This is one of the common solution ↵
for LIS problem).↵
↵
Elements of this array are increasing and we can add new element $v$ to ↵
processed part of sequence as follows:↵
↵
1. find such index $i$ that $c[i] \le v$ and $c[i + 1] \ge v$↵
↵
2. let $c[i + 1] = v$↵
↵
We can process this action in $O(\log n)$ time.↵
↵
When we handle a gap, we must try to insert all numbers from set $b$. If we ↵
sort elements of $b$ in advance, then we can move with two iterators along ↵
arrays $b$ and $c$ and relax all needed values as explained above. This case ↵
requires $O(n + m)$ time.↵
↵
Authors implied solution with $O(n)$ space complexity for answer restoring.↵
We can do this in the following way:↵
↵
1. Together with array $c$ we will store array $c_index[len]$ — index of ↵
element, which complete optimal increasing subsequence of length $len$. If this ↵
subsequence ends in a gap — we will store $-1$.↵
↵
2. Also, we will store for every not gap — length of LIS($lenLIS[pos]$), which ↵
ends in this position (this is simply calculating while processing array $c$) ↵
and position($prevIndex[pos]$) of previous element in this subsequence (if this ↵
elements is gap, we store $-1$)↵
↵
Now we will start recovery the answer with this information.↵
↵
While we are working with not gaps — it's all right. We can simply restore LIS ↵
with $prevIndex[pos]$ array. The main difficulty lies in processing gaps. If ↵
value of $prevIndex[pos]$ in current position equal to $-1$ — we know, that ↵
before this elements must be one or more gaps. And we can determine which gaps ↵
and what values from $b$ we must put in them as follows:↵
↵
Let suppose that we stand at position $r$ (and $prevIndex[r] = -1$). Now we ↵
want to find such position $l$ (which is not gap), that we can fill exactly ↵
$lenLIS[r] - lenLIS[l]$ gaps between $l$ with increasing numbers from interval ↵
$(a[l]..a[r])$. Position $l$ we can simply iterates from $r-1$ to $0$ and with ↵
it calculating gaps between $l$ and $r$. Check the condition described above we ↵
can produce via two binary search query to array $b$.↵
↵
Few details:↵
↵
1. How do we know, that between positions $l$ and $r$ we can fill gaps in ↵
such a way, that out answer still the best? ↵
Let $countSkip(l, r)$ — count gaps on interval $(l..r)$, $countBetween(x, y)$ — ↵
count different numbers from set $b$, lying in the range $(x..y)$. ↵
Then, positions $l$ and $r$ are good only if $ lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r])) $. $countSkip$ we can calculate while iterates position $l$, $countBetween(x, y) = max(0, lower\_bound(b, y) - upper\_bound(b, x))$.↵
↵
2. What to do, is LIS ends or begins in gaps? ↵
This case we can solve by simply adding $-\infty$ and $+\infty$ in begin and ↵
end of out array.↵
↵
Complexity — $O(n \log n + k(n+m))$.↵
Memory — $O(n+m)$.
