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
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
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
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 |
GoogleCodeJam-2017 copied to clipboard
kamyu104
kamyu104