CHEFGR-Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

Cakewalk

PREREQUISITES:

ad-hoc, basic math

PROBLEM:

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:

  1. x >= A[i], for all i, and
  2. 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:

  1. (M + A[1] + A[2] + … + A[N]) must be divisible by N,

  2. None of the elements of the array should exceed x = (M + A[1] + A[2] + … + A[N]) / N.

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

2 Likes

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.

1 Like

My solution fails for the following test :

6 0
6 5 5 5 5 4

Output should be “No”, but my solution prints “Yes”. And I got AC for this solution.

This was an important testcase that should have been included.

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

1 Like

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

1 Like

Hello there,

How about the answer for an input like this:

    N= 5 M = 16
Array = 3 4 4 2 1

As per my understanding this should output “Yes”, because at the end, all the elements of the array would be value 6 by spending all of M.

My solution would output “Yes” for this input, but it got WA.

~RKR


#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;
}

Can anyone please tell me why my solution got WA?

this is my answer to the given problem
http://www.codechef.com/viewsolution/5068935
can anyone please help me why this code generate SIGSEGV fault
thanks

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

instead of printing “YES” and “NO” you should print “Yes” and “No” respectively.
That is why you are getting wrong answer.

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.

First find the max of the array then find sum of how many each element of the array is short of max element…if this sum is greater than m then its false…otherwise check condition (m - sum) %n ==0
if it is true print yes else print false

#include<stdio.h>

#define s(a) scanf("%ld",&a)
typedef long int li;

int main()
{
li t,n,m,h[1024],i;

s(t);
while(t--){
	s(n); s(m);
	
	li max = 0;

	for(i=0; i<n; i++){
		s(h[i]);

		if( h[i] > max )
			max = h[i];
	}

	li sum = 0;

	for(i=0; i<n; i++)
		sum += ( max - h[i] );

	if( sum > m )
		printf("No\n");
	else
		( (m-sum) % n == 0 ) ? printf("Yes\n") : printf("No\n");
}
return 0;

}

thanks for sharing this post


Australian Assignment Help

I do not know it is giving wrong answer

/* package whatever; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;
class Cool
{
public static void main (String[] args) throws java.lang.Exception
{ Scanner sc=new Scanner(System.in);
int t;
t=sc.nextInt();
for(int j=0;j<t;j++)
{ int n,h,m;
n=sc.nextInt();
m=sc.nextInt();
int a[]=new int[n+1];
int max=0;
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
if(a[i]>max)
max=a[i];
}
int count=0;
for(int i=0;i<n;i++)
{ count+=max-a[i]; }
// cout<<count<<" ";
if(m-count>=0&&(m-count)%n==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}

}

}

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.

1 Like

put link to your solution