GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday, 2 October 2022

[Solution] Good Arrays CodeChef Solution


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.

Input Format

  • First line will contain T, number of test cases. Then the test cases follow.
  • The first line of each test case contains of single integer N denoting the length of the array.
  • The second line contains N space-separated integers A_1, A_2,\ldots, A_N representing the initial array.

Output Format

  • If there is a way to convert the given array into a good array, then:
    • In a single line, output X denoting the minimum number of operations required.
    • In the following X lines, output 2 integers - L and R denoting the left and right index of the subarray you want to reverse. Note that, (1\le L\le R\le N).
  • If there is no way to convert, print -1 in a single line.

Explanation:

Test case 1: We need only one operation to convert the array into a good array. Choose L = 2, R = 3 and reverse the subarray [2, 6] to [6, 2]. Thus, the final array is [3, 6, 2]. Note that in the final array, no subarray of length less than N has gcd equal to 1.

Test case 2: It is not possible to convert the given array to a good array using any number of operations.

Test case 3: The given array is already good. That is, no subarray of length less than N has gcd equal to 1. Thus, we need 0 operations.

No comments:

Post a Comment