Geothermal's blog

By Geothermal, history, 4 years ago,

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.

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.

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.

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.

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.

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.

• +98

| Write comment?
 » 4 years ago, # |   0 Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).
 » 4 years ago, # |   0 wow, so quick tutorial.
 » 4 years ago, # |   0 Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).
 » 4 years ago, # |   0 Thank you!
 » 4 years ago, # |   0 Wow, nice trick with the 'special nodes' in F. Is this trick well known?
•  » » 4 years ago, # ^ |   +8 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.
 » 4 years ago, # | ← Rev. 2 →   +24 You can solve F offline in (N + Q) log(N). https://atcoder.jp/contests/abc133/submissions/6295299
 » 4 years ago, # |   0 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) ?
 » 4 years ago, # |   0 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).
•  » » 4 years ago, # ^ |   +2 can we solve F using MO's algorithm on trees?
•  » » » 4 years ago, # ^ |   +2 Probably, but absolutely not as good as the one using offline lca queries. and I think it harder to code in MO's algorithm than in the previous algorithm. My optimum solution :D
 » 4 years ago, # |   0 What is goto done?
•  » » 4 years ago, # ^ |   +2 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.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Why does this TLE? https://atcoder.jp/contests/abc133/submissions/6332987 thanks XD
 » 4 years ago, # | ← Rev. 3 →   +81 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.
•  » » 4 years ago, # ^ |   +3 Now i see what makes codeforces one of the best.
 » 4 years ago, # |   0 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 ?
•  » » 4 years ago, # ^ |   0 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).
•  » » » 4 years ago, # ^ |   0 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 .
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 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/
•  » » 4 years ago, # ^ |   +1 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.
 » 4 years ago, # |   +3 You did godly things thanks .
 » 4 years ago, # | ← Rev. 3 →   0 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#include #define int long long using namespace std; typedef long long ll; const int N = 200000 + 10; ll n, q, f[N][20], col[N], len[N], sum[N]; ll d[N], sz[N], son[N], pos[N]; ll top[N], id[N], df; vector g[N]; vector bels[2][N]; void link(ll u, ll v) { g[u].push_back(v); g[v].push_back(u); } void dfs1(ll u, ll pre) { f[u][0] = pre; d[u] = d[pre] + 1; sum[u] = sum[pre] + len[u]; sz[u] = 1; for(int i = 1; i <= 18; i++) { if(f[f[u][i - 1]][i - 1]) f[u][i] = f[f[u][i - 1]][i - 1]; else break; } for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(v == pre) continue; dfs1(v, u); sz[u] += sz[v]; if(!son[u] || sz[v] > sz[son[u]]) son[u] = v; } } int lca(int u, int v) { if(d[u] < d[v]) swap(u, v); for(int i = 19; i >= 0; i--) if(d[u] - (1 << i) >= d[v]) u = f[u][i]; if(u == v) return u; for(int i = 19; i >= 0; i--) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; return f[u][0]; } void dfs2(ll u, ll t) { top[u] = t, id[u] = ++df; pos[df] = u; if(son[u]) dfs2(son[u], t); for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(v == f[u][0] || v == son[u]) continue; dfs2(v, v); } } ll Bs1(int x, int t) { int l = 0, r = bels[0][x].size() - 1; ll ans = -1; while(l <= r) { int mid = (l + r) >> 1; if(bels[0][x][mid] <= t) ans = mid, l = mid + 1; else r = mid - 1; } return ans; } ll BinarySearch(int x, int t) { int l = 0, r = bels[1][x].size() - 1; ll ans = -1; while(l <= r) { int mid = (l + r) >> 1; if(bels[0][x][mid] <= t) ans = mid, l = mid + 1; else r = mid - 1; } if(ans == -1) return 0; return bels[1][x][ans]; } pair bsearch(int u, int v, int po) { if(bels[0][po].empty()) return make_pair(0, 0); ll A = Bs1(po, v) - Bs1(po, u - 1); ll C = BinarySearch(po, v), D = BinarySearch(po, u - 1); return make_pair(A, C - D); } pair Query(int u, int v, int c) { pair t; t.first = 0, t.second = 0; while(top[u] != top[v]) { if(d[top[u]] < d[top[v]]) swap(u, v); pair te = bsearch(id[top[u]], id[u], c); t.first += te.first, t.second += te.second; u = f[top[u]][0]; } if(id[u] > id[v]) swap(u, v); pair te = bsearch(id[u], id[v], c); t.first += te.first, t.second += te.second; return t; } signed main(){ scanf("%lld%lld", &n, &q); for(ll i = 1, u, v, c, d; i < n; i++) { scanf("%lld%lld%lld%lld", &u, &v, &c, &d); link(u, n + i); link(v, n + i); col[n + i] = c, len[n + i] = d; } dfs1(1, 0); dfs2(1, 1); for(int i = 1; i <= 2 * n - 1; i++) bels[0][col[pos[i]]].push_back(i),bels[1][col[pos[i]]].push_back(len[pos[i]]); for(int i = 1; i <= n - 1; i++) for(int j = 1; j < bels[1][i].size(); j++) bels[1][i][j] += bels[1][i][j - 1]; while(q--) { int x, y, u, v; scanf("%lld%lld%lld%lld", &x, &y, &u, &v); pair ans = Query(u, v, x); //fprintf(stderr, "%lld, %lld\n", ans.first, ans.second); ll ans1 = sum[u] + sum[v] - 2 * sum[lca(u, v)]; ll ans2 = - ans.second + 1ll * y * ans.first; //printf("%lld %lld\n", ans1, ans2); printf("%lld\n", ans1 + ans2); } return 0; } 
•  » » 4 years ago, # ^ |   0 May I suggest putting your code in a spoiler tag to collapse it?
•  » » » 4 years ago, # ^ |   0 Sure.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Is this Heavy Light Decomposition ?
•  » » » 4 years ago, # ^ |   0 Yes... I don't know how to explain it using english. :)
•  » » 4 years ago, # ^ |   0 Well this is a well-known trick, but isn't it too hard to code during the contest?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 I think it is easy if you practice a lot. :)However, I finish it within 60 minutes. Here's my submission: qwq
 » 4 years ago, # |   +3 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. Spoilervoid dfs2(int v, int p, int dist) { rdist[v] = dist; for (auto c: targ[v]) { cnt[v][c] = cnts[c]; tot[v][c] = totals[c]; } for(auto np: g[v]) { if (np.X == p) continue; int nv = np.X; int c = np.Y.X; int d = np.Y.Y; cnts[c]++; totals[c] += d; dfs2(nv, v, dist+d); totals[c] -= d; cnts[c]--; } } 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.
•  » » 4 years ago, # ^ |   0 Since n and c are large, we must use map to save info about vertex/color relations?
•  » » » 4 years ago, # ^ |   +8 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]$.
•  » » 4 years ago, # ^ |   0 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?
•  » » » 4 years ago, # ^ |   +10 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.
 » 4 years ago, # | ← Rev. 2 →   0 It's good. 为什么Atcoder的题解会放到Codeforces上？
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 thanks @ Geothermal for nice and fast editorial...
 » 3 years ago, # |   0 For those who are wondering what technique was used in F, this link might be useful