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.
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 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
| Название |
|---|



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