string
greedy
math
dp
divide and conquer
stack
]
Google Code Jam, round 1A
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))