Python solutions of Google Code Jam 2020. 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 problem was marked as Very Hard means that it was an unsolved one during the contest and may not be that difficult.
- Code Jam 2019
- Qualification Round
- Round 1A
- Round 1B
- Round 1C
- Round 2
- Round 3
- Virtual World Finals
- Code Jam 2021
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Vestigium | Python | O(N^2) | O(N) | Easy | Math | |
| B | Nesting Depth | Python | O(N) | O(1) | Easy | String | |
| C | Parenting Partnering Returns | Python | O(NlogN) | O(1) | Easy | Greedy | |
| D | ESAb ATAd | Python | O(B^2) | O(B) | Medium | Bit Manipulation | |
| E | Indicium | Python | O(N^3 * sqrt(N)) | O(N) | Hard | Bipartite Matching, Greedy |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Pattern Matching | Python | O(N * P) | O(P) | Easy | String | |
| B | Pascal Walk | Python | O(logN^2) | O(logN) | Medium | Math, Greedy, Bit Manipulation | |
| C | Square Dance | Python | O(R * C) | O(R * C) | Hard | Simulation, BFS, Linked List |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Expogo | Python Python | O(log(|X| + |Y|)) | O(1) | Medium | Variant of Pogo | Invariant, Greedy |
| B | Blindfolded Bullseye | Python | O(128) | O(1) | Medium | Probability, Binary Search, Geometry | |
| C | Join the Ranks | Python | O(R * S) | O(1) | Hard | One-Liner | Invariant, Sort |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Overexcited Fan | Python | O(M) | O(1) | Easy | Simulation, Math | |
| B | Overrandomized | Python | O(L * U) | O(1) | Easy | Probability | |
| C | Oversized Pancake Choppers | PyPy Python Python | O(N * DlogD) | O(D * N) | Hard | Sort, Hash Table, Euclidean Algorithm, Binary Search, Greedy, Bucket, LCM |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Incremental House of Pancakes | Python Python | O(1) | O(1) | Easy | Binary Search, Math | |
| B | Security Update | Python | O(ClogC + D) | O(C) | Medium | Sort | |
| C | Wormhoe in One | Python | O(N^2) | O(N^2) | Medium | Math | |
| D | Emacs++ | PyPy* PyPy | O(KlogK + QlogK) | O(KlogK) | Hard | Tree, Lazy Construction, Middle Line, Dijkstra's Algorithm, Iterative Recursion, LCA, Prefix Sum, Tree Ancestors (Binary Lifting) |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Naming Compromise | Python | O(C * J) | O(C * J) | Easy | DP, Edit Distance | |
| B | Thermometers | Python Python | O(N^2) | O(1) | Hard | Greedy, Mirror | |
| C | Pen Testing | PyPy Python PyPy Python |
O(T * N^2 + N * S) | O(N * (T + S)) | Hard | ❤️ | Heuristic, Memoization, Probability |
| D | Recalculating | *PyPy C++ *PyPy C++ |
O(N^2 * logN) | O(N^2) | Hard | ❤️ | Coordinate Rotation, Sliding Window, Rolling Hash, Rabin-Karp Algorithm, Line Sweep, Coordinate Compression, Segment Tree |
You can relive the magic of the 2020 Code Jam Virtual 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 | Pack the Slopes | PyPy | O(N * (logN)^2) | O(N) | Medium | Greedy, Heavy-Light Decomposition, Stack, Recursion, Segment Tree (Lazy Propagation), RMQ | |
| B | Adjacent and Consecutive | Python Python Python | O(NlogN) | O(N) | Hard | ❤️ | State Compression, Math, Skip List |
| C | Hexacoin Jam | PyPy | O(B^(D + 1) * D + N^2 * D) | O(B^(D + 1) * D) | Hard | ❤️ | Structure Match, Hash, Math |
| D | Musical Cords | PyPy | O(NlogN + N * K) on average | O(N * K) | Very Hard | ❤️ | Geometry, Trigonometric Functions, Two Pointers, Binary Search, Quick Select, Sort |
| E | Replace All | Python | O(A^3) | O(A^2) | Medium | Floyd-Warshall Algorithm, SCC, Bipartite Matching |