Given an array of positive integers, determine if it is possible to make all the elements in the array equal by adding non-negative number to its elements such that the sum of the added numbers is exactly M.
EXPLANATION:
For the given array A of size N, we want to determine whether it is possible to make all its elements equal by adding non-negative numbers to them. Let as assume that it is possible to do so and the final value of the elements is x.
This means the following two conditions must hold:
x >= A[i], for all i, and
sum of (x - A[i]) is M.
From the second condition, we can actually compute the value of x:
(x - A[1]) + (x - A[2]) + … + (x - A[N]) = M
x = (M + A[1] + A[2] + … + A[N]) / N
If x is not an integer, then clearly we do not have a solution. Hence, we need to check the following two conditions for the existence of a valid x:
(M + A[1] + A[2] + … + A[N]) must be divisible by N,
None of the elements of the array should exceed x = (M + A[1] + A[2] + … + A[N]) / N.
The x must hold : x>= max(A[i]) of the original array. So that all array elements become equal in the end.
Time Complexity:
O (N)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.
About this problem: my nephew chose this problem for me and I solved it in 8-9 minutes ACed solution. He was happy, and my approach was: take the sum of array, add m to it and if it’s divisible by N then Yes else No.
But I now know that it’s not correct. It should have showed WA, but it didn’t.
For this case: N = 6, A = [1, 12, 12, 12, 12, 12], M = 5
sum(A) + M = 61 + 5 = 66.
Now 66 IS divisible by 6, so your solution would say “Yes” when clearly the answer is “No”. Unless I am missing something we got weak test-cases here.
@grebenesieh: I did it with the same logic, and now I have a question that even though you stated a weak case here, how come the judge accepted the solution?
Like I said, “weak test-cases”. Your code isn’t checked by some AI for correctness, it is just ran against a set of pre-defined inputs and if it gives the expected answer every time you get an accepted result. Clearly, the example I give above (or any variation of it) is not a part of their pre-defined inputs.
I took the sum of the heights of all the columns and M cubes and ultimately checked if the total sum was divisible by N (no. of columns) or not. My solution was accepted (my solution) but as stated by grebnesieh, the weak case i.e. when N=6, A=[1,12,12,12,12,12],M=5, the logic produces a ‘YES’ whereas it should produce a ‘NO’. So is it that the judge missed this case, is my code incorrect?
i found the max of array ,added value array elements A[i]-A[N] from M to equal max.
if M<0 it is a ‘NO’ if M=0 then it is ‘YES’.
if M > 0 ,dividing it by N print ‘YES’ if 0 or ‘NO’ if not.
this logic sounds pretty solid ,but it says wrong answer when submitted.
As I did, substract all elements of array from largest element and add the results of each substractions (Find least number of cubes of ground needed to make all columns in level). If sum is less than m then “No” and if equal to m then “Yes” and if greater than m then check whether (m - sum) is divisible by n or not. If divisible (level of each columns can be further increased by (m - sum)/n) then “Yes” otherwise “No”. http://www.codechef.com/viewsolution/4955148
As already stated, there were weak test cases for this problem. Some people haven’t checked for the second condition that final value of all elements should be greater than or equal to max element of the original array. E.g. for the first sample case:
5 7
3 3 4 2 1
We have sum=13, m=7 and n=5. So here, (sum+m)%n = 20%5 = 0 and hence some people report answer as ‘Yes’ which is incorrect.
If however we are given m=2 for above case, (sum+m)%n = 15%5 = 0 but still answer is ‘No’ because here (sum+m)/n = 15/5 = 3 is not greater than or equal to 4 (which was the max element in the array).
I know what “some people” means here, yup it’s incorrect but accepted. If it were incorrect(WA) at 3:09 p.m on 3rd of October, I’d have surely rechecked but it showed ac so why bother now
#include<stdio.h>
int main() {
int t, n, m, sum, highest, i, num, reqd;
scanf("%d", &t);
while (t-- > 0) {
highest = 0;
sum = 0;
i = 0;
scanf("%d%d", &n, &m);
while (i < n) {
scanf("%d", &num);
sum += num;
highest = (num > highest) ? num : highest;
i++;
}
reqd = (highest * n) - sum;
if (reqd > m) {
// If reqd number of blocks is more than available.
printf("NO\n");
} else if ((m - reqd) % n == 0) {
// If after making all columns equal to height of tallest column,
// remaining is equally distributable amongst them.
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
http://www.codechef.com/viewsolution/5150687 is the accepted version of your code. you were fixing size of a to be n when n was not defined or had some garbage value. also your logic was not correct.
I did it with the same logic, and now I have a question that even though you stated a weak case here, how come the judge accepted the solution? SERPLinker
Can anybody please tell what is the need for checking condition (m-sum) divisible by n? Why can’t we simply check the condition sum==m as we have to use EXACTLY m blocks. Plz help. Getting a WA.
