Problem Idea

general
,
1

Here is one problem idea that have. I have tried to make the problem statement as clear as possible but still let me know if it is not.

Given an array of size N ( N<=10^5 ) ( all elements are less than or equal to 300 and greater than 1) we need to find the length of the longest subsequence which follows the following property :

Let x[1]… x[n] be a subsequence , let p[1],p[2]…p[m] be prime numbers which divide atleast one of the numbers in x[1],…x[n] . Now for each p from 1 to m lets do the following,Let productX ( a variable ) =1 :

  1. If p[i] divides only 1 number in 1…n then find the largest power of this primes which divides that number and multiply it to productX

  2. If p[i] divides more than 1 number then find the largest power of this prime which divides each of the numbers. Now you have n numbers like y[1],y[2]…y[n] ( y[i] is basically the largest power of prime p which divides x[i]).Among those numbers select the smallest and the largest number and multiply it to productX ( Selected numbers must be greater than 1 ).

Now if productX == Product of numbers in that subsequence then it is a valid subsequence .

Example 1) 2 2 4 3 In this case answer is 3 ( Subarray is 2 2 3 or 2 4 3 ). 2 2 4 3 wont be valid because product of numbers is 48 and productX is 2** 4 **3=24 .

I thought of solving this using Max flow .

2

I did not think of the solution, but question seems interesting

3

The question looks really nice. I could not get any solution. Can you post your solution idea also?

4

I tried to find a solution, no idea. Can you post your idea?

5

I only have solutions for some cases like when each number is of the form a^x*b^y where x>0 and y>0 and a and b are primes and a<=p and b>=p ( p will be a given prime number ). In this case we can draw a bipartite graph and find the maximum flow that will be the answer . But to solve for a general case , I dont have an algorithm .

6

First, If i understood the qn correct, we need to find maximum subset of elements, such that no prime number divides more than 2 elements in the subset. Is this correct?

If thats not the qn then ignore this

I think I have a very non elegant solution for the constraints. Anyway check if it works.

First we can remove all redundant elements. (i.e we can have atmost 2 x’s for all x in [1,300]).
So size of array is 600.
Let g(n) be the highest prime factor of n.

let h(n) denote the list of all numbers x in input with g(x) = n (h(n) is defined only if n is prime)

We will traverse i in increasing order choose numbers which we have to pick…

One observation is that second highest prime factor is <= 17. So if we know how many numbers with 2,3,5,7,11,13,17 we have already picked ( each can be used 0,1 or 2 times only). then it is enough to represent the state. Then we can decide either to pick a no. or not and suitably update the state.

State is something like (n2,n3,n5,n7,n11,n13,n17,i) where nk is no. of numbers with k as prime factor that you have chosen and i is the current index for which you are considering filling numbers from h(i)
Complexity is 3^7*600.
I am not sure about correctness. Can someone verify this?

1 Like
7

The solution seems correct to me . It should work within the time limit .

8

Lets say you are choosing among those numbers that have a maximum prime say 31 dividing it. Then you can still choose 2 numbers which divide 31 right. Then won’t we have a complexity of 3^7 *(600)^2 ? Of course this complexity is surely a loose bound but how do you do it without choosing every pair of numbers in this set ?

9

You dont need to choose every pair in this set. Fix an order among the numbers in this set(say ascending) . Now,iterate in this set in this order and you only need to keep track of how many numbers you have picked in this set till now (0 or 1) ( when you pick 2nd number you can go to next prime directly) and the bitmask. so it is like 2*(no. of primes) * 3^7. tat is like 600*3^7.