Need help optimizing code

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.

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.

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.

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?)

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).

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.

this is my solution in java , i passed 8/11 on tests.

https://gist.github.com/3970382

i couldnt reduce better than o(n) but still thinking

This calls a DP-ish question. Sort all points by x, then by Y. Assuming that all points are always "approximated" to a known granularity (say, 0.05), it should be easy to fit 20x20 = 400 points for 1 square unit.

Now, for a rectangle A,B,C,D points, number of points it contains =

A_B | | C_D Area(D) - Area(C) - Area(B) + Area(A)

Where Area(point) represents the total number of points contained between Point(minx,miny) to the Point itself.