Блог пользователя bli0042

Автор bli0042, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

can anybody tell me how to solve the 4th problem from the contest (Recalling Early Days GP with Trees)?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    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-vertex

    • if (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 between
      subDown[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-vertex

    • if (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-vertex
      subUp[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-vertex

    • if (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 intersection

    Then, use depth-first search for calculate value on each vertex (from leafs to 0-vertex):

        dfs(int v, int p = -1) {  // v - current, p - parent
            for (int to : g[v])
                if (to != p)
                    dfs(to, v);
            values[v] = values[v] + addUp[v] + addDown[v] - subIntersection[v]; // add all progressions in current states and subtract intersections
            if (p >= 0) {
                addUp[p] = addUp[p] + (addUp[v] - subUp[v])*r;          // push increases progressions to parent
                addDown[p] = addDown[p] + (addDown[v] - subDown[v])/r;  // push decreases progressions to parent
            }
        }
    

    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