PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Vibhu Garg
Testers: Utkarsh Gupta, Jatin Garg
Editorialist: Nishank Suresh
DIFFICULTY:
1604
PREREQUISITES:
Familiarity with gcd
PROBLEM:
You have an array A and an integer K. Let G = \gcd(A).
Find out whether there exist K disjoint non-empty subarrays in A with gcd g_1, \ldots, g_K such that \frac{g_1 + g_2 + \ldots + g_K}{K} = G.
EXPLANATION:
First, note that the gcd of any subarray of A will certainly be at least G, since G divides every element of A.
So, each g_i \geq G, which means the only way their average can equal G is if each g_i itself equals G.
So, we need to find if K disjoint subarrays in A have gcd G.
Note that since G divides every element of A, if we have a subarray whose gcd is G, extending this subarray to the right or left will still leave its gcd as G.
In particular, if a solution exists, then there will always exist a solution that covers the full array.
This gives us a simple algorithm to check:
- While the array is not empty, find the smallest prefix of the array with gcd G. If no such prefix exists, stop.
- This prefix (if found) will form one subarray in the answer. Remove this prefix and do the same to the remaining array.
The number of times we successfully performed the operation equals the maximum number of disjoint subarrays with gcd G that can be obtained. Check if this number is \geq K or not.
This can be implemented quite easily:
- Keep a variable denoting the current gcd, say g. Initially, g = 0.
- For each i from 1 to N:
- Set g := \gcd(g, A_i).
- If g \gt G, continue on
- If g = G, increase the answer by 1 and reset g to 0.
TIME COMPLEXITY
\mathcal{O}(N\log (maxA)) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
int gcd (int a, int b) {
if (b == 0)
return a;
else
return gcd (b, a % b);
}
int main(){
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector <int> v(n);
int G = 0;
for(int i = 0; i < n; i++){
cin >> v[i];
G = gcd(G, v[i]);
}
int currG = 0, count = 0;
for(int i = 0; i < n; i++){
currG = gcd(currG, v[i]);
if(currG == G){
count++;
currG = 0;
}
if(count == k) break;
}
if(count == k){
cout << "YES\n";
}
else{
cout << "NO\n";
}
}
return 0;
}
Editorialist's code (Python)
from math import gcd
from functools import reduce
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
G = reduce(gcd, a)
cur = taken = 0
for i in range(n):
cur = gcd(cur, a[i])
if cur == G:
cur = 0
taken += 1
print('Yes' if taken >= k else 'No')
