Wave Solution TLE altough for a similar sol time is 0.08 sec

general
,
1

Link to que
https://www.codechef.com/COOK130B/problems/WAV2
Link to submission
https://www.codechef.com/COOK130B/status/WAV2,s1g1r
NOTE(in my above solutions i have used endl but even after trying \n it doesnt make much difference. )
The below code is for the que wave which gets solved in 0.08 seconds but the one below it is almost similar code to it(only difference is i have solved it through a function)but gets TLE. I am new to CP,can anyone help me understand why its happening.
Code 1 TL 0.08 sec
link to code 1https://www.codechef.com/viewsolution/48230408
Link to code 2 TLE
https://www.codechef.com/viewsolution/48230751
Link to code 3 TLE(almost similar to sol 1)
https://www.codechef.com/viewsolution/48230828

Code 1 TL 0.08 sec

#include<bits/stdc++.h>
using namespace std;

void solve(){
int n,q;
cin>>n>>q;
vector arr;
for(int i=0;i<n;i++){
int k;
cin>>k;
arr.push_back(k);
}
sort(arr.begin(),arr.end());
for(int i=0;i<q;i++){
int d;
cin>>d;
auto it = lower_bound(arr.begin(), arr.end(), d);
int k = it - arr.begin();
if(k==arr.size()){
cout<<“POSITIVE”<<"\n";
}
else if (arr[k] == d) {
cout << “0” << “\n”;
}
else if(k%2==0){
cout<<“POSITIVE”<<"\n";
}
else {
cout << “NEGATIVE” <<"\n";
}
}
}
int main(){

#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
freopen(“error.txt”,“w”,stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}

Code 2 TLE

#include<bits/stdc++.h>
using namespace std;

string find(vector arr,int d){
if(d<arr[0])
return “POSITIVE”;
else if(d>arr[arr.size()-1])
return “POSITIVE”;
auto it= lower_bound(arr.begin(), arr.end(), d);
int k=it-arr.begin();
if(arr[k]==d)
return “0”;
if(k%2==0)
return “POSITIVE”;
else
return “NEGATIVE”;
}

void solve(){
int n,q;
cin>>n>>q;
vector arr;
for(int i=0;i<n;i++){
int k;
cin>>k;
arr.push_back(k);
}
sort(arr.begin(),arr.end());
for(int i=0;i<q;i++){
int d;
cin>>d;
string s=find(arr,d);
cout<<s<<"\n";
}
}
int main(){

#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
freopen(“error.txt”,“w”,stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
2 Likes
2

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

While I’m waiting for this, check that your find function takes arr by reference instead of by value.

3

This is O(n) because it makes a copy of your string.
In the first solution, they use lower_bound which is binary search O(logn)

1 Like
4

same problem bro
due to this problem sometimes i feel like i shouldn’t solve questions on codechef
if anybody can really provide some insights it would be very helpful

5

Done. Thanks for the link.

6

Not really :confused: The updated code you posted is still completely mangled.

7

Can u submit this code of Hidden cell problem from lunchtime, when I m submitting it’s showing internal error.
Link :- CodeChef: Practical coding for everyone

8

I have added the links. If it doesnt work this time too then i am sorry.

1 Like
9

I have done a solution where i print it without coping the string (code 3 link) but even that gives TLE.

10

Thanks, they work - see the Edit in my first post (turns out that you are indeed taking arr by value - you’ll need to take it by reference instead) :slight_smile:

1 Like
11

Thank You for your help. Now it is running on time. I didnt know calling it without “&” will make it call by value.

1 Like