CodeJam 2017 Qualification Round
coding python codejam algoProblem 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.