Codeforces Round #818 (Div. 2) Разбор.
Difference between ru5 and en1, changed 6,610 character(s)
Задача A. ИдеяProblem A. Idea by [user:Igorbunov,2022-09-02]↵

<spoiler summary="Hint 1">↵
У нас могут быть только следующие пары чиселOnly the following pairs of numbers are possible: $(x, x)$, $(x, 2 \cdot x)$, and $(x, 3 \cdot x)$↵
</spoiler>↵

<spoiler summary="
Решение">↵
Давайте заметим, что у нас могут быть только следующие пары чисел
Solution">↵
Notice that only the following pairs of numbers are possible
: $(x, x)$, $(x, 2 \cdot x)$, and $(x, 3 \cdot x)$. 

<spoiler summary="
Доказательство:">↵
Пусть $d = gcd(a, b)$, тогда заметим, что не может быть
Proof:">↵
Let $d = gcd(a, b)$. Now notice that it's impossible that
 $a = k \cdot d$, где for some $k > 4$, так как иначе $lcm$ точно будет не меньше $k \cdot d > 3 \cdot d$. Тогда остается только варианты выше, а также $(2 \cdot d, 3 \cdot d)$. Но в этом случае $lcm = 6 \cdot d$.↵
</spoiler>↵

Количество первого типа $n$, второго
because otherwise $lcm$ will be at least $k \cdot d > 3 \cdot d$. Therefore the only possible cases are the pairs listed above and $(2 \cdot d, 3 \cdot d)$, but in the latter case we have $lcm = 6 \cdot d$.↵
</spoiler>↵

The number of the pairs of the first kind is $n$, of the second kind is
 $\lfloor \frac{n}{2} \rfloor$, третьегоand of the third kind is $\lfloor \frac{n}{3} \rfloor$. А значит ответ на задачу равенTherefore, the answer to the problem is $n + \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor$.↵
</spoiler>↵

------------------------------↵

Задача B. ИдеяProblem B. Idea by [user:FairyWinx,2022-09-02]↵

<spoiler summary="Hint 1">↵
Решите эту задачу дляSolve the problem for $k = 2$.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
Решите задачу, когда нет ограничения на закрашенную клетку.↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Попытайтесь закрашивать клетки по диагоналям.
Solve the problem without the "$(r, c)$ must be colored" limitation.↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Try to paint diagonals

</spoiler>↵

<spoiler summary="Hint 4">↵
Если в вашем коде много строчек не пишите)↵
</spoiler>↵

<spoiler summary="Решение">↵

Давайте заметим, что ответ на задачу не меньше $\frac{n^2}{k}$, так как квадрат можно разбить на непересекающиеся подпрямоугольники размера $1 \times k$. Значит нужно научиться делать пример на это число.↵

Решим вначале задачу, без ограничения на закрашенную клетку. Тогда нам хочется сделать что-то типа шахматной расскраски, то есть диаганальную раскраску.↵

В этом случае, мы можем пронумеравать диаганали (от самой "нижней", до самой "верхней"). В этом случае в каждом подпрямоугольнике будет $k$ подряд идущих диагоналей, а значит, если закрасить каждую $k$ диаганаль, то мы получим ответ на задачу (и ответ в точности будет равен $\frac{n^2}{k}$, так как в каждом подпрямоугольнике мы закрасили ровно одну клетку).↵

Ну а можно заметить, что клетка
No, you don't need casework↵
</spoiler>↵

<spoiler summary="Solution">↵
Notice that the answer to the problem is at least $\frac{n^2}{k}$, because you can split the square into so many non-intersecting rectangles of dimensions $1 \times k$. So let's try to paint exactly so many cells and see if maybe it's always possible.↵

For simplicity, let's first solve the problem without necessarily painting $(r, c)$. In this case, we're looking for something like a chess coloring, which is a diagonal coloring.↵

Let's number the diagonals from the "lowest" to the "highest". Notice that every $1 \times k$ and $k \times 1$ subrectangle intersects exactly $k$ consecutive diagonals, so we can paint every $k$-th diagonal to obtain the required answer: every such subrectangle will contain exactly one painted cell.↵

To add the $(r, c)$ requirement back, notice that
 $(xryc)$ принадлежит диагонале с номеромlies on the diagonal number $xr + yc$. (Так как когда мы идем на одну клетку вверх-влево, то одна из координат увеличивается на 1, а другая не меняется). А значит, нужно просто закрасить все клетки, у которыхBecause if you trace any path from $(0, 0)$ to $(r, c)$ with non-decreasing coordinates, going one cell upwards or rightwards increases exactly one of the coordinates by one, and also increases the number of the diagonal by one). Therefore, all we need to do is paint the cells whose coordinates satisfy $(x + y) \% k = (ar + bc) \% k$↵

