You are not logged in. Please login at www.codechef.com to post your questions!

×

SUBLCM - editorial

20
7

PROBLEM LINK:

Practice
Contest
Author: Lalit Kundu
Tester: Tasnim Imran Sunny
Editorialist: Devendra Agarwal

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.

Let Dp[i] denotes the length of the longest subarray ending at i and satisfying the property that the product of all integers of the subarray is LCM of the subarray.

If we know Dp[i-1] , can we calculate Dp[i] ?

Yes , Dp[i] = min ( Dp[i-1]+1 , i - Cal(i) ) (Array indexing starts from 1) , where Cal(i) calculates the last index encountered which is not co-prime to A[i] while travelling left from i. If no such index is found , then 0 is returned.
Let A[] = 2 3 5 4 9 5 10 , then Cal(i) for i=1,...7 will be 0,0,0,1,2,3,6.


Dp[] = 1 2 3 3 3 3 1

Ans=max(Dp)=3

How to calculate the Cal(i) efficiently ?

A number is not co-prime to another number if there exist a common gcd [ or a common prime factor ].

Ok, then we need to factorise A[i+1] , let say we wrote A[i+1] = p1e1 * p2e2 * p3e3 * .... * pkek , where pi is prime number.

Now we need to pick up the latest index where any of these factors came.

But how can we do it efficiently ?

Look at the constraints and you will notice that A[i] <= 106 , so each prime is less than 106

