The first two-hour 101 Hack of 2014 is taking place tomorrow on HackerRank from 11:30 am to 1:30 pm (U.S. Eastern time).
Excited for tomorrow's five challenges! I hope to see some others there.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
The first two-hour 101 Hack of 2014 is taking place tomorrow on HackerRank from 11:30 am to 1:30 pm (U.S. Eastern time).
Excited for tomorrow's five challenges! I hope to see some others there.
Name |
---|
can anybody tell me how to solve the 4th problem from the contest (
Recalling Early Days GP with Trees
)?My solution (sorry for bad English):
firstly, we need to calculate numbers on every vertex after all update queries. Every vertex has numbers:
addUp[i]
— sum of progressions that increases from i-th vertex in direction to 0-vertex,subUp[i]
— sum that we need to subtract from addUp[i] for push to next vertex (it means that some of increases progressions is ended on i-th vertex),addDown[i]
— sum of progressions that decreases from i-th vertex in direction to 0-vertex,subDown[i]
— sum that we need to subtract from addDown[i] for push to next vertex (it means that some of decreases progressions is ended on i-th vertex),subIntersection[i]
— need for remove of intersections (see below).For every query
(a, b, x)
we need to change this numbers:m = lca(a,b)
//lowest common ancestor from 0-vertexif (a==m) then we need to define decreased progression from b to a, it means that
addDown[b]+=x*r^dist(a,b)
// we need to start from this value to a-vertex // dist is distance betweensubDown[a]+=x
// this value we need to subtract from addDown[a] when go to parent of a-vertex, because some of progressions was ended on a-vertexif (b==m) then we need to define increased progression from a to b, it means that
addUp[a]+=x
// we need to start from this value to b-vertexsubUp[b]+=x*r^dist(a,b)
// this value we need to subtract from addUp[b] when go to parent of b-vertex, because some of progressions was ended on b-vertexif (a!=m and b!=m) then we need to define two progressions
(a, m, x)
and(m, b, x*r^dist(a,m))
, and we need to calculate:subIntersection[m] += x*r^dist(a,m)
// it need because two created progressions have intersectionThen, use depth-first search for calculate value on each vertex (from leafs to 0-vertex):
Now, we can to calculate s[i] — sum of values in vertices on path from 0-vertex to i-vertex.
For every query
(a, b)
we can calculate answer:(s[a]+s[b]-s[m]*2+values[m])
// m = lca(a,b)P.S. I hope, you understand me
My ugly code is here http://codeforces.net/contest/1/submission/5859681
Great solution. I was thinking along the lines of Heavy-Light decomposition but couldn't get anywhere with it. Thanks for your good explanation. :)
We can just have two arrays (deltaUp and deltaDown) instead of five. Instead of subIntersection we subtract correct values from deltaUp of lca and deltaDown of lca's parent