</spoiler>↵

------------------------------↵

Задача C. ИдеяProblem C. Idea by [user:FairyWinx,2022-09-02]↵

<spoiler summary="Hint 1">↵
ЕслиWe've got a problem if $b_{i} \ge b_{i + 1} + 1$, то могут быть проблемы
</spoiler>↵

<spoiler summary="Hint 2">↵
Все нормально, еслиIt's alright if $a_i = b_i$↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Программист не математик, можно не доказывать решение.↵
</spoiler>↵

<spoiler summary="Решение">↵
Очевидно, что для любого $i$ должно выполняться, что либо $a_i = b_i$, либо $b_i \leq b_{i + 1} + 1$, так как либо $a_i$ уже равно $b_i$ и $i$ элемент увеличивать не нужно, либо же мы должны увеличить $a_i$ до $b_i$ операциями из условия, а на них накладываются ограничения выше.↵

Теперь докажем, что этих двух условий достаточно. Пусть $i$ &mdash; это индекс минимального элемента в $a$, который не равен $b_i$. Тогда заметим, что мы в любом случае сможем сделать $a_i := a_i+1$, так как в этом случае выполняется $a_i \leq b_i \leq b_{i + 1} + 1$, а значит можно увеличить $a_i$. То есть такими операциями можно получить массив $b$.↵
</spoiler>↵

-------------------------------↵

Задача D. Идея [user:FairyWinx,2022-09-02]↵

<spoiler summary="Hint 1">↵
Переформулируйте чуть лучше задачу в терминах полного бинарного дерева.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
Странно на одной и той же глубине делать два изменения.↵
</spoiler>↵

<spoiler summary="Решение">↵

Давайте поймем, что задачу можно переформулировать следующим образом: Дано полное бинарное дерево с $2^n$ листами. Также для каждой вершины, не являющейся листом, помечено ребро в ровно одного из детей. А ответ на задачу &mdash; это лист, до которого можно добраться из корня по отмеченным ребрам. А изменения &mdash; это сменить помеченное ребро выходящее из вершины.↵

Тогда понятно, что нет смысла делать изменения больше, чем у одной вершины на уровне, так как нам важна только одна вершина, до которой идет путь, а значит ответ зависит только от того, на каких глубинах мы решили поменять исход (и очевидно, что разные множества изменненых исходов дают разного победителя). А значит если $k$ фиксированно &mdash; $\binom{n}{k}$ (так как нам нужно просто выбрать, какие из $k$ глубин мы будем изменять), а значит ответ на задачу равен $\sum{\binom{n}{i}}$, где $0 \leq k \leq min(n, k)$
Programmer aren't mathematicians, you don't need to prove the solution↵
</spoiler>↵

<spoiler summary="Solution">↵
Firstly, we obviously require $a_i \le b_i$ to hold for all $i$. With that out of our way, let's consider non-trivial cases. Also let $a_{n+1} = a_1, b_{n+1} = b_1$ cyclically.↵

For each $i$, we require that either $a_i = b_i$ or $b_i \leq b_{i + 1} + 1$ holds. That's because if we increment $a_i$ at least once, we had $a_i = b_i - 1$ and $a_{i + 1} \le b_{i + 1}$ before the last increment of $a_i$, and from here it's just a matter of simple algebraic transformations.↵

Now let's prove these two conditions are enough. Let $i$ be the index of the minimal element of $a$ such that $a_i < b_i$ (i.e. the smallest element that's not ready yet). Notice that in this case we can, in fact, assign $a_i := a_i+1$, because $a_i \leq b_i \leq b_{i + 1} + 1$ holds, and now we're one step closer to the required array. It's easy to continue this proof by induction.↵
</spoiler>↵

-------------------------------↵

Problem D. Idea by [user:FairyWinx,2022-09-02]↵

<spoiler summary="Hint 1">↵
Reformulate this problem in terms of a complete binary tree.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
It would be strange for the sponsors to changes two nodes of the same depth.↵
</spoiler>↵

<spoiler summary="Solution">↵
The problem can be reformulated as follows. We've got a complete binary tree with $2^n$ leaves. There's a marked edge from each intermediate node to one of its children. The winner is the leaf reachable from the root via marked edges. Changes modify the outgoing marked edge of a node.↵

Now it should be fairly obvious that there's no reason to change more than one node per level, because only one node matters per level--the one on the path from the root to the answer node. So, the winner only depends on the subset of levels we perform changes on, and vice versa: different subsets always yield different winners.↵

