GDSUBARR Editorial


Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Tejas Pandey
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra






Chef considers an array good if it has no subarray of size less than N such that the GCD of all the elements of the subarray is equal to 1.

Chef has an array A of size N with him. He wants to convert it into a good array by applying a specific operation.
In one operation, Chef can choose any subarray and reverse it.

Find the minimum number of operations required to convert the array into a good array and the operations themselves. If there are multiple ways to achieve the result, print any.
If it is not possible to convert the array into a good array, print -1 instead.

Note: A subarray of an array is formed by deletion of several (possibly zero) elements from the beginning and several (possibly zero) elements from the end of the array.


Observation \;1: Suppose the gcd(A_1,A_2....A_{n-1}) \neq 1 and gcd(A_2,A_2....A_{n}) \neq 1 , then our array would be good.
This is because if gcd of an array is greater than 1, then any subarray of it would have gcd greater than 1.

First thing we would do is precompute the suffix gcd and prefix gcd, such that

prefix[i] = gcd(A_1,A_2....A_i) \\ suffix[i] = gcd(A_i,A_{i+1},....A_n)

Now we would loop through the array and at any element, say A_i, we would check if

gcd(prefix[i-1],suffix[i+1]) \neq 1 ......(i)

If it satisfies we would either reverse the array A[1,2....i] or array A[i+1,i+2....n] with aim to satisfy the initial condition given in Observation \;1.
Now we can do this in atmost two operations. Initially we would check if prefix[n-1] \neq 1 or suffix[2] \neq 1. If both of these satisfies then no further operation is needed otherwise if any one of them satisfies then we would need one more operation otherwise if none satisfies we would need to do two operations.


O(N), for each test case.


Setter’s Solution
Tester1’s Solution
Tester2’s Solution

how is this O(N)
how will we calculate prefix and suffix gcd array ?

I guess you are talking about the log complexity of the gcd. It seems they just ignored it.

Can anyone explain me the intuition behind this solution ?