# Quadrant Queries challenge

Running the same test 10,000 times with cProfile tells me that most of the damage happens in the count() function. This is my attempt at a solution to the Quadrant Queries challenge from InterviewStreet (the problem statement can be found here).

According to InterviewStreet, I passed 3/11 testcases and I ran out of CPU time. I have no way of knowing whether I was 3 for 3 and ran out of time or say, 3 for 6 and ran out of time. I don't know if my code works on all input.

Please help me optimize this code:

def reflect_x(i, j, coordinates):
for pair in xrange(i-1, j):
coordinates[pair][1] = -coordinates[pair][1]
return coordinates

def reflect_y(i, j, coordinates):
for pair in xrange(i-1, j):
coordinates[pair][0] = -coordinates[pair][0]
return coordinates

def count(i, j, coordinates):
quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0
for pair in xrange(i-1, j):
x, y = coordinates[pair][0], coordinates[pair][1]

if x >= 0 and y >= 0:
quad_one += 1
elif x < 0 and y >= 0:
quad_two += 1
elif x < 0 and y < 0:
quad_three += 1
elif x >= 0 and y < 0:
quad_four += 1

print "%d %d %d %d" % (quad_one, quad_two, quad_three, quad_four)

def reflect(coordinates, queries):

for query in queries:
if query[0] == "X":
reflect_x(query[1], query[2], coordinates)
elif query[0] == "Y":
reflect_y(query[1], query[2], coordinates)
elif query[0] == "C":
count(query[1], query[2], coordinates)
else:
print query

if __name__ == "__main__":
N = int(raw_input())
coordinates = [[int(pair[0]), int(pair[1])] for pair in (pair.split() for pair in (raw_input() for i in xrange(N)))]

Q = int(raw_input())
queries = [[query[0], int(query[1]), int(query[2])] for query in (query.split() for query in (raw_input() for i in xrange(Q)))]

reflect(coordinates, queries)

-
Add the code from pastie here that is relevant and also be specific about what you need help with. codereview.stackexchange.com/questions/how-to-ask – James Khoury Aug 24 '11 at 5:09
It's all relevant .. – James Brewer Aug 24 '11 at 6:19
These sites are full of questions like this. In the first place, you need to know about costly lines of code, not just functions. Try this method. – Mike Dunlavey Aug 29 '11 at 14:24

## 6 Answers

def reflect_x(i, j, coordinates):
for pair in xrange(i-1, j):
coordinates[pair][1] = -coordinates[pair][1]
return coordinates


Something like:

def reflect_x(i, j, coordinates):
coordinates[i-1:j] = ((x,-y) for x,y  in coordinates[i-1,j])


Is clearer and possibly slightly faster. Also, modify or return, don't do both.

def count(i, j, coordinates):
quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0


If you have a count attached to your variable, the probably means it should be a list

    quad = [0] * 4

for pair in xrange(i-1, j):


You may be better off slicing the list. That will be happen entirely in C, but looking up the value each time happens in python.

        x, y = coordinates[pair][0], coordinates[pair][1]


Same as:

        x, y = coordinates[pair]


...

        if x >= 0 and y >= 0:
quad_one += 1
elif x < 0 and y >= 0:
quad_two += 1
elif x < 0 and y < 0:
quad_three += 1
elif x >= 0 and y < 0:
quad_four += 1

print "%d %d %d %d" % (quad_one, quad_two, quad_three, quad_four)

def reflect(coordinates, queries):


bad name, this function doesn't only reflect

    for query in queries:
if query[0] == "X":
reflect_x(query[1], query[2], coordinates)
elif query[0] == "Y":
reflect_y(query[1], query[2], coordinates)
elif query[0] == "C":
count(query[1], query[2], coordinates)
else:
print query

if __name__ == "__main__":
N = int(raw_input())
coordinates = [[int(pair[0]), int(pair[1])] for pair in (pair.split() for pair in (raw_input() for i in xrange(N)))]


You don't need to do everything on one line. You can also unpack the tuple in the for clause.

    coordinate_lines = (raw_input() for i in xrange(N))
coordinates = [(int(x),int(y)) for x,y in line.split for line in coordinate_lines]


As for optimisation: Firstly, you need to realise that you don't actually care what the coordinates are. All you care about is the quadrants. The reflection operations merely move you from one quadrant to the other.

I have to disagree with Jeff Mercado, as I don't think his approach will work. (maybe I've missed what he's hinting at.) Basically what you have is a worst case O(N*Q) running time. Since both N and Q are large numbers you cannot get away with doing that. His approach reduces the complexity to O(1) for the count operation, but leaves O(N) for the reflect operations. That's still going to give you O(N*Q).

We need to reduce the cost of the reflect operations as well.

Basically, for each quadrant we need to keep track of the points in that quadrant. We'll put them in some sort of data structure. We need a data structure that will allow the efficient implementation of:

1. Finding all points with indexes between a start/stop index
2. Swapping those points between two different versions of the data structure
3. Finding the count of all points currently in the data structure

