bli0042's blog

By bli0042, 11 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    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

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Great solution. I was thinking along the lines of Heavy-Light decomposition but couldn't get anywhere with it. Thanks for your good explanation. :)

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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