CASH - Editorial

Did you think I would put the word proof without providing a proof? That seems pretty dumb. Also, there is arrow on the left of the word, suggesting that it requires interaction. Anyways, good that you found it now.

1 Like

You got it right :laughing:

1 Like

Thanks for the solution. For those who would be thinking it was supposed that each element in Array should be divisible by K . For that in given example1
k = 7
1 14 4 41 1
T = 61 mod 7 = 5
An = 1 which is small than 5.
so try to get 4 from previous element , Array becomes 1 14 4 37 5.
now we subtract 5 from last element array becomes 1 14 4 37 0. As we know now sum is divisible by k,we remove Ai%k from from ith elements and add to last element,
Array becomes 0 14 0 35 7.all elements divisible by K.

similarly for next example
T = 30 mod 9 = 3
1 10 16
Make array as 0 9 18

Please help, I am new in this community.

T = int(input())
for i in range(T):
N, K = input().split()
bag = []
for i in range(int(N)):
val = int(input())
bag.append(val)
bagSum = sum(bag)
print(bagSum%int(K))

This is my Python code for the problem and its failing can any one help to resolve how this…

Remove

for i in range(int(N)):
val = int(input())
bag.append(val)

And add

bag=map(int,input().split())

The numbers are space seperated, not in different lines.

1 Like

Can you please help me why this code doesn’t work?

import java.io.*;
import java.util.*;
import java.lang.*;


class HARD_CASH {

  public static void main(String[] args) throws java.lang.Exception {
Scanner input=new Scanner(System.in);
int noOfTestCases = input.nextInt();
for (int t = 0; t < noOfTestCases; t++) {
  int n = input.nextInt();
  int k = input.nextInt();
  long R = 0;
  int[] a = new int[n];
  long[] need = new long[n + 1];
  for (int i = 0; i < n; i++) {
    a[i] = input.nextInt();
    R = a[i] % k;
    need[i] = (k - R) % k;
  }

  long[] prefix = new long[n];
  prefix[0] = a[0];
  long[] suffix = new long[n+1];
  suffix[n-1] = need[n-1];
  for(int i =1;i<n;i++){
    prefix[i] = prefix[i-1]+a[i];
  }

  for(int j =n-2;j>=0;j--){
    suffix[j] = suffix[j+1] + need[j];
  }

  long res = Long.MAX_VALUE;
  for (int i = 0; i < n; i++) {
    if (prefix[i] >= suffix[i+1]) {
      res = Math.min(res, prefix[i] - suffix[i+1]);
    }
  }

  System.out.println(res);

}
  }
}

Can you explain your code?

I tried to put comments with the help of example.

import java.io.*;
import java.util.*;
import java.lang.*;


class HARD_CASH {

  public static void main(String[] args) throws java.lang.Exception {
    Scanner input = new Scanner(System.in);
    int noOfTestCases = input.nextInt();
    for (int t = 0; t < noOfTestCases; t++) {
      int n = input.nextInt();
      long k = input.nextLong();
      long R = 0;
      //      eg: a = {1,14,4,41,1}
      int[] a = new int[n];

      //     No of coins required to be multiple of k : eg: need = {6,0,3,1,6}
      long[] need = new long[n + 1];
      for (int i = 0; i < n; i++) {
        a[i] = input.nextInt();
        R = a[i] % k;
        need[i] = (k - R) % k;
      }

      //      Sum of coins that can be removed until index i eg: if a= {1,14,4,41,1} then prefix = {1, 1+14, 1+14+4, 1+14+4+41, 1+14+4+41+1}
      //      i.e prefix = {1, 15, 19, 60, 61}
      long[] prefix = new long[n];
      prefix[0] = a[0];
      for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
      }

      //      Sum of coins that can be put back until index i eg if need = {6,0,3,1,6} then suffix = {6+0+3+1+6,0+3+1+6,3+1+6,1+6,6}
      //      i.e suffix = {16,10,10,7,6)
      long[] suffix = new long[n + 1];
      suffix[n - 1] = need[n - 1];
      for (int j = n - 2; j >= 0; j--) {
        suffix[j] = suffix[j + 1] + need[j];
      }

      //      Compare the value of coins that can be removed from prefix at ith position and the coins that can be put back in i.e suffix at i+1 th position
      //      eg: at index i = 1 the maximum that can be taken out is prefix[1] = 15 and the maximum that can be put back in N-c bags is suffix[2] = 10 so R = 15 -10 = 5
      long res = Long.MAX_VALUE;
      for (int i = 0; i < n; i++) {
        if (prefix[i] >= suffix[i + 1]) {
          res = Math.min(res, prefix[i] - suffix[i + 1]);
        }
      }

      System.out.println(res);

    }
  }
}

are you talking about theatre problem?

1 Like

Thanks for commenting, try

Test case

1
1 2
4

1 Like

hi really loved your solution i couldn’t even think of this.
I mean how did you think of this approach that adding all the entries and then taking it’s mod with K will give us the solution ??

Plz guide me about the underlying maths concept, so that in future if i encounter with something close to this, then i would be able to solve it .

As I said in the editorial, I calculated obvious bounds first. In this problem, the obvious lower bound happened to be the answer.

sorry but i din’t get what is meant by obvious bounds ?
pardon me if i m eating up your time …

Maybe, proving that the answer is exactly x is very hard. However, proving the answer must be >= y or <= z may be much easier.

Can u tell where i m going wrong in this approach ? Any particular test case?https://www.codechef.com/viewsolution/30925795

Thanks, that really helped, you are doing a great job!

If any one is interested here’s a proof by induction:

Let the predicate P(n) be, that for any set of ‘n’ bags of coins you only have to get rid of ‘sum % k’ coins to make it so that each bag has an amount which is divisible by k.

Base Case:
P(1) is true as for any set containing exactly 1 bag, you only need to remove B1 % k coins or sum % k coins.

Inductive Step:
Lets take any set of ‘n + 1’ bags of coins like so: B1, B2 … Bn+1. Now select c = 1, or less formally, take B1 % k coins and move them to bag B2 (note that now B1 has an amount which is divisble by k and now we only have to worry about the rest of the bags), thus the new value of B2, or B2new is now B2 + B1%k. Now for the set of n bags B2new, B3, B4 … Bn+1, according to our predicate P(n), the minimum amount of coins needed to be removed for any set of n bags of coins is ‘sum % k’ or (B2new + B3 … Bn+1)%k
Now (B2new + B3 … Bn+1)%k = (B1%k + B2 + B3 … Bn+1)%k = (B1%k + B2%k + B3%k … Bn+1%k)%k(property of modulo) = sum_of_n+1_Bags % k.

Thus P(n+1) is also true. Q.E.D
If you want to learn more about how to do proofs I would recommend this playlist by MIT: MIT 6.042J Mathematics for Computer Science, Fall 2010 - YouTube

1 Like

@swapnil2201, a case for which your code fails
1
3 4
2 1 8

Your o/p:
0

Expected o/p:
3

I’ve done a proof by induction if that’s what you were looking for, just go down and you’ll see it.

can u explain it in brief ,like how can u arrived at that solution .
like how u got to know that sum%k will be the answer.@tmwilliamlin