How to solve the problem Square or Cube from Airtel Crack the Code ?

general
, , , , ,
1

Given an array of ‘N’ numbers and ‘Q’ queries, where in each query you are given a range [L,R], you need to tell if the product of all numbers in this range is a perfect square or a perfect cube or both or none.

1 <= N,Q <= 3*10^5
-10^5 <= Arr[i] <= 10^5

I used MO’s algorithm, maintaining the number of primes whose sum of powers modulo 2,3 is equal to 0 and compared that with the number of distinct primes in the prime factorisation of all numbers in the range. I got TLE. The Complexity is 6*(N+Q)*Sqrt(N).

3 Likes
2

Can you share your code ? I think it can be solved by MO’s algorithm just with some tricky implementation.

3
4

I tried to reduce the number of division and modulo operations. There was almost no difference.

5

You could try optimisation by @meooow

Sort even blocks ascending,odd blocks descending

(Blocks 0 based)
It really fastens very much.

6

I’ll try that

7

Still getting TLE

8

Getting TLE. Maybe it needs to be solved by other method than Sqrt decomposition.

9

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.

10

Can you provide solution using hashing . also can anyone tell how to solve gcd path on tree of that contest.

11

I have a solution using hashing,O(logN) query,but i dont know if thats what u want.

12

@vivek_1998299 yes that solution should work. Share your idea and code.

13

My solution is based on some divide and conquer and hashing(it would be simple if u read disjoint sparse table tutorial before)

Lets build a tree,where the root node ans the query for all ranges(l,r) such that l< mid and r> mid,mid=n/2

So in this node ,precalculate the prime factorisation of ranges (i,mid-1) where i>=l and (mid,j) where j>mid ,calculate it mod2 and mod3

So lets say for (l,mid-1) we have prime factor(power raised to mod2) as 2,3,5(no use of 0 powers)

Then for (l,r) to be a perfect square (mid,r) must have the same prime factors mod2(ie 2,3,5)

So one can just hash the prime factor sequence in some way and for checking (l,r) ,compare hash value of (l,mid-1),(mid,r)

For mod3,we must have sth like 2^1,3^2 on one side and 2^2,3^1 on other

So for mod3,one should hash the complement(3-x) in left side ie if it is 2^2,3^1 then convert to 2^1,3^2 and hash it,while for the right side hash the uncomplemented form

So again to check if its a cube one can compare complemented of(l,mid-1) and uncomplemented of (mid,r)

However this node could only ans for the ranges (l,r) such l < mid ,r > mid

So do this thing repeatedly for left and right halves

Preprocessing:O(nlogn)

Query:O(logn)

(U can ans it in O(1) using some bit operations,however i dont remember it correctly)

Sorry i haven’t written the code,its just an idea.

2 Likes
14

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
15

I really feel my solution rubbish after listening to ur solution :slight_smile: .

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

16

I’ll try that, thanks :slight_smile:

17

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
18

@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 : https://www.youtube.com/watch?v=3pk02p1-weU

19

@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
20

Nice problem :slight_smile:
@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.