Hard Cash || Editorial 2.0

editorial
,
1

Chef wants to take Chefina on a date. However, he has to complete one more task before leaving. Since he does not want to be late, he is asking you for help.

There are N

bags with coins in a row (numbered 1 through N); for each valid i, the i-th bag contains Ai coins. Chef should make the number of coins in each bag divisible by a given integer K

in the following way:

  • choose an integer c

between 0 and N* (inclusive)

  • take some coins from the first c
    bags ― formally, for each i (1≤i≤c), he may choose any number of coins between 0 and Ai inclusive and take them out of the i* -th bag

  • move some of these coins to some of the last N−c
    bags ― formally, for each i (c+1≤i≤N), he may place a non-negative number of coins in the i

  • -th bag

Of course, the number of coins placed in the last N−c

bags must not exceed the number of coins taken out from the first c bags, but there may be some coins left over. Let’s denote the number of these coins by R. You should find the smallest possible value of R.

// SOLUTION AKA EDITORIAL

My Approach

In this question, I first traversed the whole Array and find the minimum number of coins you subtract from each of given coin so it is divisible by given number K and also stored sum of minimum number of coin you need to subtract.
Here vmodk[i] store minimum number of coin you need to subtract from ith coin so it is divisible by K
We find this simply by

for(long long i = 0;i<n;i++){
vmodk[i] = v[i]%k; // vmodk[] store minimum number of coin
sum+=vmodk[i];
}

Then we again traversed the whole array and find the number of coin you need to add (greater than 0) at each coin so it is divisible by K.
We do this simply by
Here vmin[i] store it
for(long long i = 0;i<n;i++)
{
long long j = v[i]/k;j++;
vmin[i] = j*k - v[i];
}

Now Everything is complete , We should only start with the end of array and traversed till we reach at start and perform follow steps

  1. sum = sum - vmod[i]; // It show we remove coins from 0 to ith position
  2. check if (sum<=0) then answer is sum+vmod[k]; break;
    else
    sum=sum-vmin[i];//It show we take out our needed coins to make it divisible
    if(sum<=0) then answer is sum + vmin[i]+vmod[i]; break;

My Solution Link -CodeChef: Practical coding for everyone

1 Like