MEBA - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Testers: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A. In one move, you can select two different indices i and j, and increase A_i by A_j.
Is it possible to make all the array elements equal?

EXPLANATION:

Observe that if you perform the operation on indices i and j such that A_i \gt 0 and A_j \gt 0, the new value at index i will be A_i + A_j, which is strictly larger than A_j.
In particular, it’s not equal to A_j.

A different way of looking at this is that, if A contains two unequal positive numbers before an operation, it’ll also contain two unequal positive numbers after the operation.
So,

  • If A contains two unequal positive numbers initially, it’s never possible to make all the elements equal.
  • Otherwise, all the non-zero elements of A are equal, in which case it’s obviously possible to make all the elements equal.
    This is done by repeatedly choosing indices i, j such that A_i = 0 and A_j \gt 0, which essentially just sets A_i to A_j.

In the end, all that needs to be done is to check whether all the positive elements of A are equal or not.
One easy way to do this is to compute the minimum and maximum of all the positive elements of A, and check if they’re equal.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    mn, mx = max(a), max(a)
    for i in range(n):
        if a[i] > 0: mn = min(mn, a[i])
    print('Yes' if mn == mx else 'No')
4

TestCase:
1
5
1 2 3 4 5

Link to 1st code: CodeChef: Practical coding for everyone (Output: NO)

Link to 2nd code: CodeChef: Practical coding for everyone (Output: YES)

Answer according to editorial code: No

Both of the above given codes are judged as correct answer. So please add some more strong testcases and recheck all the submissions for this problems.

2 Likes
5

Yes. I also checked both the codes and solution. He is absolutely right. So I also request to add this kind of test cases and take action accordingly.

1 Like
6

include
include
include
include
using namespace std;

int main() {
// your code goes here

int t;cin>>t;
while(t--){
    // check for only +ve element (>0 is equal or not)
    int n; cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    int mini = INT_MAX, maxi = INT_MIN;
    for(int i=0; i<n; i++){
        if(v[i]!=0){
            mini = min(mini, v[i]);
            maxi = max(maxi, v[i]);
        }
    }
    if(mini==maxi) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
	
return 0;

}

why does this code doesn’t work?
[edited – got it if all the elements are 0 , i haven’t checked for that case)
if(mini==maxi || (mini==INT_MAX && maxi==INT_MIN)) cout<<“YES”<<endl;
]