FCTRE without MO algo

help
1

can anyone tell me how to do FCTRE without MO algo
Thanks in advance…

2

i got only 40 .my approach is at each node i have hashmap that store the prime factors of multiplication of values from node 1 to current node . i.e O(n logn) and for each query i found LCA (logn)and then calculate the total divsors by removing the primefactors upto lca .
my code:CodeChef: Practical coding for everyone
so this could be of O(Qlognlogn+Nlogn).still i am not getting 100.

3

For every query you iterate through all the primes that can be possible in the number and the number of such primes is a lot. So per query you take atleast O(number of primes) operations. and number of primes less than 1e6 is about 1e5 ig. So it is 1e5*1e5 operations.

2 Likes
4

ohkk bro i got it
but can you please tell how to do without MO algo

5

I used a faster method for finding LCA of each node, which takes O(NlogD) to set up and about O(NlogD) for each query, where D is the depth of the tree, but even so I got only 40 points. I think the killer is in the handling of the prime numbers and their factors. I store the numbers (costs) as their prime factors with multiplicities, then multiply primes by adding the multiplicities, an operation which takes O(number of primes). In my method there are 2 multiplications per node during setup, and 4 multiplications or divisions per node for each query.

You can see my solution at CodeChef: Practical coding for everyone

I have an idea for improving the LCA algorithm, which I intend to try this week, but I don’t expect much gain in speed.

6

That is Strange, Even I did the same thing but got only 10 points.

1 Like
7

Yeah even I did the same. I think the lenient constraints on Java made his solution pass for 40 points.

8

If you try to solve FCTRE with LCA using binary lifting. Then worst case for each query can go O(NlogN)

Case: Linear tree with all prime numbers
Query between two opposite ends.

9

But for a number less than 10000 number of prime factors can be almost 6 only

10

but we have take care of multiplicatoin so can go upto big numbers

1 Like
11

but i use sparse table
each query logn

12

Yes, sparse table on trees is okay.
But we need to store a map of all prime frequency in f[i][j] that there are in between path of i and jth ancestor. Ignore everything and think of last node. Let’s say its last ancestor is conveniently the root. f[i][j] will be storing all N node if all N data are distinct primes. But f[i][j-1] will be storing exactly half. So injust two maps there are N+N/2 node, try calculating for yourself for next.

Let’s say we move past that and fit data in memory somehow, some crazy optimisation applied.

Now consider scenario of query. In each query, result is Merge (a\rightarrow LCA,b\rightarrow LCA), This merging can again take O(N) per query.

1 Like
13

May be it can be done using HLD. But till now, I didn’t find any solution on it.