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.
You got it right
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.
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?
Thanks for commenting, try
Test case
1
1 2
4
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
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