SUBGCD - editorial

editorial
, , ,
1

PROBLEM LINK:

[Practice][1]
[Contest][2]
Author: [Lalit Kundu][3]
Tester: [Tasnim Imran Sunny][4]
Editorialist: [Devendra Agarwal][5]

DIFFICULTY:

CakeWalk

PREREQUISITES:

math

PROBLEM:

Given an array A_1,A_2…A_N you have to print the size of the largest contiguous subarray such that GCD of all integers in that subarray is 1. Minimum size of the subarray is 2.

Solution:

Suppose gcd of a subarray is 1. Let us denote this subarray by S.

What is the gcd of this S and any other number ?

It is 1 . Reason : gcd of Subarray is 1 , and gcd(1,any_number) = 1

So , if there is a subarray whose gcd is 1, then any subarray containing this subarray will also have gcd 1.

What is the largest subarray in the whole array?

Full Array itself(i.e subarry of N elements)! If the gcd of all the array elements is 1 ,then answer is N.

Can you prove that if gcd of all the array elements is not 1, then answer is -1.

If gcd of all elements of all array elements is not 1 then it implies that there are no subarrays whose gcd is 1.[ You can prove by contradiction , Important point is that full array will contain all subarray’s ]

Pseudo Code


	for(int i=1;i<=N;i++){
		Read(Input) 
		gc = (i==1)?Input:gcd(gc , Input)  
	if ( gc == 1) print N
	else print -1

AUTHOR’S and TESTER’S SOLUTIONS:

[Author’s solution][6]
[Tester’s solution][7]
[1]: http://www.codechef.com/problems/SUBGCD
[2]: http://www.codechef.com/COOK50/problems/SUBGCD
[3]: http://www.codechef.com/users/darkshadows
[4]: http://www.codechef.com/users/rustinpiece
[5]: http://www.codechef.com/users/devuy11
[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/SUBGCD.cpp
[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/SUBGCD.cpp

7 Likes
2

Can someone explain why the largest subarray has to be the entire array?
Using the following example input:

1
5
2 2 4 5 7

Why wouldn’t the answer be 3 since {4,5,7} is the largest contiguous subset whose members have a GCD of 1?

4 Likes
3

**if the input is given as: 2 3 6

GCD: of 2 and 3 will be 1

GCD: of 1 and 6 will be again 1
**
the answer in this case will be 3

but it should be 2 as only the pair of 2,3 will have GCD 1 and 3,6 will be giving GCD = 2
but after reading the Tester Solution as well, still, I am having this doubt.

please correct me if I am wrong anywhere.

4

For the entire array the gcd is 1 also. gcd(2, 2, 4, 5, 7) = 1

4 Likes
5

I am adding a short explanation. Please check if you find it useful.

6

Btw, Answer of this case will be 3, because gcd(2, 3, 6) = 1.

7

@dpraveen please next time make your contest without that 502 or 503, it demotivates to code. thanks.

1 Like
8

In short: If the gcd of entire array is 1, then answer is n. Otherwise answer is -1. Proof is given in the editorial.

Finding gcd of entire array could be done like this.

g = a[0];  
for (int i = 1; i < n; i++)
	g = gcd(g, a[i]);
1 Like
9

for the input 2 3 6

g=2

iteration 1: g = gcd(2,3) = 1

iteration 2: g = gcd(1,6) = 1

answer will be 3 (according to the code)

but the actual answer must be 2

10

Why? Why the actual answer should be 2?

11

3 6 will give gcd as 2

there is only 2,3 subarray whose gcd is 1

12

The subarray [2, 3, 6] has gcd 1, So answer will be 3, why 2?

13

ohh…
thnks for correcting me :slight_smile:

14

Mention not :slight_smile:

15

Okay. I was interpreting it wrongly. The instructions said “GCD of all integers in that subarray is 1”, which I took to mean that the GCD of every pair of integers within the subarray had to be 1. Instead, it means that the GCD of all integers taken together is 1.

3 Likes
16

Test cases for this one were weak, my solution got accepted even when it returned -1 for array 2, 6, 3, correct answer is 3…

17

There’s something wrong with the judge, I can’t see how this code gives WA.

18

In the tester solution -
The comparisons inside the assert function for “t” and “n” are not correct. t has been compared with maxn whereas n has been compared with maxt, which can’t be right because t can go to 10 but maxn is 10000 and n can go to 10000 but maxt is 10 only.

19

Exactly. the question stated that!!!

20

beautifully different, great question for a cakewalk.

1 Like