# Determining position of point W.R.T to given line equation

Problem from HackerRank::

Problem Statement:

There are $N$ lines. Each line has an index between $1$ and $N$. The slope of each line is negative, i.e. it goes from upper-left to lower-right.

There are $Q$ queries. Each of them is in the format $L$ $R$ $x$ $y$, and you should output whether there is any line with index between $L$ and $R$ and the point $(x,y)$ is under it. If there is, then the answer isYES, otherwiseNO`.

As you know, any line splits an infinite plane into two regions. The point $(x,y)$ is under the line if that point is at the same region with point $(-\infty , -\infty)$ . If the point lies on the line it does not count.

Input Format:

The first line contains $N$, the number of lines. The following $N$ lines each contains two integers $m$ and $n$ that describes the line $mx + n = y$.

Output Format:

For each query, output one line containing either YES or NO.

Sample Input:

2
-1 3
-2 -4
3
1 2 0 0
1 1 0 0
2 2 0 0

Sample Output:

YES YES NO

Explanation:

For this, I've submitted this code in Python, but in half of the test case, the time limit was exceeded.

n = int(input())
x = []
y = []
for i in range(n):
l = list(map(int, input().split()))
x.append(l[0])
y.append(l[1])
q = int(input())

for i in range(q):
p = list(map(int, input().split()))
L = p[0]-1
R = p[1]-1
X = p[2]
Y = p[3]
flag = 0
for i in range(L,R+1,1):
if(Y - x[i]*X - y[i] < 0):
print("YES")
flag = 1
break;
if(flag == 0):
print("NO")

I can't understand how can I improve my code further. Because for loop to check from L to R is necessary. also the loop to execute every query is necessary. So in total 2 loops are needed. How can I reduce time here?

• hackerrank.com/contests/placements-practice/challenges/… Jul 16, 2016 at 19:02
• It might be that you need to preprocess the input lines so that you can answer each query in time sublinear to $\mathcal{O}(R - L)$. Jul 22, 2016 at 16:39
• but how? I can't understand. Jul 22, 2016 at 19:15
• I'd love to write you an answer, but I'm having trouble getting your code to work. Assuming you wrote this in Python 3, how do you provide your code with the input? On my PC it starts answering before I'm done inserting the input. Is that as intended?
– Mast
Dec 28, 2016 at 19:21

Note to potential future reviewers: This code appears to be suitable for Python 3 only.

Let's structure your code a little and see if we can fix the timing problem.

I propose the following order:

1. Global variables
2. Helper functions
3. Main function
1. Input
2. Actual calculations
4. if __name__ == '__main__':

The latter may not look familiar to you, but it's an include guard. It's a good practice to start using those, especially if you ever want to re-use parts of your code. Now your main only gets executed if the script is called directly, not when it's called by import.

Which leaves us after the first couple of edits with the following:

x = []
y = []

return int(input())

for i in range(amount):
l = list(map(int, input().split()))
x.append(l[0])
y.append(l[1])

return list(map(int, input().split()))

def main():
for i in range(q):
L = p[0]-1
R = p[1]-1
X = p[2]
Y = p[3]
flag = 0
for i in range(L, R+1, 1):
if(Y - x[i]*X - y[i] < 0):
print("YES")
flag = 1
break
if(flag == 0):
print("NO")

if __name__ == '__main__':
main()

Which still isn't much, but the structure is getting better. Note that I made your comma's breath ((L,R+1,1) is more readable when written as (L, R+1, 1) and there's no longer a ; behind your break. It's Python, we don't need semi-colons after break/continue etc.

One of the major things fixed now is your code was executing before you finished reading your input. That's usually a bad idea unless you're in some kind of do until told otherwise loop, which this wasn't. Now it waits for all input before it executes the rest.

I/O used to be:

2
-1 3
-2 -4
3
1 2 0 0
YES
1 1 0 0
YES
2 2 0 0
NO

Now it is:

2
-1 3
-2 -4
3
1 2 0 0
1 1 0 0
2 2 0 0
YES
YES
NO

There's still a couple of problems with it. We're now iterating an extra time, which can't be helpful for the time it takes to execute. But at least it looks better now, so we can see what we're doing. It still fails just as many test cases as your original code did, so at least we didn't do noticeably worse.

What else can we do better?

L = query[0]-1
R = query[1]-1
X = query[2]
Y = query[3]
flag = 0
for i in range(L, R+1, 1):

R = some value minus one. The actual value we need is R plus one. Since the description of the challenge says L and R are given (not L+1 and R+1), it doesn't make sense to modify them.

Let's go from L-1 to R instead.

L = query[0]
R = query[1]
X = query[2]
Y = query[3]
flag = 0
for i in range(L-1, R, 1):

Another thing we don't need is this entire flag business. Let's use return values instead:

x = []
y = []

return int(input())

for i in range(amount):
l = list(map(int, input().split()))
x.append(l[0])
y.append(l[1])

return list(map(int, input().split()))

def does_line_exist(query):
L = query[0]
R = query[1]
X = query[2]
Y = query[3]
for i in range(L-1, R, 1):
if(Y - x[i]*X - y[i] < 0):
return True
return False

def main():
queries = []
for i in range(q):
for query in queries:
if does_line_exist(query):
print("YES")
else:
print("NO")

if __name__ == '__main__':
main()

Poof! No more flag.

But wait, this still doesn't solve your TLE problem! No, I'm afraid not and I'm going to tell you why. The author of the problem has made the constraints so narrow that the only acceptable solutions are those which use the Convex hull trick. It basically boils down to checking whether a value is < -y instead of < 0.

I'll leave the actual implementation of said trick to you. Feel free to post a follow-up question once you've implemented it.