GoogleCodeJam 2020 [](./LICENSE)
May 17, 2021 · View on GitHub
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
Qualification Round
| # | 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 |
Round 1A
| # | 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 |
Round 1B
| # | 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 |
Round 1C
| # | 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 |
Round 2
| # | 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) |
Round 3
| # | 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 |
Virtual World Finals
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 |