STRNG Editorial

editorial
, ,
1

PROBLEM LINK:

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

Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

To be Calculated

PREREQUISITES:

None

PROBLEM:

Chef has an array A of length N.

An index i is called strong if we can change the gcd of the whole array just by changing the value of A_i.

Determine the number of strong indices in the array.

EXPLANATION:

Observation 1: GCD of any number with 1 is 1.

In case the gcd of whole array is not 1, then it means that none of its elements is 1, so we can change any element to 1, to make the gcd of the whole array as 1, thus all n indices would be strong indices in this case.

For the case when gcd of the array is 1, let us define two arrays as prefix\_gcd and suffix\_gcd, where

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

Now we iterate over all the indices of the array and for a particular index say, i, if gcd(prefix\_gcd[i-1],suffix\_gcd[i+1]) is equal to 1 then no matter what the value of A_i, it can’t change the value of gcd of the whole array (which would be 1), so it won’t be a strong index else in any other case it will be a strong index, because we can set A_i to be gcd(prefix\_gcd[i-1],suffix\_gcd[i+1]), and that will become the gcd of the whole array.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

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

2 Likes
2

what’s wrong in my code?

#include

#include <unordered_map>

#include

#define ll long long

#define un unsigned

#define mp unordered_map

#define INT_MAX 2’147’483’647

using namespace std;

const int mod = 1e9+7;

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t;

cin >> t;

while (t--){

    int n;

    cin >> n;

    int arr[n];

    int gcd = 0;

    int index1 = -1;

    int index2 = -1;

    for (int i = 0; i < n; i ++){

        cin >> arr[i];

        if (i == 0){

            gcd = arr[i];

            continue;

        }

        gcd = __gcd(gcd, arr[i]);

        if (gcd == 1 && index1 == -1){

            index1 = i;

            index2 = i-1;

        }

    }

    //cout << "index1 : " << index1 << '\t' << "index2 : " << index2 << '\n';

    if (gcd != 1){

        cout << n << '\n';

        continue;

    }

    if (n == 2) {

        if (arr[0] != arr[1] && arr[0] != 1 && arr[1] != 1)

        cout << 2;

        else if (arr[0] != 1 || arr[1] != 1) cout << 1 ;

       

        else cout << 0;

        cout << '\n';

        continue;

       

    }

    gcd = 0;

    for (int i = 0; i < n; i ++){

        if (i == index1 || i == index2){

            continue;

        }

        if (gcd == 0){

            gcd = arr[i];

            continue;

        }

        gcd = __gcd(arr[i], gcd);

    }

   

    // cout << "__gcd(gcd, arr[index1]) :  " << __gcd(gcd, arr[index1]) << '\n';

    // cout << "__gcd(gcd, arr[index2]) :  " << __gcd(gcd, arr[index2]) << '\n';

   

    if (gcd == 1) cout << 0;

    else if(__gcd(gcd, arr[index1]) != 1 && __gcd(gcd, arr[index2]) != 1 ) cout << 2;

    else if (__gcd(gcd, arr[index1]) != 1 || __gcd(gcd, arr[index2]) != 1 ) cout << 1;

    else cout << 0;

    cout << '\n';

   

}

return 0;

}

3

Here the first thing is that if GCD is not 1 -->ans =n
Now ,
If count of1>=2 -->ans =0;
else if count of 1==1 → gcd(left_gcd , right_gcd)!=1 -->ans =1 else 0
else //All are primes
checking that a prime exists n-1 times or not
if exist ans = cnt of that
else zero

1 Like
4

My code does this But getting wrong how???

5

I implemented the approach provided in the solution video of Strong Elements. But few testcases are giving wrong answers. Can anyone please help me to figure out what is wrong in my code?

6

Hi CodeChef Team,

I noticed that the below or similar test case is missed in the test set for validation

Input:
1
3 5 10 15 20

Expected Output:
1

But Code with Output 0 is also accepted

7

It was an easy question unfortunately i missed the 1==1 cond^n;“v_v”

8

Why use vector rather than array?