(FCTRE) Factor Tree - Video Solution (APRIL20)

editorial
,
1

Hi,
I have created a video solution for the problem FACTOR TREE under April long challenge 2020. This was one of the most fun to solve problem in the contest and I hope you will enjoy the solution too.
I also explain how to use mo’s algorithm on trees.

If you understood the solution please do leave a like on the video.

Happy coding!

10 Likes
2

What is RE(other).
My code: CodeChef: Practical coding for everyone

It will give tle for task3. But why is it wrong for task1 and 2.

3

You are calling explore() recursively and this function has visited and cost vectors passed by value. So when the recursion causes function stack to become huge (10^5), each instance of the function in the stack will have the copies of visited and cost vectors which are itself huge. So you are using too much memory. I think this is why you are getting RE.

2 Likes
4

Thanks

1 Like
5

Thanks :slight_smile: .Great Explanation.

1 Like
6

Glad you liked it!

1 Like
7

Thanks for the explanation

I did this way in place of Mos algo

Precomputation:

for each node , I found the factors of product of costs of nodes in the path from root to that. node. This can be done along with dfs( find the fact count of product till this node using its parent)

complexity : NlogA - N is dfs complexity and at each node i am computing factors unsing parent hence logA

Query:
u,v

ans(u) + ans(v) - 2* ans(lca) + ans( single lca node)

ans(u) - means answer in path from root to u.

ans() can be computed using preprocessing step. as i already have factors for product from root to u . Here i just need to multiply their powers.

4*logA

But this resulted in TLE. CodeChef: Practical coding for everyone

Anyone please help me to understand the reason.

8

What does compute_intersection() and compute_sub() do?
How are you calculating the answer for a query? From what i understood from your code you are iterating over all prime factors which will be there in the product from u to v. In worst case there can be more than N primes, where N is no of nodes in the path.

9

Not so easy actually, you would have to iterate through all the primes in the map.

I think the problem is with the maps, these can get really big, imagine the costs having all primes, then your “root to that node” map will have a map like {2 : 1, 3: 1, 5: 1 … }.
There are approx 78000 primes below 1e6 this would give a TLE because you’ll have to answer 1e5 queries.

1 Like
10

Can u help , why my solution is giving even for subtask 1 ? i am find my mistake.
CodeChef: Practical coding for everyone

11

Try passing this “vector<vector >v” as reference.

12

I have updated my code with comments.

13

codechef.com/viewsolution/31952865

I don’t know which kind of errors are these ,
I am trying to switch from python to c++ due to tle so I don’t actually know how to code c++ that well
I almost followed ur code but it is giving strange errors ,
maybe i am not re-initialising things properly , maybe in c++ it is not done in this way .
Can u please help me solve it .

14

In sorting function why did you use return l / BL % 2 ? r < q2.r : r > q2.r; instead of return q1.r<q2.r?

15

This is a more efficient way of sorting for mo’s algorithm. Look at how the right pointer moves. You will get why its better.