CLPNT EDITORIAL

editorial
, , , , ,
23

Yeah Sure, basically those line are just including the order statistic tree/ordered set, you can check this it out in case you are not much familar with it

1 Like
24

https://www.codechef.com/viewsolution/35675507
I have applied binary search too, but not getting the answer.
please have a look.

25

thank you!!

26

this might help:CodeChef: Practical coding for everyone

27 
        auto ind = lower_bound(a.begin(),a.end(),val)-a.begin();
        if((x+y)==a[0])ind++;

does this work same way as the ordered_set

28

That would not matterā€¦ for N walls a.size. If the last coordinate after the last wall lowerbound will return size+1. (here size =N-1) so the answer would stay correct.

29

itā€™s matterā€¦because if pos==n then a[pos] will throw run time error.
here is the link of your AC submission using vector. CodeChef: Practical coding for everyone

1 Like
30

Yeah I just saw what a horrible coincidence is causing the WA. my lowerbound isnā€™t returning incorrectly but rather the values at that position are matching up which is returning -1

Thanks
a,end() is causing the mess up

31

Yeah itā€™s O(n).

32

Right there is a run-time error which is being displayed as WAā€¦

Doesnā€™t codechef have anything to display run-time error? There is SIGSEV and SIGFTPā€¦

I can see a RE tag mentioned in the FAQ but I donā€™t knowā€¦

33

Ya it should ,
this thing messed my whole contest.

34

Two exactly same code.

  1. CodeChef: Practical coding for everyone
  2. CodeChef: Practical coding for everyone

1st got WA but 2nd got AC. How is this possible?

1 Like
35

I used lower bound and similar solution was uploaded by someone else and i was getting WA but the other solution got AC, can you please help me figure out the difference.

Inside the testcases loop-
// ll is long long.
ll n, i, x;
cin >> n;
vector a;
for (i = 0; i < n; i++)
{
cin >> x;
a.push_back(x);
}
ll q;
cin >> q;
for (i = 0; i < q; i++)
{
ll p, z;
cin >> p >> z;
p += z;
vector::iterator lower;
lower = lower_bound (a.begin(), a.end(), p);
ll cv = lower - a.begin();
if (a[cv] == p)
cout << ā€œ-1ā€ << endl;
else
cout << cv << endl;

}

Other Soln-
long long int n;
cin>>n;
long long int q[n];
for(long long int i=0;i<n;i++)
{
cin>>q[i];
}
long long int t;
cin>>t;
while(tā€“)
{
long long int x,y;
cin>>x>>y;
long long int s=x+y;
long long int d = lower_bound(q, q+n, s)-q;
if(q[d]==s)
{
cout<<"-1"<<endl;
continue;
}
else{
cout<<d<<endl;
}
}

36

I also faced the same issue, I tried both lowerbound as well as Binary search but was getting WA and a very similar soln was accepted

37

Can you please explain how you solved it with PBDS? I solved it with binary search.

38

I have used two approach and i think both are correct and same but the first one got WA while the latter one got AC. Here are the links:-

  1. wrong code- CodeChef: Practical coding for everyone
  2. correct code -
    CodeChef: Practical coding for everyone
    Can someone explain why its happening so?
39

This should not get accepted because lower bound can give n as return value but max array index is n-1 and in the next if statement you are trying to access that element. Which should give runtime error.

1 Like
40

Line 27

1 Like
41

The same case is withā€¦ exactly the same approachā€¦ one got WA other got AC

43

ohh right, Thankyou for helping me, btw this means that both solns shoud not get accepted right??