Problem A statement

[string, greedy]

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8e9c

Solution

This problem constraints allow us to use greedy strategy: each time decide to take element or double element.

Complexity

It is O(n^2) for time and O(n) for space.

Code

T = int(input())
I = lambda: [int(x) for x in input().split()]

for j in range(T):
    s = input().rstrip()
    n = len(s)
    ans = []
    for i, x in enumerate(s):
        end = [s[j] for j in range(i + 1, n)]
        if end < [x] + end:
            ans += [x]
        else:
            ans += [x, x]

    print("Case #" + str(j + 1) + ": " +   "".join(x for x in ans))

Remark

There is also O(n) time complexity solution.

Problem B statement

[math, greedy]

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8fc1

Solution

The idea is to add values [1, 2, 4, 8, ..., 2^29] to our array A and the rest take as small values. Then we can make any possible values using +- of these elemens. For the B we sort it and then take sign changing sum.

Complexity

It is O(n^2) for time, because I generate A in stupid way. We can easily make it O(n log n). Space is O(n).

Code

import sys

def q():
    arr = [int(i) for i in input().split()]
    return arr

def p(v):
    print(v)
    sys.stdout.flush()

T = int(input())

for j in range(T):
    n = int(input())
    A = [1<<i for i in range(30)]
    k = 3
    while len(A) < n:
        if k not in A: A += [k]
        k += 1

    p(" ".join(str(x) for x in A))
    B = q()
    A, B = A[:30], sorted(A[30:] + B)
    part1 = B[::2]
    part2 = B[1::2]
    if sum(part1) > sum(part2):
        part1, part2 = part2, part1

    delta = sum(part2) - sum(part1)   # must be odd positive if we do all correctly
    x = (delta + (2**30) - 1)//2
    part3 = [2**i for i in range(30) if (x>>i) & 1]
    ans = part3 + part1
    p(" ".join(str(x) for x in ans))

Problem C statement

[dp, divide and conquer, stack]

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa9280

Solution

See oficial solution.

Complexity

It is O(E^3 + E^2W) for time and O(E^3) for space.

Code

I = lambda: [int(x) for x in input().split()]
from functools import lru_cache
T = int(input())

for j in range(T):
    E, W = I()
    arr = [I() for _ in range(E)]

    @lru_cache(None)
    def C(l, r):
        if l == r: return arr[l]
        ans = [min(x, y) for x, y in zip(C(l, r - 1), arr[r])]
        return ans

    @lru_cache(None)
    def D(l, r):
        return sum(C(l, r))

    @lru_cache(None)
    def M(l, r):
        if l == r: return 0
        return min(M(l, x) + M(x+1, r) + 2*D(l, x) + 2*D(x+1, r) for x in range(l, r)) - 4*D(l, r)

    ans = M(0, E - 1) + 2*D(0, E - 1)
    print("Case #" + str(j + 1) + ": " + str(ans))