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 
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
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