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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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.
Название |
---|
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://mirror.codeforces.com/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