PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Tejas Pandey
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra
DIFFICULTY:
2828
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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
Now we would loop through the array and at any element, say A_i, we would check if
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.
TIME COMPLEXITY:
O(N), for each test case.