SRM 618: When python failed

This is the eighth of ten matches in which I promised to use python exclusively. This is also the first match in which I feel like I can claim I lost plenty of points because of this restriction.

Div1 250: The one with heteronormativity

So I am supposed to be solving this problem, and all I can think of after reading for the first time is that the problem's definition of family allows incest but is all about not allowing same-gender pairings :/ okay. ..

So a "family" is defined as a graph, in which each edge either has zero incident edges or exactly two incident edges. The two incident edges MUST be from two nodes with different genders. Also the graph must be topsorted. Given a graph of up of 100 nodes return if it could be a family or not. Basically, you have to assign genders to each node. It turns out that the input format guarantees that the graph is topsorted and that each node has 0 or 2 incident nodes. So all that we need to do is ask if we can assign the genders correctly.

If two nodes appear as the parents of a node, then their genders must be different. If we imagine a different graph, in which each of these pairs of nodes that must have a different gender are connected by a single edge. Then the graph must be bipartite. If the graph is bipartite, then the answer is that Yep, the graph could be a "family". Else not. Checking if a graph is bipartite is an easy application of the Depth-first search.

class Family:
 def isFamily(self, parent1, parent2):
    n = max(max(parent1),max(parent2)) + 1
    # Make a set of edges in the hopefully bipartite graph, they are undirected 
    E = set(zip(parent1, parent2)) | set( zip(parent2, parent1) )
    E.remove( (-1,-1) )
    
    # is the graph bipartite?
    color = [-1] * n
    result = [ "Possible" ]
    def dfs(x, c):
        if color[x] == -1:
            color[x] = c
            for (u,v) in E:
                if u == x:
                    dfs(v, 0 if c == 1 else 1)
        elif color[x] != c:
            result[0]  = "Impossible"
        
    for i in range(n):
        if color[i] == -1:
            dfs(i, 0)
        
    return result[0]

I took a bit of time mostly because of the above-mentioned distraction :P, but python helped me keep the code clean. I think it should pass unless 100x100 is suddenly too slow (I doubt it).

Div1 500: The one with strings.

You should count the number of maximal-length strings that use an alphabet of `n` letters and follow these properties:

• No consecutive equal letters.
• For each pair of (possibly equal) characters X and Y, string "XYXY" is NOT a subsequence of the string.

The first issue is how to know what is the maximum length possible. After plenty of analysis, I found that the maximum length possible is 2n-1. However, there are two methods to achieve it:

• One way, is to surround a string of 2(n-1)-1 length using (n-1) alphabet characters, using two instances of one character different to those (n-1) ones. For example: A????????????A, where ????? contains no A.
• The other way has 3 instances of the extreme character. A??????A!!!!!!!A, but also ?????? and !!!!!! cannot share characters.

So the rest is to count the number of valid patterns. It is not necessary to worry about which character goes to which position of the pattern, because we can just multiply the result by `n!`.

The rest is an `O(n^2)` dynamic programming, unfortunately, `n` is up to 5000 (I wish it was 1000), so no matter what I do, the thing will take at least 6 seconds. That's too much.

More info about the recurrence in the comments of the code:

MOD = 1000000007

def modFactorial(x):
    r = 1
    for i in xrange(1, x + 1):
        r = (r * i) % MOD
    return r
        

class LongWordsDiv1:
 def count(self, n):
    # The maximum number of letters is 2*n-1, although there are multiple ways 
    # to reach that maximum
    # Example, for n = 5
    # 012343210
    # 010234320
    # 010232420
    # 012103430
    # 012321040
    # 012131040
    # there should be 9, but can't think of the other 3
    
    dp = [0] * 5001
    dp[0] = 1
    dp[1] = 1
    for i in xrange(2,n+1):
        #1) 2n - 1 = 2 + (2(n-1) - 1)
        res = dp[i-1]
        #2) find a,b: 2n - 1 = 3 + 2a + 2b - 2
        #                 b  = (2n - 1 - 3 - 2a + 2) / 2
        #                 b  = (2n - 2a - 2) / 2
        #                 b  = n - a - 1
        a = 1
        while a < i:
            b = i - a - 1
            if b > 0:
                res += (dp[b] * dp[a]) % MOD
            else:
                break
            a += 1
        dp[i] = res

    return ( dp[n] * modFactorial(n) ) % MOD

It is possible I missed something in this analysis, though.