I used a similar way but got a wrong answer, please help here’s my solution.
https://www.codechef.com/viewsolution/35669865
@souradeep1999 @faisal1947 @jyoti369
thank you so much,
just one question that is why do i get O[n*2] when I used elif when checking x+y in wall
im glad it helped @tn6541
x+y in wall: is O(N) time (linear search in list internally)
and this is inside loop which runs q times hence it becomes O(q*N)
thats why i made a set of all a’s elements ,x+y in set is O(1)
1 Like
when you declare a local variable it is stored in the stack memory
Global variables are stored in heap memory.Online compilers mai often there is a limit of stack memory.Heap memory limit is large.
So to search an elements in a set is faster than in a list?
https://www.codechef.com/viewsolution/35674052
This is my solution approach. Please help to find error in the code, I am getting wrong answer.
bro @pranava23 could not understand ur approach,
will u plz let me know how did u approached because its certainly not similar to anyone approach i have seen and debug so far.
thank you.
brother @tech_29
i don’t know java much but i tried to debug:
portion of your code:
while(q>0){
int x = sc.nextInt();
int y = sc.nextInt();
int result = 0;
for(int i=0;i<n;i++){
if((x+y)==a[i]){
result = -1;
break;
}
}
if(result==0){
for(int i=0;i<n;i++){
if(a[i]>x && a[i]>y)
break;
else
result++;
}
}
error in line 32(of ur submitted code)
if(a[i]>x && a[i]>y) should be if (a[i]>x+y):
after also after loop check
if a[i]>x+y:
print i+1
else:
print(i)
anyways:
no need two separated for loops both can be done in single loop
moreover:
even if u rectify mistakes u would get TLE since for overall complexity would become (q*N) use BS instead of for loop
please let me know if anything is unclear
hope this helps
Try upper_bound() -1
When you use lower_bound it gives you one greater index of the element lower Or exact. So, if your element is at n-1 position it will return n.
In upper_bound-1.
If index == -1
Cout<< 0
Else if (v[index] == x+y)
Cout<<-1;
Else
Cout<< index+1
You will get correct answer hope you get it 
- Found the min distance of the line from the origin which is the length of the normal.
For q queries I checked - Used the equation y=(-x) + c to check if it lies on the line
- Then found the distance of the given point, from origin which I compared to the arr containing distances
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t>0){
t--;
int n;
cin>>n;
vector<long> a;
long temp;
for(long i =0;i<n;i++){
cin>>temp;
a.push_back(temp);
}
//sort(a.begin(),a.end());
long q;
cin>>q;
long ans = 0;
long x=0,y=0;
auto it = a.begin();
for(long i=0;i<q;i++){
cin>>x>>y;
it = lower_bound(a.begin(),a.end(),x+y);
if(*it == x+y)
cout<<-1<<endl;
else{
ans = (it - a.begin());
/*
if(it == a.end() || *it < x+y)
ans = n;
if(ans > n)
ans = n;
if(ans < 0 || it == a.begin())
ans = 0;
*/
cout<<ans<<endl;
}
}
}
return 0;
}
I can’t see why i am getting WA here…
help!
https://www.codechef.com/viewsolution/35730710
@faisal1947 Can you help me out with this question, I got the correct answer for the sample test case but when I submitted I got RUNTIME error
I have done similarly. I am still getting TLE. Can anyone please help me?https://www.codechef.com/viewsolution/35732644
hey @tanmayi33 ,
u r getting TLE because u r doing linear inside while(q–) loop:
which makes ur code O(Q*N)
instead make a flag and set it to false,
implement Binary search inside while loop instead of for loop;
if u find a[mid]==x+y then flag=True-> break ->print -1
thankyou bro @mr_bluesky16 got AC.but didn’t got the logic of wrong ac by using lower_bound .as mentioned in the problem a1<a2<a3<…<aN so we can use lower_bound na?? .can u explain
Well as I explained above if you use lower bound it will return n if your element is at n-1 position. So, you can try to use lower_bound() -1 maybe it will work like upper_bound() -1. I told you to use upper_bound() -1 because it always works for me. But i think lower_bound() -1 will also work. But i never tried 
@mr_bluesky16 but lower bound works like if x+y is present at i=0 it will give 0,if present at n-1,it will give n-1 and if every element is less than x+y in the array then it will give size of array i.e n
so everything seems right
can u give an example where this is going wrong 
can anyone help me why this two condition(1 and 3) are valid??