Skip to content

kamyu104/GoogleCodeJam-2017

Repository files navigation

Python solutions of Google Code Jam 2017. Solution begins with * means it will get TLE in the largest data set (total computation amount > 10^8, which is not friendly for Python to solve in 5 ~ 15 seconds). A 4-minute timer is set for the small dataset and a 8-minute timer is set for the large dataset this year.

Qualification Round

# Title Solution Time Space Difficulty Tag Note
A Oversized Pancake Flipper Python O(K * S) O(S) Easy Greedy
B Tidy Numbers Python O((logN)^2) O(logN) Easy Math Analysis
C Bathroom Stalls Python O(logK) O(1) Easy BST
D Fashion Show Python O(N^2) O(N) Hard Greedy

Round 1A

# Title Solution Time Space Difficulty Tag Note
A Alphabet Cake Python O(R * C) O(1) Easy Greedy
B Ratatouille Python O(N^2 * P^2) O(N * P) Medium Greedy
C Play The Dragon Python O(sqrt(N)) O(1) Hard ❤️ Math Analysis

Round 1B

# Title Solution Time Space Difficulty Tag Note
A Steed 2: Cruise Control Python O(N) O(1) Easy Math Analysis
B Stable Neigh-bors Python O(N) O(1) Hard Math Analysis
C Pony Express Python O(N^3) O(1) Medium Floyd-Warshall

Round 1C

# Title Solution Time Space Difficulty Tag Note
A Ample Syrup Python O(NlogK) O(K) Easy Sort, Heap
B Parenting Partnering Python O(NlogN) O(N) Medium Sort, Greedy
C Core Training Python O(N^2 * K) O(N) Hard DP, Probability

Round 2

# Title Solution Time Space Difficulty Tag Note
A Fresh Chocolate Python O(1) O(1) Easy Math, Greedy
B Roller Coaster Scheduling Python O(M + N) O(M) Easy Math, Greedy
C Beaming With Joy Python O(R * C) O(R * C) Medium CNF, 2-SAT, SCC, Tarjan's Algorithm
D Shoot the Turrets Python O(S * R * C + S * T^2 + T * S * (R + C)) O(S * R * C) Hard BFS, Bipartite Matching

Round 3

# Title Solution Time Space Difficulty Tag Note
A Googlements Python O(L * (H(L + 1, L) - 1)) O(L) Easy Math, Backtracking, Pruning
B Good News and Bad News Python O(P^2) O(P) Medium Graph, DFS, Spanning Tree
C Mountain Tour Python O(C * log*(C)) O(C) Medium Union Find, Greedy
D Slate Modern Python O(N^2) O(N^2) Hard ❤️ Manhattan Distance, Coordinate Compression, DP, Arithmetic Progression

World Finals

You can relive the magic of the 2017 Code Jam World Finals by watching the Live Stream Recording of the competition, problem explanations, interviews with Google and Code Jam engineers, and announcement of winners.

# Title Solution Time Space Difficulty Tag Note
A Dice Straight PyPy PyPy O(N^2) O(N) Medium Sliding Window, Bipartite Matching, Ford-Fulkerson Algorithm
B Operation Python O(11*2^11 * (N * D^2)) O(2^11 * (N * D)) Medium Grouping, Greedy, DP
C Spanning Planning PyPy O(R * N^3) O(N^2) Hard Cycle, Spanning Tree, Kirchhoff Matrix Tree Theorem, Determinant, Gaussian Elimination
D Omnicircumnavigation PyPy O(N^2) O(N) Easy ❤️ Geometry, Plane, Vector, Inner Product, Outer Product
E Stack Management Python O((N * C) * logN) O(N * C) Very Hard ❤️ Preprocess, Stack, DFS
F Teleporters PyPy O(N^3 * logM) O(N^2 * logM) Very Hard ❤️ Geometry, Binary Search, Distance Matrix, Power of 2, Precompute, Iterated Squaring