SRM 620, python fails again

This was the last of the 10 SRMs I decided to use python exclusively on. Also definitely the one in which the poor topcoder python support did the most harm.

Div1 250, the one with gcd

Game: You start with a pair of positive integer `(x,y)`, in each move you can move to `(x,x+y)` or `(x+y,y)`. You are given two paris `(a,b)` and `(c,d)` , where each integer is up to 1000000. You want to know if there is a pair `(x,y)` such that both `(a,b)` and `(c,d)` are reachable using it as a starting position. Return the largest possible sum `x+y` in that case else -1

The idea is to go backwards. From `(a,b)`, there are two candidate backward moves: `(a-b,b)` and `(a,b-a)`, however, since the integers must be positive, only one of them is valid: If `(a>b)`, then pick `(a-b,b)` , if `(a<b)` pick `(a,b-a)` , if they are equal, this is the time to stop, because else one will go negative.

So it is easy to make the two sets of pairs `(x,y)` that can reach both `(a,b)` and `(c,d)`, we could find if the two sets have an intersection, if they do, return the maximum sum. Easy:

Notice that when one of `a` or `b` is 1, and the other is 1000000, there are 1000000 elements in one list. So there can be way tons of elements and looking for the intersection is hard unless we go clever and use sets that work in logarithmic time to find if they contain stuff or not. (Or maybe a hash table, but hash tables really blow) In c++, it means std::set or std::map, in python:

class PairGame:
 def maxSum(self, a, b, c, d):
    # find all the pairs that can be reached going backwards from (a,b):
    def backwards(a,b):
        while a > 0 and b > 0:
            yield (a,b)
            if a >= b:
                a -= b
            else:
                b -= a
    # find the intersection between the two sets:
    inter = set( backwards(c,d) ) & set( backwards(a,b) )
    return -1 if len(inter) == 0 else max( x+y for (x,y) in inter)

I submitted it and scored 225~ points. I was so proud of this code. I knew that people coding in c++ or one of the joke languages would be making totally awful things, like repeating the code used to go backwards from `(a,b)`, copy and pasting it to do it with `(c,d)` but doing the slightly different search.

Unfortunately, it times out with `(a,b) = (1000000,1)` and `(c,d) = (1000000,1)`, or similar. I could notice that it can barely run around 1 second when none of the integers is 2. So the only way to fix this is to take care of the cases when any of them is 1 individually (without making huge loops). This complicates the code a ton, and I needed tons of resubmits before getting the following code which might still be wrong:

class PairGame:
 def maxSum(self, a, b, c, d):
    # this wouldn't be necessary if python wasn't too slow for O(n) when n = 1000000
    if a == 1:
        # The path to (a,b) is (1,1), (1,2), ... (1,x), ... (1,b)
        #can we reach (1,x) going backwards from (c,d) ?
        #if so, what's maximum x that we can reach?
        while (c > 1) and (d > 0):
            if d > c:
                d = d % c
            else:
                c = c % d
                if c == 0 and d == 1:
                    c = 1
        if c == 1:
            return min(b,d) + 1
        else:
            return -1
    if b == 1:
        return self.maxSum(b,a,d,c)
    if c == 1 or d == 1:
        return self.maxSum(c,d,a,b)
        
    # Let's pretend the followign is the only real part of the code, okay?
    def backwards(a,b):
        while a > 0 and b > 0:
            yield (a,b)
            if a >= b:
                a -= b
            else:
                b -= a
    inter = set( backwards(c,d) ) & set( backwards(a,b) )
    return -1 if len(inter) == 0 else max( x+y for (x,y) in inter)

(In fact, at first it seemed like the main problem was memory, but even after fixing the memory, it is still too slow

All those using c++ or Java or perhaps even C# wouldn't have this issue. It caused me to lose plenty of points in resubmits and I might fail still. The problem is much harder when `n = 1000000` is too slow. And the worst thing is, that difficulty wouldn't have changed much for c++/Java if the constraint was 500000, but it would have saved python. Well, too bad.

Div1 500

I had little time. All I can say is that the problem is the same as if you just picked a sequence of skills and sorted by this sequence of skills lexicographically. The rest is fuzzy