FCTRE bruteforce

1

In FCTRE, I was getting WA for the first sub task when I used DFS . But why wouldn’t a simple DFS work here (for the first sub task ofcourse)?

2

maybe becoz u werent MOD-ding it

3

Where my code is wrong?
Link: CodeChef: Practical coding for everyone
It is giving RE (SIGSEGV)

4

But according to the constraints, maximum happiness quotient possible is 10^9 (for the first sub task). What is the need to Mod?

5

I think you misinterpreted the question. Happiness quotient is the product of cost( A[i] ) in the path.
A[i] for all the subtasks is <=10^6. So product can exceed 10^9.

2 Likes
6

For the first subtask, N≤10^3

7

yes but node values a[i] had no such sub constraints… so products can be greater than mod(10e9+7)…

2 Likes
8

Ohh, yeah. I got confused too

1 Like
9

My bad. Thank you

10

If you want a video solution : Factor Tree - Mo's algorithm on Trees | Codechef April Long Challenge 2020 - YouTube