BACREP - Algorithm behind?

1

Those who solved BACREP, Can you reply here, the algorithm you used?

It took me 6 days and still haven’t solved fully :frowning:

5 Likes
2

i have also not solved fully, but i think segmented trees is used to solve this problem with lazy propagation technique.

1 Like
3

BACREP - “Bacterial Reproduction” - heavily-documented code; Editorial-style overview.

Edit:

After 3 months of posting, I finally earned “Nice Reply” XD

30 Likes
4

Some beautiful observation(time-depth is the key to success in this problem) + Segment Tree + Lazy Propagation. :slight_smile:

10 Likes
5

I have sorted queries by “depth - time” then simply used HLD + segment trees.

1 Like
7

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

8

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

2 Likes
9

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 :frowning:

9 Likes
10

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. :sweat_smile:

3 Likes
12

Some hints.

  • Queries can be processed offline
  • how can you define where some bacteria will be at a particular time? Find some relation between node height, time it appears in that cell and when this bacteria would be present in some child cell. Call this delta
  • Define similarly for the queries. Call this delta1
  • Value of delta is Height[node] - time it appears on this node.
  • Value of delta1 is Height[node being queried?] - time at which query is done.
  • Number the queries and store them for future processing.
  • You can easily prove that the delta and delta1 of ancestor/child are never the same if the update on ancestor is made after the query on child.
  • Make a Fenwick tree to store the sum of elements <= delta for every delta.
  • Run a DFS. For the particular node that we are processing, first add all the updates that are done to this node to the Fenwick tree.
  • then processes all queries done on this node. Then iterate to the children.
  • After processing all children nodes and queries in this fashion, reverse the updates that were added by this node.

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…

3 Likes
13

Can anybody help me what was the problem in this one ?? https://www.codechef.com/viewsolution/27366408

I was hoping 1st subtask to accept

1 Like
14

Complexity : O((N + Q) logN)

1 Like
15

I solved beautifully with fenwick tree and PBDS

solution

3 Likes
16

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?

1 Like
17

Same here bro… apna time aayega…

1 Like
18

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?

1 Like
20

Yeah but when u reach a current node…first do the updates

1 Like
21

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

22

Just take a blank segment tree…with everything set to zero, and then here’s the drill

  1. Do updates
  2. Ask Query
  3. Go deep
  4. Backtrack and Remove updates
3 Likes
23

you explained your code in such a simple manner…Thanks

1 Like