We can use an array of size 106{let's call it P[]} to find out the latest position. Look at the pseudo code for Cal(i).

Pseudo Code int Cal(int idx) int ret_val = 0 Factors = Factorise(A[idx]) //Factorise will only return prime factors for(int i = 0 ;i< Factors.size() ;i++ ) //iterating through all factors ret_val = max( ret_val , P[Factors[i]] ) //P is an array of size 106 P[Factors[i]] = idx //latest index for prime number Factors[i] is updated to idx. return ret_val

What will be our answer ?

Max ( dp[i] ) for all i

Some PitFalls

You need to precompute factors of each numbers [ from 1 to 106 ]. 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 * 107 which will time out.

Another Way of understanding the Solution
Actually you can also interpret the solution as an application of two pointer method.

Two pointer method
Assume that [i, j] is the your current valid segment/ window. If you go from i to i + 1, and the segment [i + 1, j] still remains a valid segment, then you can apply this method. So you can consider that when going from left to right, if you maintain a pointer for the right end of the good segment, then the right end of the segment always keeps on increasing.

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
You can notice that if the segment [i, j] is a valid segment (ie. a segment containing numbers having their lcm equal to their product), then the segment [i + 1, j] is also valid. When we want to extend the right end of our current segment (ie. we are looking at validity of segment [i, j + 1] considering that we know that segment [i, j] is valid), we need to check whether the current number has any common divisor (prime divisor will also work) with any number in the window. This check can be done easily by using the Cal array as explained above.

Overall complexity of this method is O(N).

AUTHOR'S and TESTER'S SOLUTIONS:

Author's solution Tester's solution

This question is marked "community wiki".

asked 22 Sep '14, 00:14

devuy11's gravatar image

4★devuy11 ♦♦
56273842
accept rate: 0%

edited 27 Sep '14, 13:14

jaskaran_1's gravatar image

3★jaskaran_1
525233550

1

solution links broken..

(22 Sep '14, 00:19) rishul_nsit4★

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

(22 Sep '14, 22:42) kk_cool2★

Extremely strict time limit!! There should not have been any need to pre-compute factors of every number beforehand. Good question ruined only by the imposition of tight time limit!

link

answered 22 Sep '14, 00:18

rishul_nsit's gravatar image

4★rishul_nsit
78351020
accept rate: 0%

1

You don't need to compute all the factors, You can only work with prime factors.

(22 Sep '14, 00:22) dpraveen ♦♦4★

I didn't mean all factors. Prime factorization of every number could be calculated on the fly instead of pre-computation. Nevertheless learnt something from the question so no qualms :) PS: There is no python solution which clearly given an idea about the strict time limit.

(22 Sep '14, 00:26) rishul_nsit4★

You can compute on the fly but it's time complexity would be different.

(22 Sep '14, 00:30) dpraveen ♦♦4★

Can you provide a worst case for computing on the fly? Provided I cache them as and when I calculate them. That is I don't compute the factors of any number more than once.

(22 Sep '14, 00:46) rishul_nsit4★
3

10^5 numbers each number 720720

(22 Sep '14, 01:54) dpraveen ♦♦4★

I used sieve to calculate the smallest prime factor(spf) of every number less than 10^6. Then I was calculating the prime factors for each number using the method of repeatedly dividing by the spf in a loop until the number is greater than 1. For this loop, most number of iterations will be 20 for 2^20. I used a set to store the prime factors which would balance out as when number of distinct prime factors would be more, the number of loop iterations would be less and vice versa. So the worst case complexity for single test case would be 20*(10^5) = 2*(10^6). Then I was using the two pointer method that was explained above. I got TLE using this approach. I would like to know if there was a test file in which all test cases were identical?

[Edit]

"Yes, there was a file in which all the test cases were identical. It was n = 10^5 and all numbers being 720720."

I don't have much experience in problem setting but I don't think this is a good practice. The primary purpose of including 't' in the problem is that complete testing can be done in less number of files. Usually 't' is not included in the time complexity. Repeating the test case 50 times means you are essentially making n=5*(10^6). So in most problems time limit is such that if the solution can pass the worst test case within the time limit, it should be able to pass all test files. Even when all test cases have the maximum limits, t is usually less than equal to 10. 50 makes the time limit extremely strict. Maybe one of the more experienced problem setters can comment on this.

link

answered 22 Sep '14, 01:06

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

edited 22 Sep '14, 03:17

Yes, there was a file in which all the test cases were identical. It was n = 10^5 and all numbers being 720720.

(22 Sep '14, 01:29) dpraveen ♦♦4★

Kudos to Tester's solution...very readable! Thanks.. :)

link

answered 22 Sep '14, 11:16

akumar3's gravatar image

3★akumar3
1416
accept rate: 0%

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;

link

answered 14 Oct '14, 20:54

caioaao's gravatar image

3★caioaao
11126
accept rate: 0%

Shouldn't this be Dp[i] = max(Dp[i-1]+1 , i+1 - Cal(i) ) instead of Dp[i] = min ( Dp[i-1]+1 , i+1 - Cal(i) )

link

answered 22 Sep '14, 01:48

rahul_nexus's gravatar image

3★rahul_nexus
7741923
accept rate: 13%

We have to take the smaller one... what if i+1 - Cal(i)<dp[i-1]+1... then within the length of dp[i-1]+1 there is a number that is not coprime with the ith element .. therefore we have to take the valid segment which is the smaller one

(22 Sep '14, 02:27) usaxena957★

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 * 32 => { 2=1, 3=2 }

link

answered 22 Sep '14, 01:54

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

To Editorialist : Some accepted solutions are giving wrong answer for case : 2 46093 92186 . Please consider this case .

link

answered 22 Sep '14, 04:33

shalini11's gravatar image

3★shalini11
11
accept rate: 0%

edited 22 Sep '14, 10:55

Please anyone expalin how is this working Dp[i] = min ( Dp[i-1]+1 , i+1 - Cal(i) )

link

answered 22 Sep '14, 10:23

cbgiri_001's gravatar image

4★cbgiri_001
-3113
accept rate: 0%

Could somebody explain me this in the Tester's solution:

if(i)
       {
           best[i] = MAX(best[i-1],x);
           ans=MAX(ans,i-best[i]);
       }
       else
         best[i]=-1;
   }

And how does it function similar to

dp[i]=min(dp[i-1]+1,i-Cal(i))
link

answered 27 Sep '14, 16:03

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

Easy with sliding window algorithm...(or kadanes algorithm)

link

answered 03 May '15, 11:23

gchandel6's gravatar image

4★gchandel6
24226
accept rate: 25%

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

link

answered 23 Sep '15, 15:56

georgejoseph's gravatar image

4★georgejoseph
16
accept rate: 0%

a really nice problem :)

link

answered 24 Nov '15, 21:38

spinxo's gravatar image

2★spinxo
1
accept rate: 0%

Great problem and a great editorial _/\_

link

answered 25 Jan '16, 20:59

lakshmi8's gravatar image

2★lakshmi8
461
accept rate: 14%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×2,595
×2,170
×877
×119
×93

question asked: 22 Sep '14, 00:14

question was seen: 14,109 times

last updated: 25 Jan '16, 20:59