WAV2- Editorial

editorial
, ,
23

Find has an approximately linear time complexity @tushar_harsh. Check this out: http://www.cplusplus.com/reference/algorithm/find/

1 Like
24

@rogue_raven

25

According to your set, P(x) = (x - 1)(x - 3)(x - 5)(x - 100)(x - 120)
In this case putting your queries in place of x gives the following output which is expected from the problem:

NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

which does not match with your either of your expected or codeā€™s output. No idea how your code got AC.

26

Hey shouldnā€™t the actual output be :
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

27

I overlooked the negative sign. Yes, the expected output is

NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

Let me edit that.

28

ā€œPoor test casesā€ is the only reason. Author and tester are responsible for that.

29

oh ! all this time I thought it was constant, my bad not considering it, thanks !!

1 Like
30

Your code does not even pass the example test case. Please refer to the proper usage of lower_bound algorithm function. Your code got AC due to their poor test cases.

31

can someone explain TLE reason here
https://www.codechef.com/viewsolution/48057518

33

You are sorting the array Q timesā€¦just sort it once before taking the queries

1 Like
34

I have no idea what is the time complexity is. and I canā€™t see any constraint issue in the product variable.

35

Such a silly mistake I madeā€¦Thanks

37

Can somebody please explain why I am getting TLE here, I just tried a simple brute force approach. It would be kind if you also explain the complexities here, I didnā€™t understand the concept,
Link: Here is the solution: https://www.codechef.com/viewsolution/48416750

#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main() {
std::ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
int cnt,x,l;
while(qā€“){
cnt=0;
l=0;
cin >> x;
for(int i=0;i<n;i++){
int k = (x-a[i]);
if(x==a[i]){
l=1;
break;
}
else if(k<0){
cnt++;
}
}
if(l==1){
cout <<0<<endl;
}
else if(cnt%2 == 0)
cout <<ā€œPOSITIVEā€<<endl;
else
cout <<ā€œNEGATIVEā€<<endl;

}
return 0;

}

39 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*Finds the first occurence of number greater than a using binary search and returns 
(n-(index of the digit)) which is the number of values greater than a.
If a number is equal to a it returns -1*/
int bin(vector<int> v,int a,int n)
{
   int str=0,en=n-1,pos=0;
    while(str<=en){
        int mid=((str+en)/2);
        if(v[mid]>a){
            pos=mid;
            en=mid-1;
        }
        else if(v[mid]==a){
            return -1;
        }
        else{
            str=mid+1;
        }
    }
    return (n-pos);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     unsigned long long n,j,k;
     cin>>n>>k;
    vector<int> v;
            for(int i=0;i<n;i++){
                cin>>j;
                v.push_back(j);
            }
            sort(v.begin(),v.end());
     while(k--){
            int a;
            cin>>a;
            //If the number of values greater than a is even then it returns positive 
            cout<<(((bin(v,a,n)&1)==0)?"POSITIVE":((bin(v,a,n)==-1)?"0":"NEGATIVE"))<<endl;
            }
}

Can someone tell me where i went wrong. It would help me a lot. Thank you.

1 Like
40

bin should take v by reference instead of by value, to avoid TLE.

2 Likes
41

Yes. It is working now. Why does this work though??.

2 Likes
42

If you pass by value, you make a copy of v every time you call bin.

2 Likes
43

Ohh okay. Thanks a lot.

2 Likes
44

// help in debugging my code as it gives correct output on running customs //input but canā€™t submit successfully.

include
#include<bits/stdc++.h>
#include<bits/stdc++.h>

using namespace std;

int main() {
// your code goes here
int n,q;cin>>n>>q;
vectora;
for(int i=0; i<n;i++){
int a1;cin>>a1;
a.push_back(a1);
}
sort(a.begin(),a.end());
vector::iterator it;

while(q--){
    int x;cin>>x;
    if(binary_search(a.begin(),a.end(),x))cout<<"0";
    else{
        if(x<a[0]||(n%2==0&&x>a[n-1]))cout<<"POSITIVE"<<endl;
        else if(x>a[n-1]&&n%2!=0){
            cout<<"NEGATIVE"<<endl;
        }
        else {
            
        
    it = upper_bound(a.begin(),a.end(), x);
    int  it2 = it - a.begin();
    if(it2%2==0)cout<<"POSITIVE\n";
    else cout<<"NEGATIVE"<<endl;
        }
    }
}

return 0;

}