CLPNT EDITORIAL

editorial
, , , , ,
#1

PROBLEM LINK
Practice
Contest
Author and Editorialist: Souradeep Paul
Tester: Avijit Agarwal, Sarthak Manna

DIFFICULTY
Easy

PREREQUISTITES
Basic Math and Geometry, Binary Search

PROBLEM
There are N line segments and i'th segment connects points (a_i,0) and (0, a_i). You are also given Q queries and in each query given a point (x_i, y_i). For each query find the number of line segments present under this point and if the point already lies upon a line segment then print -1.

EXPLANATION
Equation of i'th line is x + y - a_i = 0, so for a point P(x_p, y_p) there are 3 possible scenarios,

  1. if x_p+y_p-a_i < 0, then P is under this line.
  2. if x_p+y_p-a_i = 0, then P is upon this line.
  3. if x_p+y_p-a_i > 0, then P is above this line.

So we can use binary search over the answer, let’s see how.
Now if you currently checking i'th segment and find that P is lying above the line then you have to break more line segment to allow Chef to reach (0, 0), so you can continue the searching upon upper half of the binary search. Otherwise, if P lie under the line then you are going to break more segments which is not possible as you can’t break segments which are above you, so you can continue the searching upon the lower half of the binary search. Lastly, if you find that P lies on a line in any step of binary search then you simply find that it’s not possible to reach (0, 0).
The time complexity is \mathcal{O}(Q\log{}N).

SOLUTIONS
C++ solution can be found here
Java solution can be found here
Python solution can be found here

#2

@souradeep1999 I have applied similar approach, but I am getting TLE. Can you please help me?
My solution link:-
https://www.codechef.com/viewsolution/35675507

1 Like
#3

Getting WA :confused:

#include <iostream>
#define ll long long
using namespace std;
bool check(ll a,ll b,ll arr[],ll size){
    ll lhs=0,rhs=0;
    for(ll i=0;i<size;i++){
        if((ll)(a+b) == arr[i]) return true;
    }
    return false;
}
int main(){
    int t;  cin >> t;
    while(t--){
        ll n;  cin >> n;
        ll a[n];
        for(int i=0;i<n;i++) cin >> a[i];
        ll q; cin >> q;
        for(int i=0;i<q;i++){
            ll x,y ,cnt=0;    cin >> x >> y;
            if(check(x,y,a,n)) cout << "-1\n";
            else {
                for(int i=0;i<n;i++){
                if((x+y) >= a[i]) cnt++;
                }
                cout << cnt << "\n";
            }     
        }
    }
    return 0;
}
#4

Solution in C++: https://github.com/strikersps/Competitive-Programming/tree/master/Code-Chef/Doof-On-Cartesian

#6

https://www.codechef.com/viewsolution/35691000 - This is my array submission
https://www.codechef.com/viewsolution/35690890 - This is my vector submission

Both are same but why does the vector one give WA?

@souradeep1999 please look into this. There is no difference in both solutions. It would be nice if someone can help me figure out the issue ( no matter how trivial it is )

#7

i have also applied the similar approach but getting TLE.
Can anybody help?
my solution:https://www.codechef.com/viewsolution/35677587

#8

It will give TLE.
Because its time complexity o(n**q);
Use Binary search instead for getting time complexity O(logn*q);
Here is my code with binary Search : https://www.codechef.com/viewsolution/35690902
Hope this helps. Thanks !!!

2 Likes
#10

I tried O(n*q) solution but it gives WA instead of TLE , can you tell me why it shows so ?

#11

I used a set because of two reason

  1. All the elements are distinct
  2. Searching is O(1) in an average case in sets for more info see this

My Accepted code in Python
https://www.codechef.com/viewsolution/35658126

You can ask me if you have any doubt regarding my solution or not able to understand

Thanks

#12

I think, Whenever a test case fails (as there are no subtasks) the verdict will obviously show WA without testing it furthur.

1 Like
#13

My short solution using policy-based data structures

AC_SOLUTION 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
void solve(){ 
  int n,x,y,q;cin >> n ;
  oset<int>s ;
  FOR(i,n){
    int x;cin >> x;
    s.insert(x);
  }
  cin >> q ;
  FOR(i,q){
    cin >> x >> y ;
    if(s.find(x+y)!=s.end())
      cout << "-1" << "\n" ;
    else
      cout << s.order_of_key (x+y) << "\n" ;
  }
}
signed main() {
  int t;cin >>t;
  while(t--)
    solve();
}
4 Likes
#14

what if, pos==a.size()?

#15

https://www.codechef.com/viewsolution/35678399 I have the same issue.

#16

can anyone tell that what is the time complexity of find() function in vector? is it not O(logn)?
Because when i used the find function of vector I got TLE but when I used find function of set it got accepted.

#17

It might be helpful.
#18

So basically it is O(n). Thanks for responding.

#19

here is my solution using lower_bound instead of BS: https://www.codechef.com/viewsolution/35661570

1 Like
#20

Can you please explain what template T does and how can I get familiar with this topic ??

#21

Please share your code it might help us to find what’s the bug in code

#22

I used lower bound and did this question.
Link to my solution:
https://www.codechef.com/viewsolution/35688202

1 Like