How to solve Bacterial Reproduction(BACREP) from October Long 2019?

help
, , , , ,
1

Anybody mind sharing a detailed explanation. I could only come up with the Brute Force approach during the contest.

1 Like
2

Check out my solution:

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

3 Likes
3

Thank you :slight_smile: I knew you would answer :stuck_out_tongue:

1 Like
4

400 lines :cold_face::cold_face:

5

By the way, although I would be seeing your code but from what I could think during the contest, does it have something to do with first doing an Euler Tour(ETT) over the tree and then using either a Segment Tree or Mo’s Algorithm to answer each query? I couldn’t reach to the ‘how-to’ part though, may be there is some neat trick.

6

Yes - Euler Tour (or DFS) plus Segment Tree is sufficient :slight_smile:

2 Likes
7

Can anybody help me what was the problem in this one ?? CodeChef: Practical coding for everyone

I was hoping 1st subtask to accept