Geothermal's blog

AtCoder Beginner Contest 133 English Solutions
By Geothermal, history, 5 years ago, In English

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

  • Vote: I like it
  • +98
  • Vote: I do not like it

Comments Comments (38)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wow, so quick tutorial.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, nice trick with the 'special nodes' in F. Is this trick well known?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks! I'm actually not sure how well-known it is, but the general idea of square root decomposition for tasks like this is reasonably common. My main motivation here was that I had reduced the problem to dealing with paths up a tree. Many of the common tree decomposition techniques (e.g. HLD, centroid decomposition) didn't seem helpful here because with up to N different colors, storing all the data could be extremely memory intensive. I considered square root decomposition because it allowed me to perform my precomputations and store the data in $$$O(N \sqrt{N})$$$, which suggested that it might be the right tool here.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

You can solve F offline in (N + Q) log(N). https://atcoder.jp/contests/abc133/submissions/6295299

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does there exist a solution for question C, Remainder Minimization, where the time complexity of the solution is O(2019) instead of O(2019^2) ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems F can alternatively be solved in $$$O((N+Q) \log N).$$$ If anyone wants to post a write-up of one such solution, please feel free to do so and I'll add it to the post (with credit, of course).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is goto done?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    In C++, you can use goto statements to immediately go to some other line in your program. In my code to problem F, I used goto done to end execution of the loop meant to identify special nodes immediately after a special node was found on the path upwards from some node, since that means we won't need to add a new special node to accommodate the node we're currently considering.

    In retrospect, using break instead would have worked just as well here, as it doesn't matter whether or not we set special[cur] to true again, but often, goto is superior to break because you can use it to break out of loops other than the innermost one or to skip some code appearing immediately after a loop.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +81 Vote: I do not like it

It's awesome some people write editorials for Atcoder Beginner Contests. And I think that ABC is the best place for beginners to compete. Problems are both educational and not that boring. Kudos to organizers and to you for writing the editorial.

It's easier to just do R = min(R, L + 2019) in C instead of an if.

Problems like D are often done with binary search and it's also a possible alternative solution here. Binary search the first variable, use its value to compute every next variable and the last equation will tell you if your first variable turns out too big or too small.

In F, I will briefly describe the offline solution some people mentioned. In the $$$i$$$-th query (say, about path from $$$a$$$ to $$$b$$$), we compute the LCA of $$$a$$$ and $$$b$$$ and put index $$$i$$$ in some list for vertices $$$a$$$, $$$b$$$ and $$$lca$$$ (e.g. list_of_queries[a].push_back(i)). Then we do DFS from the root and we maintain the frequency array (and sum-of-values array) of path from the root to the current vertex. For the current vertex, we go through list_of_queries[vertex] and for each query id in that list, we need the number of edges of some color that are on the path from the root.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Now i see what makes codeforces one of the best.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B i can Just say that if i take the square root of dist where b = (dist)^(1/2) then check whether b * b = dist. Which is Better ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course, your case is faster and better in this situation. But, when the numbers are big, lest say, bigger than 1e18, C++ sqrt won't work as you want. Consider doing a binary search on sqrt in this case (which is ofc. still better than keeping squares).

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for that but i don't understand the last sentence this "bigger than 1e18, C++ sqrt won't work as you want. Consider doing a binary search on sqrt in this case (which is ofc. still better than keeping squares)." Why is that .

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Short answer: Floating point operations are scary. There's always the fear that running sqrt(x^2) gives a double which is $$$x - \epsilon$$$ for a small $$$\epsilon$$$. This would then get cast to an int as $$$x - 1$$$, so the check would fail then.

        Fun list of floating point gotchas: https://floating-point-gui.de/

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, that would work. I used my approach because I wanted to avoid dealing with double precision issues, as taking a WA on a relatively easy problem like this one would have been bad for my penalty. This solution has a better time complexity, but in general, the best solution to a competitive programming problem may not be the most efficient one--it's the acceptable solution you find easiest to implement. In the ABC environment, I needed to implement the easier problems in a matter of minutes without making any incorrect submissions, so I decided to simply check against all squares even though that weakened my solution's time complexity.

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You did godly things thanks .

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

We can solve the problem F online using Heavy light decomposition.

For each heavy chain, we can use a vector to maintain the informations. When there's a query, we can binary search on vector to get the informations we need.

Because I want to make the action easier, I create a node for each edge.

It is simple and easy to understand by code. Time complexity is $$$O(N log^2 N).$$$

Code
→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There's offline solution for F without sqrt decomposition.

For every query (a,b,c,d) we want to know $$$x_c$$$ and $$$y_c$$$ for nodes a, b, and lca(a,b).

Lets precompute all "interesting colors" for every node (note there's at most q*3 node/color pairs). We can find answers for every interesting node/color pair using DFS.

Let $$$X$$$ and $$$Y$$$ be current arrays of $$$x$$$ and $$$y$$$ respectively for every color. In the vertex just copy the answer for interesting colors.

When we go down the edge we update exactly one value in $$$X$$$ and $$$Y$$$, and can easily be rolled back when returning from vertex.

Spoiler

This gives you $$$O((n+q)\ln n)$$$

P.S. Similar can also be done online with persistent arrays but you need way more code.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Since n and c are large, we must use map to save info about vertex/color relations?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      If colors were up to $$$10^9$$$, you would need a map. An array is enough here. When you go down in DFS with edge of color $$$c$$$, increase frequency of $$$c$$$ by $$$1$$$. When you go back up, decrease by $$$1$$$.

      I think that kilotaras used a map to save something for every query but it isn't necessary. Just tell vertices $$$a$$$, $$$b$$$ and $$$lca(a,b)$$$ that they should do something for query number $$$x$$$ and they will update $$$answer[x]$$$.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For query (u,v,c) you need tot [ lca(a,b) ] [ c ], but this may not be calculated since lca(a,b) and c are maybe not interesting vertex/color pair. How do u deal with this?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Query a,b,c,d adds 3 interesing pairs : (a,c), (b,c) and (lca(a,b), c). Precompute those in advance. Then either save computed values or just update answer directly as Errichto suggested.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It's good. 为什么Atcoder的题解会放到Codeforces上？

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because the editorial at img.atcoder.jp/abc133/editorial.pdf only has a Japanese version, but there're lots of international users who can't understand. So Geothermal wrote an English one.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks @ Geothermal for nice and fast editorial...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For those who are wondering what technique was used in F, this link might be useful

→ Reply