@dvyn01 @taran_1407 @avijit_agarwal @gainullinildar
My solely request to you all please help me and my friends @anon59885521 on this … We tried our best to figure it out… and its been more than 13 days and still not getting the answer… On APR CHAL 2020 my solution to the factor tree question was quite different but i believed it will work… but it didn’t.
I tried using heavy light decomposition but this problem gave me a TLE and only 2 subtasks passed (40pts).
In the editorial the mo’s algorithm is having complexity O(Nlog(MX)(\sqrt N + log(MOD)) )O(N∗log(MX)∗( N+log(MOD))) …
In the HLD implementation of mine each decomposed path is a prefix array where each element is a “hashmap of frequency of prime factors”
When i jump from one chain to another i just have to merge the hashmap of frequency of prime factors", O(logA) operation…
In each query… i am doing standard HLD query only difference is that each node is a hashmap and i merge the maps in order to jump so in every query jumping from one chain to another is O(logn) merging hashmaps is O(logA)…
hence all queries are in O( Q * logn * logA )
this is my solution…
https://www.codechef.com/viewsolution/32313119
Its my humble request please help me on it… i might be wrong to use HLD… but i believe implementation is not… only problem is with TLE…Please help:disappointed: its a nightmare