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