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="Proof:">↵
Let $d = gcd(a, b)$. Now notice that it's impossible that $a = k \cdot d$ for some $k > 4$, 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>↵
↵
------------------------------↵
↵
Problem B. Idea by [user:FairyWinx,2022-09-02]↵
↵
<spoiler summary="Hint 1">↵
Solve the problem for $k = 2$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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">↵
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 $(r, c)$ lies on the diagonal number $r + c$. (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 = (r + c) \% k$↵
↵
</spoiler>↵
↵
------------------------------↵
↵
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">↵
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 $\binom{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>↵
↵
---------------------------------------↵
↵
Problem E. Idea by [user:FairyWinx,2022-09-02]↵
↵
<spoiler summary="Hint 1">↵
Bruteforce $c$↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
$gcd(a, b)$ 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>↵
↵
↵
---------------------------------------↵
↵
Problem F. Idea by [user:TeaTime,2022-09-02]↵
↵
Coming soon, tutorial by [user:imachug,2022-09-03]↵
↵
Editorialist's note: I didn't submit the solution myself, but I proved it theoretically, aggregated solutions of problemsetters as well as participants, so I'm fairly sure it's correct, but you might want to treat it with more suspicion.↵
↵
<spoiler summary="Hint 1">↵
Try graph theory.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try flow theory.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
No, that won't work, try again.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Let's reformulate the problem in terms of graphs. We are given an undirected graph and we are asked to determine edge directions, subject to fixed indegree minus outdegree (hereinafter *balance*) values for some vertices. ↵
↵
It is tempting to think of this as a flow problem: edges indicate pipes with capacity of 1, vertices are producers or consumers of flow, and vertices with fixed differencies produce or consume an exact amount of flow. Except that's not quite an equivalent problem: a maxflow algorithm will find a flow, i.e. an orientation of edges, but it might just ignore some edges if it feels like it.↵
↵
We need to overcome this somehow by introducing incentive to use all edges. To do this, forget about the "edges are edges, vertices are vertices" idea for a while. Create an imaginary source and add a pipe with capacity 1 to every edge of the original graph. Technically, this is interpreting edges of the original graph as vertices of the flow graph. Non-technically, I like to interpret this like magically spawning flow into the middle of the edge.↵
↵
Now, the flow appearing in the edge has to actually go somewhere if we want the maxflow algorithm to treat it like a treasure it wants to increase. Let's just add two pipes: from the edge to vertex $u_i$ and from the edge to vertex $v_i$, because where else would it go? (technically, any capacity works, but let's use 1 for simplicity) This has a nice side effect of determining the orientation of the edge: if the flow from the edge goes into $u_i$, it's as if it was oriented from $v_i$ to $u_i$, and vice versa.↵
↵
A small problem is that this changes the semantics of the edge orientation somewhat. In the original problem, $u_i \to v_i$ incremented $v_i$ and decremented $u_i$. In the new formulation, only $v_i$ is incremented, so we need to transform the requirements $a_v$ on balances into requirements $b_v$ on indegrees: $b_v = \frac{a_v + \mathrm{deg} v}{2}$ (and we need to check that the numerator is even and non-negative, otherwise the answer is NO).↵
↵
How do we enforce the indegree requirements? Easy: for all vertices with $s_v = 1$, add a pipe from the vertex $v$ to an imaginary sink with capacity $b_v$, and for all vertices with $s_v = 0$, add a pipe from the vertex $v$ to an imaginary sink with capacity $\infty$.↵
↵
Run a maxflow algorithm. Check that every pipe from the source to an edge and every pipe with non-infinite capacity from a vertex to the sink is satiated. If this does not hold, the answer is NO. If this holds, the answer is YES and the edge orientation can be restored by checking which of the two pipes from an edge is satiated.↵
↵
Is this fast? That depends on the algorithm heavily, but if you use Dinic's algorithm, you might've heard it works in $\mathcal{O}(M \sqrt{P})$, where $M$ is the number of pipes ($n + m$ in our case) and $P$ is the sum of $\min(incap_v, outcap_v)$ for each vertex, which is $\mathcal{O}(m)$ in our case, so the resulting complexity is $\mathcal{O}(m \sqrt{m})$, which is good enough.↵
</spoiler>↵
↵
↵
<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="Proof:">↵
Let $d = gcd(a, b)$. Now notice that it's impossible that $a = k \cdot d$ for some $k > 4$, 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>↵
↵
------------------------------↵
↵
Problem B. Idea by [user:FairyWinx,2022-09-02]↵
↵
<spoiler summary="Hint 1">↵
Solve the problem for $k = 2$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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">↵
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 $(r, c)$ lies on the diagonal number $r + c$. (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 = (r + c) \% k$↵
↵
</spoiler>↵
↵
------------------------------↵
↵
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">↵
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 $\binom{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>↵
↵
---------------------------------------↵
↵
Problem E. Idea by [user:FairyWinx,2022-09-02]↵
↵
<spoiler summary="Hint 1">↵
Bruteforce $c$↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
$gcd(a, b)$ 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>↵
↵
↵
---------------------------------------↵
↵
Problem F. Idea by [user:TeaTime,2022-09-02]
↵
Coming soon
↵
Editorialist's note: I didn't submit the solution myself, but I proved it theoretically, aggregated solutions of problemsetters as well as participants, so I'm fairly sure it's correct, but you might want to treat it with more suspicion.↵
↵
<spoiler summary="Hint 1">↵
Try graph theory.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try flow theory.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
No, that won't work, try again.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Let's reformulate the problem in terms of graphs. We are given an undirected graph and we are asked to determine edge directions, subject to fixed indegree minus outdegree (hereinafter *balance*) values for some vertices. ↵
↵
It is tempting to think of this as a flow problem: edges indicate pipes with capacity of 1, vertices are producers or consumers of flow, and vertices with fixed differencies produce or consume an exact amount of flow. Except that's not quite an equivalent problem: a maxflow algorithm will find a flow, i.e. an orientation of edges, but it might just ignore some edges if it feels like it.↵
↵
We need to overcome this somehow by introducing incentive to use all edges. To do this, forget about the "edges are edges, vertices are vertices" idea for a while. Create an imaginary source and add a pipe with capacity 1 to every edge of the original graph. Technically, this is interpreting edges of the original graph as vertices of the flow graph. Non-technically, I like to interpret this like magically spawning flow into the middle of the edge.↵
↵
Now, the flow appearing in the edge has to actually go somewhere if we want the maxflow algorithm to treat it like a treasure it wants to increase. Let's just add two pipes: from the edge to vertex $u_i$ and from the edge to vertex $v_i$, because where else would it go? (technically, any capacity works, but let's use 1 for simplicity) This has a nice side effect of determining the orientation of the edge: if the flow from the edge goes into $u_i$, it's as if it was oriented from $v_i$ to $u_i$, and vice versa.↵
↵
A small problem is that this changes the semantics of the edge orientation somewhat. In the original problem, $u_i \to v_i$ incremented $v_i$ and decremented $u_i$. In the new formulation, only $v_i$ is incremented, so we need to transform the requirements $a_v$ on balances into requirements $b_v$ on indegrees: $b_v = \frac{a_v + \mathrm{deg} v}{2}$ (and we need to check that the numerator is even and non-negative, otherwise the answer is NO).↵
↵
How do we enforce the indegree requirements? Easy: for all vertices with $s_v = 1$, add a pipe from the vertex $v$ to an imaginary sink with capacity $b_v$, and for all vertices with $s_v = 0$, add a pipe from the vertex $v$ to an imaginary sink with capacity $\infty$.↵
↵
Run a maxflow algorithm. Check that every pipe from the source to an edge and every pipe with non-infinite capacity from a vertex to the sink is satiated. If this does not hold, the answer is NO. If this holds, the answer is YES and the edge orientation can be restored by checking which of the two pipes from an edge is satiated.↵
↵
Is this fast? That depends on the algorithm heavily, but if you use Dinic's algorithm, you might've heard it works in $\mathcal{O}(M \sqrt{P})$, where $M$ is the number of pipes ($n + m$ in our case) and $P$ is the sum of $\min(incap_v, outcap_v)$ for each vertex, which is $\mathcal{O}(m)$ in our case, so the resulting complexity is $\mathcal{O}(m \sqrt{m})$, which is good enough.↵
</spoiler>↵
↵
