Still getting TLE
Getting TLE. Maybe it needs to be solved by other method than Sqrt decomposition.
There’s one other way I thought of solving this problem, that uses hashing. I wanted to know if there is some other (simpler) solution.
Can you provide solution using hashing . also can anyone tell how to solve gcd path on tree of that contest.
I have a solution using hashing,O(logN) query,but i dont know if thats what u want.
My idea using hashing is also similar, I’ll maintain a string of remainders modulo 2,3 of prime powers and hash it. But, rather than going for disjoint sparse table, This was what I thought, if H(i) is the hash for the range [0,i], for [L,R] to be a perfect square, H[R] = H[L-1] (because you get product if you divide prefix products). So, we will just need the hashes for prefixes. The string for the ith prefix will differ at 6 characters at most from the i-1th prefix, you can compute in O(6*Log(Mod)) time. I have never implemented hashing for strings, so I wasn’t sure about performance.
1 Like
I really feel my solution rubbish after listening to ur solution 
.
And yeah ,i too wasnt sure about hashing,(good hash function)
Though u could give a try using this hash function:sum( prime*(base)^prime)mod m
Where prime denotes prime factor,base is any prime
Though cant guarantee abt no collision
I’ll try that, thanks
You don’t have to worry about collision much. Instead of one hash function, you can use two different hash functions (two different mods basically). This reduces the probability of collision.
3 Likes
@project8 you can try divide and conquer for gcd path, find the centroid, look for the longest path passing though it, then remove it and search recursively in the newly formed trees. You can learn about it here : Episode 12 - Divide and Conquer on Trees - YouTube
@project8 My dp idea is as follows: For each node, maintain a dp table called dp[p][pos]. Here pos lies between [0, K - 1] and p is a prime this node value is comprised of. Now this dp[p][pos] says that what is the maximum path length starting with this node and ending in one of the subtrees of node. Now using this pos and p, we can actually get maximum path starting in one subtree and ending in another subtree with node connecting between them and it’s position is pos in longest path.
1 Like
Nice problem
@hemanth_1 I tried your hash method and it works. I don’t see why it would be 6*Log(Mod) operations though, 6 is enough.
can you please share your code ?
Here it is: wv8Dj1 - Online C++0x Compiler & Debugging Tool - Ideone.com
I am sure it’s a bit difficult to understand it.
@vivek_1998299 a polynomial hash like you mentioned: hash_2(n) = \sum_p (cnt_n(p) \bmod 2) \cdot base ^ p \mod M where p is prime and cnt_n(p) is the number of times p divides n. It is similar for hash_3. If you want the code: link.
@meooow Yeah you’re right, 6 is enough. I was thinking of taking a prime close to the length of the string as ‘Mod’, and use binary exponentiation for updating. I saw a different hash function here : https://threads-iiith.quora.com/String-Hashing-for-competitive-programming . But we can precompute powers instead.
@hemant i tried using the hash function u mentioned in one of my past hackerrank question,however couldnt get AC(got 50/55) due to collisions.Plz tell if u could find a perfect value of p,mod
(Particularly for strings with 26 characters)
@hemanth_1 actually the hash I used is the same as the one described in that article. Here you can consider the character S_i is cnt_n(i) \bmod 2 when i is prime and 0 when it is not. The difference from the string case is that, as you said when describing the approach, here from hash(x) to hash(xy) some characters change instead of only a new character being added.