 # CLOSCHEF - Editorial

Author: Aryan Agarwala
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh

Simple

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
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = collections.Counter(a)

big = n - freq - freq - freq[-1]
if big > 1:
print(0)
continue
if big == 1 and freq[-1] > 0:
print(0)
continue
if freq[-1] > 1 and freq == 0:
print(0)
continue
print(1)

3 Likes

Even Different String is same as Find Unique binary string from today’s Leetcode contest.

3 Likes

they are same but look at constraints ?
n = 16 leetcode (exponantial solution would be accepted)
n = 100 codechef (we have to greedly construct the string)

1 Like

Maybe I’ve understood the problem wrong. For this testcase, the following sequence is closed under multiplication, but both the solutions (and the editorial) says otherwise.

1
10
1 5 2 10 0 20 0 50 0 100

1 Like

By definition, for the array to be closed under multiplication, you take any sequence of elements in it and their product must also be in the array.
A_6 \cdot A_8 = 20\cdot 50 = 1000 is not in the array, so your example isn’t closed under multiplication.

2 Likes

Doesn’t a sequence needs to be continuous? I mean if we are taking A_6 and A_8, A_7 must also be taken??

If that is not the case, they should have mentioned subsequence.

It was not specified in the problem statement, or I think I may be wrong. Anyway thank you.

Yes, it need not be continuous, I did the same mistake. In sample cases, they have shown that it need not be continuous.

Yes, same doubt.

I have implemented this solution in java but it is not accepting the solution.

https://www.codechef.com/viewsolution/50123574

I am not able to find mistake

Consider the test input:

1
3
-1 -1 -2

1 Like

OHHH, Thanks, bro.
BTW I don’t know why you suggested me this case.
But the problem was in last if conditions I should have used else-if
So, in your case, it printed 0 twice.
Now I fixed it & it got accepted

Thanks a lot

1 Like

#include<bits/stdc++.h>

using namespace std;

int main(){

int test;

cin>>test;

while(test--){

int n;

cin>>n;

int arr[n];

unordered_map<long long,int> mymap;

int g2 = 0;

for(int i = 0; i < n; i++){

cin>>arr[i];

if(abs(arr[i]) > 1) {g2++;}

mymap[arr[i]]++;

}

if(g2 > 1) {cout<<"0"<<endl; continue;}

bool check = true;

for(auto it1 = mymap.begin(); it1!=mymap.end(); it1++){

auto temp = it1;

for(auto it2 = ++temp; it2 != mymap.end(); it2++){

long long multi = it1->first * it2->first;

if(mymap.count(multi) == 0) {cout<<"0"<<endl; check = false; break;}

}

if(check) continue;

else break;

}

if(check) cout<<"1"<<endl;

}

return 0;


}

Because it’s not giving the right answers Consider the test input:

1
2
-1 -1


Ok Ok got it! Thankyou 1 Like
long long arr;

int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ctr = 0;
int ctr1 = 0;
int ctr2 = 0;
int ne = 0;
int po = 0;
long long zero = 0;
bool flag = false;
for(int i=0;i<n;i++)
{
cin >> arr[i];
if(arr[i] < 0)
ne++;
else
po++;
if(arr[i] == 1)
ctr2++;
if(arr[i] == 0)
ctr++;
if(arr[i] == -1)
ctr1++;
}
if(n ==1)
{
cout << 1 << endl;
continue;
}
if(n == 2)
{
if(arr * arr == arr || arr * arr == arr)
{
cout << 1 << endl;
continue;
}
else{
cout << 0 << endl;
continue;
}
}
if(ne == 0)
{
if(po - ctr - ctr2 == 0 || po - ctr - ctr2 == 1)
{
cout << 1 << endl;
continue;
}
else{
cout << 0 << endl;
continue;
}
}
else{
if(po == 0)
{
cout << 0 << endl;
continue;
}
else{
if(ctr + ctr2 + ctr1 == n)
{
cout << 1 << endl;
continue;
}
else{
cout << 0 << endl;
continue;
}
}
}
}
return 0;
}


I dont know but why my code fails .
if no negative element then number of element apart form 0 and 1 can be atmost one.
if only negative element then it cant be closed.
if both negative and positive are present then -1 , 0 , 1 are the only possible elements.

1
3
0 0 -2

1 Like

if both negative and positive are present then -1 , 0 , 1 are the only possible elements.

Not necessarily true. Consider

1
3
1 1 -5

1 Like

Thanks . I will have to redo it !!!  Can someone tell why this works

1. Sorting the array
2. Checking by multiplying the 1st element with rest of the elements.
3. Checking by multiplying the last element with rest of the elements.
And if there exists even 1 pair which does not satisfy this condition then 0 else 1.

Solution