PROBLEM LINK:Practice DIFFICULTY:Medium PREREQUISITES:LCM and Dynamic Programming PROBLEM:Given an array A1,A2...AN you have to print the size of the largest contiguous subarray such that LCM of all integers in that subarray is equal to the product of all integers in that subarray. Solution:Problem Idea: Calculating efficiently longest subarray which ends at i for each i. LCM of all integers in that subarray is equal to the product of all integers in that subarray. Pseudo Code
What will be our answer ? You need to precompute factors of each numbers [ from 1 to 10^{6} ]. Reason : Calculating it in run time may lead to TLE because : For factoring any number , you need to iterate over all prime numbers less than sqrt(number). In worst case this number is close to 150. Hence total number of steps will be approximately 150 * 100000 for each Test case. So, for 50 test cases this goes to 75 * 10^{7} which will time out. Another Way of understanding the Solution Two pointer method Basically in other words, you can treat the segment as a window representing a valid solution. You need to support fast addition and deletion of elements from the window. But you will notice that if your right pointer always increases then you will never need to delete the right end of the segment. You will always delete the left end and will always add the right end of the segment. It is very easy to prove that complexity of this method is O(n), as that right pointer is always increasing and hence can make at most n iterations, So overall there could be at most n + n iterations over both left and right ends of a good segment which amounts to total O(n) operations. This method is called window two pointer method. Sometimes this method is called sliding window algorithm too. How to apply it in our problem Overall complexity of this method is O(N). AUTHOR'S and TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 Sep '14, 00:14

Kudos to Tester's solution...very readable! Thanks.. :) answered 22 Sep '14, 11:16

I'm getting WA and have no idea why. Here is my submission: www.codechef.com/viewsolution/5149059 Can someone help me/provide tricky test cases? I wasn't able to find any; answered 14 Oct '14, 20:54

I did very the same as @sikander_nsit described, any generator for a worst case ? My solution is here  http://www.codechef.com/viewsolution/4879169 complexity in comments... I used map to represents polynomial, for example 18 = 2 * 3 * 3 = 2 * 3^{2} => answered 22 Sep '14, 01:54

To Editorialist : Some accepted solutions are giving wrong answer for case : 2 46093 92186 . Please consider this case . answered 22 Sep '14, 04:33

Please anyone expalin how is this working Dp[i] = min ( Dp[i1]+1 , i+1  Cal(i) ) answered 22 Sep '14, 10:23

Could somebody explain me this in the Tester's solution:
And how does it function similar to
answered 27 Sep '14, 16:03

Easy with sliding window algorithm...(or kadanes algorithm) answered 03 May '15, 11:23

Why can't we use normal gcd function in Cal(i)? I agree it increase the time.But its still in limit,right? answered 23 Sep '15, 15:56

solution links broken..
getting TLE....http://www.codechef.com/viewsolution/4882769 please someone help!!!!