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

Автор oobxw9zf0lm7ez, история, 3 года назад, По-английски

Hello

Jp morgan quant challenge mail

Problem

Thanks for helping me! I really want to understand the solve strategy on these type of problems.

Note
  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think you can do this with LCA & HLD. You need to maintain an identical tree structure with all zeros initially, to keep track of updates, let's call this updates tree. For query of type 1 find the LCA add +v to LCA, and -v to the child of LCA that is not an ancestor of u or v, child of u, child of v (you need to handle the cases when some of {u, v} are leaves) in the updates tree. Now for the query of type 0, you just need to compute the value of the node correctly, you get this by a_u from the original tree + sum of all the nodes from node u to the root in the updates tree, to do this part I think you need to implement Heavylight decomposition. once you have the node values, you can compute gcd.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Constraints?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    N=10^4, Q=5*(10^4)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      Root tree at any node. Let l be LCA(u,v). Add p to both u and v, subract p from lca, subract p from parent[lca]. Now to get the value of any node u, just query sum over subtree(use segment tree for fast sum over subtree). After getting values you can do GCD.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem statement was inconsistent with the sample explanation. In the type 0 queries, we actually have to calculate the GCD of all the nodes in the path from node u to node v, instead of just the GCD of node u and node v. I implemented a solution using LCA and fenwick tree and found out that the actual problem was different while testing the code.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone confirm if the status for this challenge is still showing pending for them?