You are not logged in. Please login at www.codechef.com to post your questions!

×

DEVUGRAP - Editorial

2
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

asked 27 May '15, 15:54

saurabh060792's gravatar image

4★saurabh060792
1951916
accept rate: 0%

edited 01 Jun '15, 20:24

admin's gravatar image

0★admin ♦♦
19.1k348495534


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.

link

answered 31 May '15, 16:45

pranjal15's gravatar image

3★pranjal15
11
accept rate: 0%

The GCD should be divisible by k

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

link

answered 31 May '15, 16:53

vozille's gravatar image

3★vozille
11
accept rate: 0%

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

link

answered 31 May '15, 16:56

pranjal15's gravatar image

3★pranjal15
11
accept rate: 0%

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

(26 Jan, 22:45) code__champ3★

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

link

answered 01 Jun '15, 13:25

amal199404's gravatar image

3★amal199404
4114
accept rate: 50%

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

(01 Jun '15, 16:56) amal1994043★

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

(01 Jun '15, 20:01) randomizer4★

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.

link

answered 01 Jun '15, 15:09

mohitbhura's gravatar image

5★mohitbhura
261
accept rate: 16%

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

link
This answer is marked "community wiki".

answered 26 Jan, 22:38

code__champ's gravatar image

3★code__champ
594
accept rate: 0%

wikified 26 Jan, 22:40

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,828
×1,481
×282
×128

question asked: 27 May '15, 15:54

question was seen: 6,167 times

last updated: 26 Jan, 22:47