PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Aryan Agarwala
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given an array A, check whether it is closed under multiplication.
QUICK EXPLANATION:
It is enough to check that A is closed under multiplication of pairs.
The only ‘bad’ cases to check are:
- A contains more than 1 element whose absolute value is larger than 1
- A contains -1 twice but not 1
- A contains -1 and another element whose absolute value is larger than 1
EXPLANATION:
First, note that it is enough to check whether A is closed under multiplication of pairs.
Formal Proof
We proceed by inducting on the length of the chosen sequence.
Suppose we have verified that all products of k (k\geq 2) elements of A, are in A. We would like to extend this to k+1.
So, fixing a set of k+1 indices S_1, S_2, \dots, S_{k+1}, we want to find 1\leq x\leq N such that A_{S_1} \times A_{S_2} \times \dots \times A_{S_{k+1}} = A_x.
However, the inductive hypothesis tells us that A_{S_1} \times A_{S_2} \times \dots \times A_{S_{k}} = A_y for some 1\leq y\leq N.
So, what we really want is to verify whether A_y \times A_{S_{k+1}} = A_x for some x.
Thus, it is enough to verify that A is closed under products of pairs.
The question remains, how to do this? Playing around with a few examples leads us to the following:
- If A contains a and b such that |a|, |b| > 1, it cannot be closed under multiplication.
Proof
Since a, b\in A we must have ab \in A. However, |ab| = |a||b| \geq 2\cdot 2 = 4.
But then we must have a\times ab = a^2b \in A, and |a^2b| = |ab||a| \geq 8.
Continue this argument to see that a^{k}b \in A for every integer k \geq 1, and |a^{k} b| \geq 2^{k+1}, so A cannot be a finite set - contradiction.
- If A contains two occurrences of -1 but doesn’t contain 1, it cannot be closed under multiplication.
- If A contains a such that |a| > 1, and -1, it cannot be closed under multiplication. This is because A contains a and -1, so it must contain -a. Then we end up back in the first case.
In all other cases, A is closed under multiplication.
Proof
Let A be such that none of the 3 conditions above hold.
Then,
- If a\in A such that |a| > 1, we know that -1 \notin A. The remaining elements of A can only be 0 and 1, which cannot create any problems.
- Otherwise, the only possible values of elements are -1, 0, 1. Multiplication by 0 or 1 will never break closure - and if there is more than one -1, A will contain 1 by assumption so it remains closed.
ALTERNATE SOLUTION
The tester used bruteforce to reduce the number of cases to analyze.
After making the observation that there cannot be two numbers whose absolute value exceeds 1, it can be noted that any good array has at most 4 distinct values.
So, for any array with \leq 4 distinct elements, insert all distinct elements into an array. Then, insert into this array another copy of every element which occurs more than once.
We are left with an array of at most 8 elements - verifying that this array is closed under multiplication of pairs is equivalent to doing so for the original array.
Since the array is small, a quadratic bruteforce works just fine here.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
SOLUTIONS:
Tester's Solution
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin >> tests;
while(tests--){
int n;
cin >> n;
int a[n];
map<long long int,int> m;
int g2 = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
if(abs(a[i])>=2) g2++;
m[a[i]]++;
}
if(g2>=2){
cout << 0 << endl;
continue;
}
vector<pair<int,int> > v;
for(map<long long int,int>::iterator it = m.begin(); it != m.end(); it++){
long long int conv = (*it).first;
if(conv<0) conv = -conv;
v.push_back(make_pair(conv, (*it).first));
if((*it).second>1){
v.push_back(make_pair(conv, (*it).first));
}
}
sort(v.begin(), v.end(), greater<pair<int, int> >());
bool p = 1;
for(int i = 0; i < v.size(); i++){
if(p == 0) break;
for(int j = i+1; j < v.size(); j++){
long long int z = v[i].second;
long long int z2 = v[j].second;
long long int k = z * z2;
if(m[k]==0){
p = 0;
break;
}
}
}
if(p){
cout << 1 << endl;
}
else{
cout << 0 << endl;
}
}
return 0;
}
Editorialist's Solution
import collections
# input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = collections.Counter(a)
big = n - freq[0] - freq[1] - freq[-1]
if big > 1:
print(0)
continue
if big == 1 and freq[-1] > 0:
print(0)
continue
if freq[-1] > 1 and freq[1] == 0:
print(0)
continue
print(1)
