Since AtCoder often doesn't release English editorials to their beginner contests, I thought I'd write up my solutions. Feel free to add a comment if anything was unclear!↵
↵
A — T or T↵
------------------↵
Our alternatives here are sending all $N$ people on the train, for a total of $N \cdot A$ yen, or using the taxi, for a total of $B$ yen. We should thus print the minimum of these two values. ↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6265526↵
↵
B — Good Distance↵
------------------↵
We reword the problem slightly: for how many points $y$ and $z$ is $\sum_{k=1}^D (y_i-z_i)^2$ a perfect square?↵
↵
Given the small input constraints, we know that this sum is going to be at most $10 \cdot (20-20)^2 = 16000$. Hence, we can simply compute a list of all perfect squares less than $16000$ and iterate over all $\dbinom{N}{2}$ pairs of points. For each pair of points, we compute the summation and check if it is equal to any of our squares. If so, we increment the answer. With about $125$ perfect squares less than $16000$, this takes roughly $125 \cdot \dbinom{10}{2}$ operations, which comes in well under the time limit.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6268768↵
↵
C — Remainder Minimization 2019↵
------------------↵
We start with an observation: if there is a multiple of $2019$ in the range $[L, R]$, the answer is 0, as we can simply take that multiple as one of $i$ or $j$ and any other value in the range as our other variable.↵
↵
We first check whether this is the case. Iterating over every value from $L$ to $R$ would be too slow, so instead, we simply check whether $\frac{L-1}{2019}$ is different from $\frac{R}{2019}$, using integer division. In this case, there must be some multiple of $2019$ in our range. If the two values are the same, we know there is no multiple of $2019$ in the range.↵
↵
In the latter case, we have a range of length at most $2018$, so an $O((R-L)^2)$ solution is good enough now. We can thus iterate over every pair of values from L to R and select whichever gives us the minimum value for the desired remainder.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6273254↵
↵
D — Rain Flows into Dams ↵
------------------↵
We are essentially solving a system of equations here. Suppose that mountain $i$ receives $2x_i$ liters of rainwater. Then, for each dam $i$, we know that $A_i = x_i + x_{i+1}$, where $x_{N+1} = x_1.$↵
↵
We start by solving for $x_1$. Since $A_1 = x_1 + x_2$, we have $x_2 = A_1 - x_1$. Then, similarly, $x_3 = A_2 - A_1 + x_1$. We notice a pattern: $x_5 = A_4 - A_3 + A_2 - A_1 + x_1$, and in general, for any odd $i$, $x_i = x_1 + \sum_{k=1}^{i-1} A_k \cdot (-1)^k.$ More simply, to compute $x_N$, we simply add the even $A_i$ and subtract the odd $A_i$ to and from $x_1$.↵
↵
We thus have from our equation for dam $N$ that $2x_1 + \sum_{k=1}^{N-1} A_k \cdot (-1)^k = A_N$. We can compute this sum in $O(N)$ and use it to solve for $x_1$. From there, we can substitute this into the equation for dam $1$ to get a value for $x_2$, and we can substitute that into equation two to solve for $x_3$, and so on. Then, we multiply these values by two and print them.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6272209↵
↵
E — Virus Tree 2↵
------------------↵
We build the tree from the top down. Root the tree arbitrarily; we have $K$ choices for the root. Then, we do DFS. In each step of our DFS, we count the number of ways to assign colors to the current node's children and then run our DFS process on each of those children.↵
↵
To count the number of ways to assign colors to a node's children, note that each child must have a different color and those colors must be different from the current node's color and the parent node's color (since the current node's parent has distance two from the current node's children). Thus, we start with $K-1$ colors available for the children of the root or $K-2$ colors available for the children of any other node. Then, once we pick a color for a node, we have one fewer color option than we did before. If we have $x$ children of a node that isn't the root, we can thus express the number of ways to pick their colors as follows:↵
↵
↵
$$\prod_{i=0}^{x-1} K-2-i$$↵
↵
The case for the root works similarly, except we use $K-1$ instead of $K-2$. The answer is then the product of these values over all of the parent nodes, since we need to assign colors to each of the children.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6275812↵
↵
F — Colorful Tree↵
------------------↵
↵
The core idea is LCA with square-root decomposition. First, we figure out how we'll eventually want to answer queries. Note that within a tree, the distance between A and B, if these two nodes have C as their LCA, is equal to $dist(A, root) + dist(B, root) - 2 \cdot dist(C, root).$ Therefore, we now need to efficiently compute distances between nodes and the root.↵
↵
Now, suppose the distance from a node $A$ to the root is $D$ initially. However, suppose that we're changing the lengths of all edges with color $c$ to $d$, and there are currently $x$ nodes of color $c$ on this path with total length $y$. Then, we can see that the distance after this change is $D - y + x \cdot d.$ We now need to efficiently compute $x$ and $y$.↵
↵
To compute these values of $x$ and $y$, we call certain nodes "special" and record the values of $x$ and $y$ for all colors at those nodes. Then, to compute $x$ and $y$ for a certain node and color, we repeatedly move from that node to its parent, incrementing $x$ and $y$ if we reach an edge of our desired color, until we reach a special node, at which point we add that node's $x$ and $y$ to our sum and return it.↵
↵
The key insight is that we can pick the special nodes so that we can both compute the $x$ and $y$-values for the special nodes quickly and reach a special node from any regular node by climbing up the tree in relatively few steps.↵
↵
To do so, we select the special nodes as follows. Sort the nodes in decreasing order of depth. Then, for each node, we move up $\sqrt{N}$ levels in the tree. If we don't find a special node in this process, make the node $\sqrt{N}$ levels above this node special.↵
↵
Obviously, this guarantees that we will only need to move up at most $\sqrt{N}$ steps to find a special node from any regular node. However, we also can prove that this gives us only $O(\sqrt{N})$ special nodes, allowing us to compute them and their $x$ and $y$-values efficiently. Any node up at least $\sqrt{N}$ levels in the tree must obviously have at least $\sqrt{N}$ nodes in its subtree, and because of the order in which we process the nodes, each new special node we add gives at least $\sqrt{N}$ nodes access to a special node that did not have it already. Therefore, we will have at most $\frac{N}{\sqrt{N}} = \sqrt{N}$ special nodes in total.↵
↵
We can thus compute the special nodes and their $x/y$-values in $O(N\sqrt{N})$, and for each query, we take $O(\sqrt{N})$ steps to move upwards and find a special node. Therefore, our total complexity is $O((N+Q)\sqrt{N})$, which passes in time.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6290486
↵
A — T or T↵
------------------↵
Our alternatives here are sending all $N$ people on the train, for a total of $N \cdot A$ yen, or using the taxi, for a total of $B$ yen. We should thus print the minimum of these two values. ↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6265526↵
↵
B — Good Distance↵
------------------↵
We reword the problem slightly: for how many points $y$ and $z$ is $\sum_{k=1}^D (y_i-z_i)^2$ a perfect square?↵
↵
Given the small input constraints, we know that this sum is going to be at most $10 \cdot (20-20)^2 = 16000$. Hence, we can simply compute a list of all perfect squares less than $16000$ and iterate over all $\dbinom{N}{2}$ pairs of points. For each pair of points, we compute the summation and check if it is equal to any of our squares. If so, we increment the answer. With about $125$ perfect squares less than $16000$, this takes roughly $125 \cdot \dbinom{10}{2}$ operations, which comes in well under the time limit.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6268768↵
↵
C — Remainder Minimization 2019↵
------------------↵
We start with an observation: if there is a multiple of $2019$ in the range $[L, R]$, the answer is 0, as we can simply take that multiple as one of $i$ or $j$ and any other value in the range as our other variable.↵
↵
We first check whether this is the case. Iterating over every value from $L$ to $R$ would be too slow, so instead, we simply check whether $\frac{L-1}{2019}$ is different from $\frac{R}{2019}$, using integer division. In this case, there must be some multiple of $2019$ in our range. If the two values are the same, we know there is no multiple of $2019$ in the range.↵
↵
In the latter case, we have a range of length at most $2018$, so an $O((R-L)^2)$ solution is good enough now. We can thus iterate over every pair of values from L to R and select whichever gives us the minimum value for the desired remainder.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6273254↵
↵
D — Rain Flows into Dams ↵
------------------↵
We are essentially solving a system of equations here. Suppose that mountain $i$ receives $2x_i$ liters of rainwater. Then, for each dam $i$, we know that $A_i = x_i + x_{i+1}$, where $x_{N+1} = x_1.$↵
↵
We start by solving for $x_1$. Since $A_1 = x_1 + x_2$, we have $x_2 = A_1 - x_1$. Then, similarly, $x_3 = A_2 - A_1 + x_1$. We notice a pattern: $x_5 = A_4 - A_3 + A_2 - A_1 + x_1$, and in general, for any odd $i$, $x_i = x_1 + \sum_{k=1}^{i-1} A_k \cdot (-1)^k.$ More simply, to compute $x_N$, we simply add the even $A_i$ and subtract the odd $A_i$ to and from $x_1$.↵
↵
We thus have from our equation for dam $N$ that $2x_1 + \sum_{k=1}^{N-1} A_k \cdot (-1)^k = A_N$. We can compute this sum in $O(N)$ and use it to solve for $x_1$. From there, we can substitute this into the equation for dam $1$ to get a value for $x_2$, and we can substitute that into equation two to solve for $x_3$, and so on. Then, we multiply these values by two and print them.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6272209↵
↵
E — Virus Tree 2↵
------------------↵
We build the tree from the top down. Root the tree arbitrarily; we have $K$ choices for the root. Then, we do DFS. In each step of our DFS, we count the number of ways to assign colors to the current node's children and then run our DFS process on each of those children.↵
↵
To count the number of ways to assign colors to a node's children, note that each child must have a different color and those colors must be different from the current node's color and the parent node's color (since the current node's parent has distance two from the current node's children). Thus, we start with $K-1$ colors available for the children of the root or $K-2$ colors available for the children of any other node. Then, once we pick a color for a node, we have one fewer color option than we did before. If we have $x$ children of a node that isn't the root, we can thus express the number of ways to pick their colors as follows:↵
↵
↵
$$\prod_{i=0}^{x-1} K-2-i$$↵
↵
The case for the root works similarly, except we use $K-1$ instead of $K-2$. The answer is then the product of these values over all of the parent nodes, since we need to assign colors to each of the children.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6275812↵
↵
F — Colorful Tree↵
------------------↵
↵
The core idea is LCA with square-root decomposition. First, we figure out how we'll eventually want to answer queries. Note that within a tree, the distance between A and B, if these two nodes have C as their LCA, is equal to $dist(A, root) + dist(B, root) - 2 \cdot dist(C, root).$ Therefore, we now need to efficiently compute distances between nodes and the root.↵
↵
Now, suppose the distance from a node $A$ to the root is $D$ initially. However, suppose that we're changing the lengths of all edges with color $c$ to $d$, and there are currently $x$ nodes of color $c$ on this path with total length $y$. Then, we can see that the distance after this change is $D - y + x \cdot d.$ We now need to efficiently compute $x$ and $y$.↵
↵
To compute these values of $x$ and $y$, we call certain nodes "special" and record the values of $x$ and $y$ for all colors at those nodes. Then, to compute $x$ and $y$ for a certain node and color, we repeatedly move from that node to its parent, incrementing $x$ and $y$ if we reach an edge of our desired color, until we reach a special node, at which point we add that node's $x$ and $y$ to our sum and return it.↵
↵
The key insight is that we can pick the special nodes so that we can both compute the $x$ and $y$-values for the special nodes quickly and reach a special node from any regular node by climbing up the tree in relatively few steps.↵
↵
To do so, we select the special nodes as follows. Sort the nodes in decreasing order of depth. Then, for each node, we move up $\sqrt{N}$ levels in the tree. If we don't find a special node in this process, make the node $\sqrt{N}$ levels above this node special.↵
↵
Obviously, this guarantees that we will only need to move up at most $\sqrt{N}$ steps to find a special node from any regular node. However, we also can prove that this gives us only $O(\sqrt{N})$ special nodes, allowing us to compute them and their $x$ and $y$-values efficiently. Any node up at least $\sqrt{N}$ levels in the tree must obviously have at least $\sqrt{N}$ nodes in its subtree, and because of the order in which we process the nodes, each new special node we add gives at least $\sqrt{N}$ nodes access to a special node that did not have it already. Therefore, we will have at most $\frac{N}{\sqrt{N}} = \sqrt{N}$ special nodes in total.↵
↵
We can thus compute the special nodes and their $x/y$-values in $O(N\sqrt{N})$, and for each query, we take $O(\sqrt{N})$ steps to move upwards and find a special node. Therefore, our total complexity is $O((N+Q)\sqrt{N})$, which passes in time.↵
↵
Code: https://atcoder.jp/contests/abc133/submissions/6290486
