Can anyone please tell what’s wrong in this solution? Thanks in advance.
https://www.codechef.com/viewsolution/50154510
This is equivalent to the solution outlined in the editorial, you can verify that by considering cases.
I won’t consider all of them here (it’s just an exercise in writing if you’d like to try) but here’s a couple of insights:
- If the array contains two numbers whose absolute values exceed 1, then definitely at least one of the product of the two maximum elements, the two minimum elements, or the minimum and maximum element won’t be in the array. Your algorithm checks this.
(If you want to formally prove this part, consider cases of when there are two large positive numbers, two large negative numbers, and one large positive and one large negative number) - If there’s only one number whose absolute value exceeds 1 (say x), it will be either the minimum or maximum for sure. Then, either the array has a -1 (in which case -x isn’t in the array), or there is no -1 in which case the array has only 0's and 1's other than x which is not a problem. Your algorithm checks this.
- The only remaining case is when all the elements are -1, 0, 1. The only possible bad case here is if -1\times -1 isn’t in the array - but if -1 is in the array, it’s guaranteed to be the minimum so your algorithm verifies this as well.
2 Likes
1
1
0
1 Like
Just a doubt. Shouldn’t this be sufficient to check if the product of the two largest and largest and smallest is in the array? I am getting WA but not able to find a sample case to disprove it.
okay got it thanks for a quick reply.
1 Like
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long int t;
cin>>t;
while(t–)
{
long int n;
cin>>n;
long long int a[n];
long long int i;
for(i=0;i<n;i++)
{
cin>>a[i];
}
long long int c=0,c1=0,cn=0;
for(i=0;i<n;i++)
{
if(a[i]>1 || a[i]<-1)
{
c+=1;
}
if(a[i]==1)
{
c1+=1;
}
if(a[i]==-1)
{
cn+=1;
}
}
int flag=1;
if(c>1)
{
cout<<0<<endl;
flag=0;
}
else
{
if(cn>=2)
{
if(c1==0)
{
cout<<0<<endl;
flag=0;
}
}
}
if(flag==1)
{
cout<<1<<endl;
}
}
return 0;
}
could
anyone tell me why is it wrong
Consider the test input:
1
2
-1 -2
Hi @ssjgz ! Can you please check my submission I couldn’t figure out corner cases.
Here is submission link: CodeChef: Practical coding for everyone
1 Like
1
1
-2
(a set consisting of a single element cannot be un-closed with the definition used).
For those of you guys who are finding it difficult to convert python logic to cpp,I tried to the exact same code by the editorial in cpp . I have even added some comments which may help you .
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
int test;
cin >> test;
while(test--){
//enter the elements in the array
int n;
cin >> n;
int arr[n];
map<int,int> freq;
for(int i = 0;i < n; i++){
cin >> arr[i];
freq[arr[i]]++;
}
//this is to find those numbers which are not -1,0,1
int big = n - freq[1] - freq[0] - freq[-1];
//now there are three cases where answer is not possible
//case 1 : when there are more than two numbers where | a | > 1
if(big > 1){
cout << 0 << '\n';
continue;
}
//case 2:when there is -1 and another number |x| > 1
//extension of case 1
if(freq[-1] > 0 and big == 1){
cout << 0 << '\n';
continue;
}
//case 3:this is the case when there are greater then 2 -1 but no ones
if(freq[-1] > 1 and freq[1] == 0){
cout << 0 << '\n';
continue;
}
//if none of the above condition satisfies then the answer is possible
cout << 1 << '\n';
}
}
Can someone tell me issue in the following code?
public void solve(int TC) throws Exception {
// solution goes here
int n = ni();
long arr[] = new long[n];
Map<Long,Integer> mp = new HashMap<Long,Integer>();
for (int i = 0; i < n; i++) {
arr[i] = nl();
mp.put(arr[i], mp.getOrDefault(arr[i],0)+1);
}
int nOne = mp.getOrDefault(-1, 0);
int zero = mp.getOrDefault(0, 0);
int one = mp.getOrDefault(1, 0);
int other = n - nOne - zero - one;
int ans = 1;
if(other>1) ans = 0;
else if(other==1 && nOne>0) ans = 0;
else if(nOne>1 && one==0) ans = 0;
pn(ans);
}