oobxw9zf0lm7ez's blog

How can I solve this tree problem from Jp morgan quant challenge [1 Aug]
By oobxw9zf0lm7ez, history, 3 years ago, In English

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
  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you need to implement Heavylight decomposition

    Can you explain more on this part pls

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply