Python solutions of Google Code Jam 2016. 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 |
Counting Sheep |
Python |
O(NlogN) |
O(logN) |
Easy |
|
Simulate |
| B |
Revenge of the Pancakes |
Python |
O(N) |
O(1) |
Easy |
|
Math Analysis |
| C |
Coin Jam |
Python |
O(N * J) |
O(N) |
Medium |
|
Tricky Math |
| D |
Fractiles |
Python |
O(K) |
O(1) |
Hard |
|
Logic, Math Induction |
Round 1A
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
The Last Word |
Python |
O(L) |
O(L) |
Easy |
|
Greedy |
| B |
Rank and File |
Python |
O(N^2) |
O(N^2) |
Easy |
|
Math Analysis |
| C |
BFFs |
Python |
O(N) |
O(N) |
Hard |
|
Hash, Graph |
Round 1B
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Getting the Digits |
Python |
O(N) |
O(1) |
Easy |
|
Greedy |
| B |
Close Match |
Python |
O(N^2) |
O(N) |
Medium |
|
Greedy |
| C |
Technobabble |
Python |
O(N * sqrt(W)) |
O(W) |
Hard |
|
Graph, Bipartite Matching |
Round 1C
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Senate Evacuation |
Python |
O(PlogP) |
O(P) |
Easy |
|
Heap, Math Analysis |
| B |
Slides! |
Python |
O(B^2) |
O(1) |
Easy |
|
Math Analysis |
| C |
Fashion Police |
Python |
O(J * P * min(S, K)) |
O(1) |
Hard |
|
Math Analysis |
Round 2
Round 3
World Finals
You can relive the magic of the 2016 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 |
Integeregex |
Python Python |
O(R^2 + RlogB) on average |
O(R) on average |
Medium |
❤️ |
Automata, NFA, Thompson's Construction, DP |
| B |
Family Hotel |
Python |
O(N) |
O(N) |
Medium |
|
DP, Probability, Euler's Theorem |
| C |
Gallery of Pillars |
Python |
O(NlogN) |
O(M) |
Medium |
|
Inclusion-Exclusion Principle, Möbius Function, Sieve Of Eratosthenes, Math Analysis |
| D |
Map Reduce |
Python PyPy |
O((R * C) * log(R * C)) |
O(R * C) |
Hard |
|
BFS, Binary Search |
| E |
Radioactive Islands |
PyPy Python PyPy |
O(X/H) |
O(1) |
Hard |
❤️ |
DP, Integral, Calculus of Variations, Euler-Lagrange Equation, Runge-Kutta Method, Binary Search, Hill-Climbing |
GoogleCodeJam-2016 copied to clipboard
kamyu104
kamyu104