SRM 611: My first python SRM

The other day, I made the foolish decision to use Python exclusive in SRMs 611 to 620. I suspected it will be bad for my rating at least initially. I am not as experienced with python as I am with c++ and there is always a good chance the admins will include a problem in the set that is unsolvable in python. On the other hand, maybe the 250 has a quick to think solution and then python's conciseness would help me score some points.

Div1 250: The one with LCM

You are given two sets `A`, `B`, the LCM set of a set `S` is the set of all numbers `L` such that `L` is equal to the LCM of the numbers in a subset of `S`. Given `A` and `B` find if their LCM sets are equal. Numbers in each set are between `2` and `10^9`, inclusive.

Tough luck, it didn't appear this was going to be a quick problem to code, and at first I had no idea what to do.

Eventually, I thought of something that appears to be a solution. Given a set `X`, we can get rid of any number that can be created by taking the LCM of other numbers in the set. After doing this, set `X` becomes the minimal set such that its LCM set will be equal to `X`. If we find the minimal sets of `A` and `B`, they will be equal if and only if the LCM sets are equal.

Implementing was another issue. How can you tell if a number can be made from the other numbers in the set? Well, you would need to process the numbers in decreasing order. I focused on the prime decomposition of each number, if the exponent of at least one prime number is larger than the maximum ever exponent in the numbers smaller than it, then this number shouldn't be removed. I needed to code Eratosthenes sieve in python for the first time, it probably isn't so well coded.

I made a mistake, the first implementation would ignore the smallest number in each of the sets, so it thought `{7}` had the same LCM set as `{8}`. The slow submission plus the resubmit made me score incredibly low. I am not 100% sure about this approach, but if I fail system tests it will not make a difference, my ranking in the match will be very low either way.

import math

class LCMSet:
 def equal(self, A, B):

    # greatest common divisor
    def gcd(x,y):
        while y != 0:
            (x,y) = (y, x%y)
        return x
    
    # least common multiple:
    def lcm(x,y):
        return x * y / gcd(x,y)
    
    # Eratosthenes siege returns an iterator of prime numbers, we don't need
    # primes larger than sqrt(max( max(A), max(B) ))
    def sieve():
        t = int( math.sqrt(max(max(A), max(B))) + 1 ) 
        compos = [ False ] * (t + 1)
        for i in xrange(2, t + 1):
            if not compos[i]:
                yield i
                j = i + i
                while j <= t:
                    compos[j] = True
                    j += i
    
    # make a list of prime numbers
    primes = list( sieve() )
    
    # prime decomposition:
    def primeDecomp(x):
        d = dict()
        for p in primes:
            c = 0
            while x % p == 0:
                x /= p
                c += 1
            if c > 0:
                d[p] = c
        if x > 1:
            d[x] = 1
        return d

    # "compress" a set, find the minimal set that has a LCM set equal to X
    def compress(X):
        decomp = [ primeDecomp(x) for x in reversed(X) ]
        n = len(X)
        c = []
        for i in xrange(n - 1):
            good = False
            # for each p^r in the prime decomposition:
            for (p , r) in decomp[i].items():
                if r > max( 0 if p not in decomp[j] else decomp[j][p] for j in xrange(i+1,n) ):
                    good = True
            if good:
                c.append( decomp[i] )
        #smallest number is always there. Missing this line caused the resubmit
        c.append( decomp[n-1] )
        return c
        
    return ['Equal','Not equal'][compress(A) != compress(B)]

Div1 500: The one with spanning tree

You are given a complete graph of up to 20 vertices with weighted edges (It is given in the form of points in a map that you have to connect using a tree topology). Return the minimum standard deviation of the edges of a spanning tree.

Easy, right? Well, the `20` constraint hints me that some heavy dp or brute force is needed. I remembered a match in which we had some sort of brute force/dp through all spanning trees, but I didn't remember enough. Also, the constraint wasn't a good sign for whether the problem is solvable in python or not :/

The end

Plenty of very different solutions for 250. I have no idea if I will pass, I expect many system test fails.

What about python? Well, this wasn't a great match for comparisons. I think I would have taken very long to code a solution in c++ too. I am currently sleep deprived, I stayed up till very late last night trying to finish something that barely passes as an editorial for SRM 610. I guess there is a good reason I am doing this for 10 SRMs and not just a couple.

Update: Failed system tests

What a bad day. Div1 250 approach fails the following test case: [{168, 7476, 84, 890, 10, 4, 40, 3560, 37380, 8, 89, 20}, {84, 4, 20, 7476, 3560, 89, 712, 420, 74760, 1780, 14952, 8, 356, 10}], it is a wrong answer so this is likely a mistake with the algorithm and not python's fault.