Those who solved BACREP, Can you reply here, the algorithm you used?
It took me 6 days and still haven’t solved fully
Those who solved BACREP, Can you reply here, the algorithm you used?
It took me 6 days and still haven’t solved fully
i have also not solved fully, but i think segmented trees is used to solve this problem with lazy propagation technique.
BACREP - “Bacterial Reproduction” - heavily-documented code; Editorial-style overview.
Edit:
After 3 months of posting, I finally earned “Nice Reply” XD
Some beautiful observation(time-depth is the key to success in this problem) + Segment Tree + Lazy Propagation.
I have sorted queries by “depth - time” then simply used HLD + segment trees.
The catch is to use segment tree on (dist[v] - time). In each node save all the updates. while doing dfs of the tree when you discover a node update the segment tree with the value that you need to add at pos= dist[v] - time. tree[pos] = tree[pos]+add
While exiting out of a node update the segment tree with the value that you need to add at pos= dist[v] - time. tree[pos] = tree[pos]-add
For querying if it is a internal node then then determine value of tree[pos] where pos = dist[v] - time.
If it is leaf node then do a range query on tree with l = dist[v] - time. and r=dist[v] +1.
https://www.codechef.com/viewsolution/27351286
Initially I was using persistent segment tree by initially sorting the queries on the basis of its distance. The set of roots were vertex. For each node that is queried, I found it’s nearest queried ancestor and updated the segment tree with root as current vertex. This approach gave me only 50 points
https://www.codechef.com/viewsolution/27343893
Beautiful observations just 3 hrs before the contest is the key to success and high rating .
Lord karan the Great what are your further plans bro,do you ever plan to give a short contest and start giving div 2 afterwards
Sir help everyone to gather codes and give us the ability to attempt whole long in last 2 hrs after total discussion with the worthy.
You have been a motivation.
Yours truly
Fake Id
Arre bro, check out August Long, that time I submitted everything in first 2-3 days, this time I submitted at last, because I was going through a breakup and mind was messed up. Really sorry
I did with euler tours, binary lifting, iterative segment trees (to squeeze in time limit).
https://www.codechef.com/viewsolution/27365890
P.S. Pragma’s just hate me. Was getting TLE because of it. What’s funny is, I couldn’t solve Array modification since I was a bit late to start.
Some hints.
It’s not very clear, but you can have a look at my solution. However, I’ve used Euler tour and some prefix update technique.
On the mobile currently and can’t give a detailed explanation.
Will try to add all details later…
Can anybody help me what was the problem in this one ?? https://www.codechef.com/viewsolution/27366408
I was hoping 1st subtask to accept
Complexity : O((N + Q) logN)
I still do not get the part where we use the prefix sums.
Why/What does the prefix sum tell, how does it calculate the answers?
Obviously for a query we need to consider only those bacteria added to some node on the path to root.
How do we sort out these from the ones we have to not consider?
Do we build one segment/fenwick tree per node? I think not. So how?
Same here bro… apna time aayega…
I think now I got it, please somebody confirm.
We do a DFS, maintaining the Segement (or Fenwick) tree of the path to root of the current node.
With this tree, we can answer all queries for this current node.
After DFS we simply output these answers in order of the queries.
Correct?
Yeah but when u reach a current node…first do the updates
I know how to build segment tree over a array? How you guys build segment tree over a existing tree? as I see most answers are Segment tree/fenwick
Just take a blank segment tree…with everything set to zero, and then here’s the drill
you explained your code in such a simple manner…Thanks