PSAS - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
It can be modified as follows:

  • Choose an index i. Then,
    • Add A_i to A_j for all j\lt i
    • Subtract A_i from A_j for all j \ge i

Is it possible to make all the elements of A equal by performing this operation several times?

EXPLANATION:

If all the elements of A are already equal, the condition is already satisfied; so let’s assume that A contains \ge 2 distinct elements.

In this case, we definitely need to perform an operation on A.
Observe that if we perform an operation with index i, then A_i will definitely become 0 (because we subtract A_i from A_i.)
So, after an operation, the array will surely contain at least one 0.

Thus, if we want to make all elements equal, it must be that everything is equal to 0 in the end.

Now we can make the key observation to this problem: if the first operation doesn’t make all elements equal to 0, no future operation can do it either!

Proof

As noted earlier, after the first operation the array will surely contain a 0.

Suppose not all elements are equal, so that the array also contains a non-zero element.

Now, when we perform another operation,

  • If the element we choose is equal to 0, the array doesn’t change.
  • If the element we choose is not equal to 0, it becomes 0.
    However, the previously existing 0 will now become non-zero, since a non-zero value will be either added to or subtracted from it.

Thus, no matter what we do, the array will still contain both 0 and a non-zero element.

This shows that we can never make the array elements all equal in the future as well.

So, it suffices to check if the first operation can make all the elements equal to 0.
Each operation can be simulated in \mathcal{O}(N) time, so we obtain a solution that’s \mathcal{O}(N^2) overall; which is fast enough for the given constraints.

It’s possible to further improve this solution to linear time, by observing that one operation can make an array all zeros if and only if it’s of the form

[C, C, \ldots, C, C, -C, -C, \ldots, -C, -C]

for some (not necessarily positive) integer C.

That is, some prefix of the array must have all the same value, and the remaining suffix must all have the negation of this value.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 'Yes'
    for i in range(n-1):
        if a[i] == a[i+1]: continue
        for j in range(i+1, n):
            if a[i]+a[j] != 0: ans = 'No'
        break
    print(ans)
2

Test Cases are weak
this code is passing:

cook your dish here

for _ in range(int(input())):
n = int(input())
l = list(map(int,input().split()))
#scnt = 0
prev = l[0]
f=0
for i in range(1,n):
if(prev==l[i]):
prev = l[i]
else:
if(prev+l[i]==0):
prev = l[i]
#scnt+=1
else:
f=1
break
if(f==1):
print(“No”)
else:
print(“Yes”)
But if take 1 -1 1 the answer is no we cannot make it.

1 Like
3

Agreed test cases are weak even below code passes the testcases
#include<bits/stdc++.h>
using namespace std;

define ll long long
define ld long double
define str string

void solve() {
int n;
cin>>n;
std::vector a(n,0);
set s;
for(int i=0; i<n; i++)
{
cin>>a[i];
s.insert(abs(a[i]));
}
if(s.size()==1) cout<<“Yes”<<endl;
else cout<<“No”<<endl;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll t; cin >> t;
while(t–)
solve();
return 0;
}
but it should not cause if array is [1, -1, 1, -1]
the output should be no but it the code says yes and it even passes the testcases