CodeJam 2017 Qualification Round

coding python codejam algo

Problem A: Pancake Flips

Problem A is a pretty straightforward one. The first solution that came to mind is the greedy solution. And this is the first rendition of the solution that I came up with.

T = input()
for t in range(T):
    S, K = raw_input().split()
    S = list(S)
    K = int(K)

    turns = 0
    for i in range(len(S)-K+1):
        if S[i]=='-':
            turns += 1
            for j in range(K):
                S[i+j] = '-+'[S[i+j]=='-']

    if S.count('-'):
        turns = 'IMPOSSIBLE'
    else:
        turns = str(turns)

    print "Case #%d: %s"%(t+1, turns)

But after reading the contest analysis, it mentions an optimization which uses a counter and I got intrigued. I tried implementing the optimization, it took me a little while to wrap my mind around it, but I got it in the end.

T = input()
for t in range(T):
    S, K = raw_input().split()
    K = int(K)

    track = [0]*(len(S)+1)
    turns = curr = 0
    for i in range(len(S)):
        curr -= track[i]
        if (S[i]=='-' and not curr%2) or (S[i]=='+' and curr%2):
            if i<=len(S)-K:
                curr += 1
                turns += 1
                track[i+K] = 1
            else:
                turns = 'IMPOSSIBLE'

    print "Case #%d: %s"%(t+1, str(turns))

As it turns out the optimization was almost 6 times as fast in execution. Such a miracle how small details like these matter so much.

Problem B: Tidy Numbers

The main idea behind this would be to figure out how I would do it by hand, and the transfer it into an algorithm that works. The solution is pretty elegant. Just a single pass, make the changes based on the different numbers in the position, and the answer will be out.

T = input()
for t in range(T):
    N = raw_input()

    pos = -1
    for i in range(len(N)-1):
        if N[i]>N[i+1]:
            pos = i
            break

    if pos>-1:
        N = map(int, list(N))
        for i in range(len(N)-pos-1):
            N[pos+1+i] = 9

        for i in range(pos+1):
            pos2 = pos-i
            if pos2==0 and N[pos]==1:
                N[pos2] = 0
            else:
                N[pos2] -= 1

                if pos2!=0 and N[pos2]<N[pos2-1]:
                    N[pos2]=9
                else:
                    break

        N = ''.join(map(str, N))

    print "Case #%d: %d"%(t+1, int(N))

Problem C: Bathroom Stalls

I read the problem, and what immediately came to mind was how similar this was to a binary search. You go into a certain position, and then you find out what’s the size the of the bin left and right of you. This solution is so beautifully concise.

T = input()
for t in range(T):
    N, K = map(int, raw_input().split())

    even = False
    K = map(int, list(bin(K)[2:][::-1]))
    for k in K:
        even = not N%2
        N = (N-1)/2

        if even and not k:
            N += 1

    print "Case #%d: %d %d"%(t+1, N+int(even), N)

Problem D: Fashion Show

This is the problem that I was unable to complete within the time. I downloaded on of the solutions, and the solution looked pretty simple to understand. After reading the analysis, I had a much better idea of what the problem is about. It is a rehash of the classical chess piece problem, and this is my intepretation of the solution.

T = input()
for t in range(T):
    N, M = map(int, raw_input().split())

    diag1 = {}
    diag2 = {}
    rows = {}
    cols = {}
    for i in range(N):
        for j in range(N):
            diag1[i+j]=diag2[i-j]=rows[i]=cols[j]=1

    grida = [[0]*N for i in range(N)]
    gridb = [[0]*N for i in range(N)]
    for m in range(M):
        sign, R, C = raw_input().split()

        R, C = map(lambda x: int(x)-1, [R, C])
        if sign=='+':
            diag1[R+C] = diag2[R-C] = 0
            grida[R][C] = 1
        else:
            rows[R] = cols[C] = 0
            gridb[R][C] = 1

    ### solve for rooks
    changed = [[0]*N for i in range(N)]
    for i in [i for i in range(N) if rows[i]]:
        for j in [j for j in range(N) if cols[j]]:
            rows[i] = cols[j] = 0
            gridb[i][j] = 1
            changed[i][j] = 1
            break

    ### solve for bishops
    diags = {}
    for i in range(N):
        for j in range(N):
            if not diags.get(i+j): diags[i+j]=0
            diags[i+j] += 1
    diags = sorted([(diags[k], k) for k in diags if diag1[k]])
    for b in diags:
        for r in range(N):
            c = b[1]-r
            if c<0 or c>=N:
                continue
            if diag2[r-c]:
                diag1[r+c] = diag2[r-c] = 0
                grida[r][c] = 1
                changed[r][c] = 1
                break

    summ = lambda x: sum([sum(i)for i in x])
    print "Case #%d: %d %d"%(t+1, summ(grida)+summ(gridb), summ(changed))

    for i in range(N):
        for j in range(N):
            if changed[i][j]:
                if grida[i][j] and gridb[i][j]: print 'o',
                elif grida[i][j]: print 'x',
                else: print '+',

                print i, j

Overall

Considering how long I have not touched algorithm writing, I am just grateful that I am still able to at least complete some of the questions for this qualification round. These solutions may not be the fastest, nor the most elegant, but I feel they very well depict my thought processes towards these questions.