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.
- Code Jam 2015
- Qualification Round
- Round 1A
- Round 1B
- Round 1C
- Round 2
- Round 3
- World Finals
- Code Jam 2017
| # | 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 |
| # | 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 |
| # | 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 |
| # | 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 |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Rather Perplexing Showdown | Python | O(2^N) | O(2^N) | Easy | Math Analysis | |
| B | Red Tape Committee | Python | O(NlogN + K^3) | O(N) | Easy | DP, Probability | |
| C | The Gardener of Seville | Python | O((R + C)log(R + C) + R * C) | O(R * C) | Hard | Simulate | |
| D | Freeform Factory | Python | O(N + C * C!) | O(N + C * C!) | Hard | Memoization, DFS |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Teaching Assistant | Python | O(S) | O(S) | Easy | Greedy | |
| B | Forest University | Python | O(T * N^2) | O(N) | Medium | Simulate | |
| C | Rebel Against The Empire | C++ PyPy | O(logN * (N^2 + H * N)) | O(N^2) | Hard | Graph, BFS, Binary Search | |
| D | Go++ | Python | O(L) | O(L) | Medium | Math Analysis |
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 |