Why heavy light decomposition is not working with FACTOR TREE problem April long challenge

@dvyn01 @taran_1407 @avijit_agarwal @gainullinildar

My solely request :pray: 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::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::disappointed::weary::weary::weary::weary::weary::cry::cry::sob::sob: its a nightmare

3 Likes

@raunak316
Here the most important observation is that the number of distinct primes within 10^5 is nearly 9500. So for the worst case of all the numbers being prime and covering nearly all the primes with 10^5 range, your calc function will have an complexity of O(9500) which will multiply your time complexity by O(9500) factor and thus will result into a TLE.
I hope it clears your query!!

4 Likes

@avijit_agarwal

Thank you sir very much you gave me your precious time…
I took me sometime but i figured it out… this thing was my blind spot… i don’t know why
i didn’t thought this way… you 6 stars and 7 stars write things too short and subtle little abstract for us :sweat_smile: :sweat_smile: :rofl: :rofl:.

By the way thank you very much… i mean very very much

BigInteger thanks = new BigInteger(1);
for(int i = 0;i <= Integer.MAX_VALUE;i++)
thanks.multiply(Long.MAX_VALUE);
System.out.println(thanks.toString());

4 Likes