Hello
Jp morgan quant challenge mail
Thanks for helping me! I really want to understand the solve strategy on these type of problems.
Note
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 07:21:14 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
you need to implement Heavylight decomposition
Can you explain more on this part pls
The problem you need to solve is to compute the sum of values from root to any node efficiently, with updates being made to the value of the nodes. I know that we can use HLD to solve this problem, but it is an overkill for this problem, you can read more about HLD here — https://blog.anudeep2011.com/heavy-light-decomposition/. You can alternatively solve it by linearizing the tree by Euler tour, and then maintain Segment tree or BIT on this array. more on this here — https://codeforces.net/blog/entry/78564.
Constraints?
N=10^4, Q=5*(10^4)
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.
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.
Can someone confirm if the status for this challenge is still showing pending for them?