Basically, we need all of these operations in logarithmic time or better. Figuring out what kind of data structure gives you that is left as an exercise for the reader.

-
The time complexities I was mentioning were with respect to each operation individually, not when you factor in the different queries that's being done. – Jeff Mercado Aug 24 '11 at 21:53
@Jeff Mercado, I know. But its the entire program that is running out of time. We can optimize count, but that still leaves reflect as fairly ineffiecient. – Winston Ewert Aug 24 '11 at 22:57
I'd say, take this one step at a time. Solutions for problem sets like this could be submitted as many times as necessary AFAIK. He has determined that count is the killer here so I'd first start at optimizing that. If the optimizations yield an acceptable solution, then make efforts to optimize other parts of the program. Personally, I don't think it would be possible to optimize both counting and reflecting, both types of operations are dependent on each other so one would have to choose which. I could be wrong though as nothing comes to mind at the moment. – Jeff Mercado Aug 24 '11 at 23:20
@Jeff, that is a perfectly valid approach. But I don't think it'll work. As it is, my curiosity was piqued so I wrote my own solution which has O(log n) for all operations but I'm still not fast enough to satisfy the online judge. – Winston Ewert Aug 24 '11 at 23:48
@Winston Ewert, why does the data structure need to be able to swap between only two different versions? Since there are 4 quadrants, shouldn't we be able to switch between four different versions of the data structure? Or am I misunderstanding something? – James Brewer Aug 25 '11 at 3:24

Consider changing your algorithm to perform the task. Every operation that you need to do takes some calculation to perform the operation. Not necessarily cheap as far as the test cases thrown at you are concerned.

• Reflect X: for every point in the range, negate the x coordinate
• Reflect Y: for every point in the range, negate the y coordinate
• Count: for every point in the range, count how many lie on each quadrant

Your code appears to be a simple naive implementation to perform these operations and that alone isn't necessarily bad. However if you're taking too much time for their test cases, you need to reconsider your algorithm, how you represent the data and how you perform the calculations if the naive implementation is too slow.

Every operation is an O(n) one. Count will suffer the most since you're trying to figure out which quadrant each point belongs to as you come up with the counts. Profiling your code against your test cases will not be very effective as you can bet they will have a lot more to throw at you. You need to find out how you can reduce these O(n) algorithms somehow to pass their tests. In fact, you can reduce Count to be O(1) with the algorithms I have in mind (the other two will have the same complexity however).

Rather than just giving you the answer, I'll provide some pointers.

1. Is there another way you could effectively count something within a range?
I'm not sure how I can really explain this but consider this example:

Suppose you kept track of your balance at the bank for every day in the month. You'd have data such as this:

1 $5000 2$5020
3 $4980 4$4780
5 $5280 6$5280
7 \$5580
etc...

How would you determine how much money you earned/lost between day 1 and day 2? How about day 2 and day 4? Is there a way to represent this problem in a similar fashion?

2. Think about what representation of your information is really important here.
Your code stores a collection of points. Whenever you need to perform the count, you would have to determine what quadrant the point belongs and increment to the appropriate counter. But do you really need to keep track of the coordinates for each point? If you represented the data in another way, would you still be able to perform the three operations that are required while still maintaining the information you need? What would that representation be?

If you can answer these, I'll expand more on my answer and we'll probably work out a nice solution together. I'll probably share my answer too (though I haven't actually run it against their tests).

-
Hopefully you'll have a revelation seeing this and it will all click. – Jeff Mercado Aug 24 '11 at 7:26
I'll face these challenges after I wake up. Hopefully I will be able to think more clearly tomorrow. – James Brewer Aug 24 '11 at 9:39
The first point here is the main focus, the second will save you a few more cycles but it's not as important to the first. – Jeff Mercado Aug 24 '11 at 15:58
1. My first thought is to subtract the balance of day 2 from that of day 1, but I don't see how this can be applied to the challenge I'm working on. – James Brewer Aug 25 '11 at 2:56
That's pretty much the idea. As long as you have cumulative totals between two distinct times, you can determine how much the total has changed between the two. In your case here, you want to find how many points in the range of point i (the first "time") and point j (the second "time") lie in each of the four quadrants. So the algorithm I had in mind is to keep a running total for each of the quadrants for each of the points. When the time comes to count how many of each lie in a range, you'd use the same technique here to determine those counts. You can calculate that immediately. – Jeff Mercado Aug 25 '11 at 3:10

I've managed to get a submission past the CPU limit, using an approach similar to what Winston Ewert describes above. First I tried it in Ruby, and hit a wall at 5/11 test cases. Switching to Java immediately brought it to 9/11, and a little more optimization got it through.

The CPU limits to this problem are extremely tight. I have doubts whether any interpreted language will be able to meet them, unless there is a better data structure than the one I used. Using a compiled language, the time limits are supposed to be 1/4 of that of an interpreted language, but it is way more than 4 times as fast. My recommendation would be to validate your approach using Python or whatever, then reimplement in Java or C.

