DEVUGRAP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greatest Common Divisor

PROBLEM:

Given an array A[] of n numbers and k. Find the minimum number of operation (adding or subtracting one from some array position) that should be performed on the array such that the gcd of all the numbers in the modified array is divisible by k.

EXPLANATION:

We are given an array A[], a number k and we can perform only one operation that is adding or subtracting one from some array position, repeatedly modifying the array until the gcd of all the numbers of the array is divisible by k. The problem is to find the minimum number of operation to achieve this. Note that if all the numbers in the array is already divisible by k, then we don’t have to do anything and the answer will be 0.

Now consider the case where some numbers are not divisible by k (hence gcd is not divisible by k). In this case, pick up that number say a[i] = qk + r where r>0 and modify it to either qk or (q+1)k whichever takes minimum number of operations. One final point to note is that all the numbers in the modified array should be positive, so when a[i] < k, we can only increase its value to make it divisible by k. The time complexity of the above algorithm is clearly \mathcal{O}(n). Refer to the following pseudo code for better understanding

for i = 0 to n
    r = a[i] mod k
    if(a[i] >= k) ans += min(r, k-r)
    else ans += k-r

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

Tester’s solution can be found here

2 Likes
2

I think test cases are weak as if consider the test case where t=1 n=2 k=1 and numbers are 4,10. GCD of 4 & 10 is 2 which is not equal to 1 but the solution gets accepted showing answer equals to 0.

3

The GCD should be divisible by k

Hence, since 2 is divisible by 1 , the answer is zero

4

Got it. i did mistake in reading the question. sorry for silly question.

5

I submitted the code using the above pseudo code but got only 20 points.
It failed for Task 3. Please help. My code:
http://www.codechef.com/viewsolution/7056995

6

INT_MAX = Maximum value for an object of type int in c = 32767 (2^15-1)

your values of n and k are 10^5 and 10^9 respectively. taking input as int leads to a overflow and a change of values of these numbers.

use long and long long for n and k.

7

I got it mohitbura.
long long should be used only for the answer
while int would work for n and k also.

8

Did the same mistake :stuck_out_tongue: superfluously 10^9 can be added 10^5 times .

9

#include<stdio.h>
#define min(a,b) a<b?a:b;
int main()
{
long long int a,b,n,k,i,c[100000];
int t;
scanf("%lld",&t);
while(t–)
{
long long int count=0;
scanf("%lld %lld",&n,&k);
for(i=0;i<n;i++)
{
scanf("%lld",&c[i]);
a=c[i]%k;
b=min(a,k-a);
count+=b;
}
printf("%lld\n",count);
}
return 0;
}
why my answer gives wrong answer

10

#include<stdio.h>
#define min(a,b) a<b?a:b;
int main()
{
long long int a,b,n,k,i,c[100000];
int t;
scanf("%d",&t);
while(t–)
{
long long int count=0;
scanf("%lld %lld",&n,&k);
for(i=0;i<n;i++)
{
scanf("%lld",&c[i]);
a=c[i]%k;
b=min(a,k-a);
count+=b;
}
printf("%lld\n",count);
}
return 0;
}
why my answer gives wrong answer

11

Can someone tell me why this code is not running?
#include <bits/stdc++.h>
using namespace std;
typedef long int ll;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin>>t;

while(t--){
    int n;
    ll k,x,cost=0;
    
    cin>>n>>k;
    for(int i(0);i<n;i++){
        cin>>x;
        ll r = x%k;
        if(x>=k) cost+=min(r,k-r);
        else cost+= r;
        
    }
    cout<<cost<<"\n";
    
}
return 0;

}