Sponsors can change exactly $i$ nodes in $\bimom{n}{i}$ ways. Summing this over $i$, we get $\sum_{i=0}^{\min(n, k)} \binom{n}{i}$. Call this number $m$. $m$ is the number of winners the sponsors choose between--let's call them candidates for brevity. It's easy to see that $m$ is the answer to the problem, because a) sponsors can guarantee the winner is at least $m$, as, independent of the list of candidate winners "provided" by Madoka, at least one of them must be at least $m$, and b) Madoka can guarantee the winner is at most $m$ by firstly marking edges arbitrarily, *then* computing the list of candidate nodes, and only *then* fill them with numbers from $1$ to $m$ (and the other nodes arbitrarily)
.↵
</spoiler>↵

---------------------------------------↵

Задача E. ИдеяProblem E. Idea by [user:FairyWinx,2022-09-02]↵

<spoiler summary="Hint 1">↵
ПеребиритеBruteforce $c$↵
</spoiler>↵

<spoiler summary="Hint 2">↵
$gcd(a, b)$ 
является делителем числа $a + b$.↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Вспомните о существовании функции эйлера↵
</spoiler>↵

<spoiler summary="Решение">↵
Давайте будем перебирать $c$, тогда $gcd(a, b) = gcd(a, a + b) = gcd(a, n - c)$. Значит $gcd(a, b)$ являются делителем числа $n - c$. Давайте тогда переберем все делители числа $n - c$. Пусть $d$ является делителем, тогда количество пар чисел $a, b$, где $a + b = n - c$ и $gcd(a, b) = d$ равно $\phi (\frac{n - c}{d})$, так как нам нужно $a$ кратное $d$ и при этом оно должно быть простым с $\frac{n - c}{d}$, чтобы $gcd$ был в точности равен $d$.↵

А значит ответ на задачу равен $\sum{lcm(c, d) * \phi{\frac{n - c}{d}}}$, где $1 \leq c \leq n - 2$, а $d$ делит $n - c$
divides $a + b$.↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Recall the existence of the Euler's totient function↵
</spoiler>↵

<spoiler summary="Solution">↵
Let's bruteforce $c$, then we have $gcd(a, b) = gcd(a, a + b) = gcd(a, n - c)$. This means that $gcd(a, b)$ divides $n - c$, so let's just go through all divisors of $n - c$. For every factor $d$, the count of pairs $(a, b)$ satisfying $a + b = n - c$ and $gcd(a, b) = d$ is $\phi (\frac{n - c}{d})$, because we need $d$ to divide $a$ and be coprime with $\frac{n - c}{d}$, so that the $gcd$ is equal to $d$.↵

Therefore, the answer to the problem is $\sum{lcm(c, d) * \phi{\frac{n - c}{d}}}$, where $1 \leq c \leq n - 2$ and $d$ is a factor of $n - c$.

</spoiler>↵


---------------------------------------↵

Задача F. ИдеяProblem F. Idea by [user:TeaTime,2022-09-02]↵

Coming soon↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru7 Russian purplesyringa 2022-09-05 00:03:30 93
en10 English purplesyringa 2022-09-04 20:19:39 7 Tiny change: 'ities in two cases:\n\' -> 'ities in three cases:\n\'
en9 English purplesyringa 2022-09-04 20:17:18 876 Add a note on Edmonds-Karp's algorithm usage in F
en8 English purplesyringa 2022-09-04 20:10:19 1391 Fix invalid complexity proof in F
en7 English purplesyringa 2022-09-03 22:16:18 1 Tiny change: 'Programmer aren't ma' -> 'Programmers aren't ma'
en6 English purplesyringa 2022-09-03 12:30:18 1213
ru6 Russian purplesyringa 2022-09-03 02:25:30 44 Fix a bug in A and a typo in C hint
en5 English purplesyringa 2022-09-03 02:24:45 132 Fix a bug in A and a typo in C hint
en4 English purplesyringa 2022-09-03 02:20:53 3540 Add problem F tutorial
en3 English FairyWinx 2022-09-03 01:20:53 2 Tiny change: 'es in $\bimom{n}{i}$ ' -> 'es in $\binom{n}{i}$ '
en2 English FairyWinx 2022-09-03 01:03:05 15
en1 English purplesyringa 2022-09-03 01:01:01 6610 Add English translation
ru5 Russian FairyWinx 2022-09-02 22:27:39 1717 (опубликовано)
ru4 Russian FairyWinx 2022-09-02 17:22:43 0 Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
ru3 Russian FairyWinx 2022-09-02 14:11:01 0 Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
ru2 Russian FairyWinx 2022-09-02 12:18:37 3 Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
ru1 Russian FairyWinx 2022-09-02 12:17:57 4008 Первая редакция (сохранено в черновиках)