If you are using Java, one general hint is to buffer both standard input and output. In my last few attempts, the most time was spent just reading the input and outputting the result. Avoid the use of java.util.Scanner, as it appears to be a real dog.

-
+1. I am also quite convinced this is impossible to solve with Python. I wrote a python implementation using the "correct" algo/data structure, and got 5/11. I recoded it using string hackery, and got 9/11 with python even though the implementation was O(N*Q). I then ported the "correct" python code to java, and got 10/11, made a few modifications, and solved it. – John C Aug 31 '11 at 20:49

I've tried this problem a number of different ways and I'm still not getting past the speed checks. I've tried using lists and sets as my data structure, and both don't have the required asymptotic performance. @Winston Ewert is right: you need at least O(log N) time for all three operations, and the best way to do this is with a binary search tree.

The way I'm trying to do this is have four BSTs, one for each quadrant. Here's my sketch of the tree so far:

class Node:
left, right, index, count = None, None, 0, 0

def __init__(self, data):
self.left = None
self.right = None
self.data = data
self.count = 1

class Tree:
root = None

def __init__(self):
self.root = None

def add_node(self, data):
return Node(data)

def insert(self, root, data):
if root == None:
return self.add_node(data)
else:
root.count += 1
if data < root.data:
root.left = self.insert(root.left, data)
else:
root.right = self.insert(root.right, data)
return root

def find(self, root, target):
if root == None:
print "Error in find (", target, "): root is None"
return 0
else:
if target == root.data:
return root
elif target < root.data:
return self.find(root.left, target)
else:
return self.find(root.right, target)


The data variable will be the index of the node in the list representation of the coordinates we are handed. The whole point of using a BST here, as I see it, is that we can potentially move a whole segment of points from one quadrant to another by grabbing a node that the segment as a whole is descended from and inserting that node into the new tree, updating the count parameter of the tree as we go. To do that we need a method for inserting nodes into trees:

    def insert_node(self, root, node):
if root == None:
return node
else:
root.count += node.count
if node.data < root.data:
root.left = self.insert_node(root, node)
else:
root.right = self.insert_node(root, node)
return root


The tricky method, which I'm not sure how to do yet, is the part that grabs the interval in question but no more than that. Obviously, we do not get a specific [i, j] to look for in the tree, since we don't know which tree i and j are in. We only get a range. This method will grab the first node that falls in the range of [i, j] in the tree:

    def find_in_range(self, root, i, j):
if root == None:
print "Error in find_in_range (", i, j, "): root is None"
return 0
else:
if i <= root.data and root.data <= j:
return root
elif root.data > i and root.data > j:
return self.find_in_range(root.left, i, j)
elif root.data < i and root.data < j:
return self.find_in_range(root.right, i, j)
else:
print "Error in find_in_range(", i, j, "): no criteria matched"


In the case where we recurse left and then find a node in the range, everything descended from the right of that node onwards is in the interval [i, inf), so we can just call find_in_range again with new parameters and fight the right end node. A little snipping here and there and we'll have selected exactly the nodes in [i, j] in our quadrant. The same argument works if we recurse right.

The problem I'm having is that if we start the first find_in_range and we're already in the range, I don't know where the end-points are. Does anyone have a suggestion for me? If I can solve this problem, the rest is just details.

-
If you want comments on your code, I recommend opening your own question not posting an answer in somebody else's question. Also, questions about algorithms like that should be stackoverflow. – Winston Ewert Aug 31 '11 at 4:06
@Winston My mistake, I haven't been on this site very long and there wasn't any way to reply the discussion you and James were having. – lionel b Aug 31 '11 at 4:36

to optimise your count try:

def count(i, j, coordinates):
quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0
current_coordinates = coordsinates[i-1:j]

for pair in current_coordinates:
x, y = pair[0], pair[1]
...


And see if that reduces it. I'm not sure what is quicker a slice or an xrange()

just as a note: your N= and Q= is (IMHO) an almost unreadable mess. (can you not read everything in and then proccess it?)

-

I wrote a solution which takes all the reflections and combines them into a single set of reflection instructions. For example, X i j followed by Y i j is equivalent to a single "diagonal" reflection, i.e. all points from first quadrant to to 3 rd quadrant. This was no easy task as you can imagine, but it is correct. The result is that the complexity is still O(N) but it is done efficiently, i.e. instead of first doing an X reflection followed by a Y reflection, we do a single reflection. Unfortunately, this did not pass the online judge either.

The perplexing thing here is that this is the cheapest/easiest problem of the lot, and I don't think it is easy. I already solved Meeting Point, and this seems to be harder than that.

The only thing I can think of is that there is a conservation of points, i.e. reflections do not destroy create points, so the four running totals are not independent. We only need to keep track of two for example and the total. However, this isn't really a big realization which to my mind.

Bottom line. This is a tough problem.

-
If it helps, a support member told me the solution must be at least O(lg n * Q) – James Brewer Aug 30 '11 at 7:46

## protected by Jamal♦May 9 '14 at 2:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?