GoogleCodeJam Farewell Rounds
April 30, 2023 · View on GitHub
- Python solutions of Google Code Jam Farewell Rounds. Solution begins with
*means it will get TLE in the largest data set. - Total computation amount >
10^8is not friendly for Python to solve in 5 ~ 15 seconds. - A problem was marked as
Very Hardmeans that it was an unsolved one during the contest and may not be that difficult.
Rounds
Round A
- Round A is appropriate for beginners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Colliding Encoding | Python3 | O(N) | O(N) | Easy | Hash Table | |
| B | Illumination Optimization | Python3 | O(N) | O(1) | Medium | Greedy | |
| C | Rainbow Sort | Python3 | O(N) | O(N) | Easy | Hash Table | |
| D | ASCII Art | Python3 | O(1) | O(1) | Easy | Math | |
| E | Untie | Python3 | O(N) | O(1) | Medium | Greedy |
Round B
- Round B is about the level of a Kick Start round or a Code Jam Round 1.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Collecting Pancakes | Python3 | O(N) | O(1) | Medium | Greedy, Prefix Sum | |
| B | Intruder Outsmarting | Python3 | O(W * log(min(D, N))) | O(1) | Medium | Extended Euclidean Algorithm | |
| C | Spacious Sets | Python3 | O(NlogN) | O(N) | Easy | Binary Search, DP | |
| D | Railroad Maintenance | PyPy3 | O(N + L) | O(N + L) | Hard | DFS, Biconnected Components, Articulation Points | |
| E | Railroad Management | Python3 | O(N) | O(N) | Hard | Graph, Cycle |
Round C
- Round C is harder than a Code Jam Round 2 but easier than a Code Jam Round 3.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Game Sort: Part 1 | Python3 | O(P * L) | O(1) | Easy | Greedy, Counting Sort, Freq Table | |
| B | Immunization Operation | Python3 | O(M + VlogV) | O(V) | Easy | Simulation, Heap | |
| C | Evolutionary Algorithms | PyPy3 | O(NlogN) | O(N) | Medium | DFS, BIT, Fenwick Tree, Coordinate Compression, Combinatorics | |
| D | The Decades of Coding Competitions | PyPy3 | O(K * (N + M + Q)) | O(K * N) | Medium | Graph, Union Find, DSU | |
| E | Game Sort: Part 2 | Python3 | O(N) | O(1) | Hard | ❤️ | Constructive Algorithms, Prefix Sum, Freq Table, Greedy |
Round D
- Round D is meant for experienced competitors. It is between a Code Jam Round 3 and Finals difficulty.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Indispensable Overpass | Python3 | O(W + E + C) | O(W + E) | Easy | Tree DP, Combinatorics | |
| B | Genetic Sequences | PyPy3 PyPy3 | O((N + M) * log(N + M) + Q * log(min(N, M)) * logN) | O((N + M) * log(N + M)) | Medium | Suffix Array, LCP Array, Binary Search, RMQ, Sparse Table, Persistent BST, Persistent Treap | |
| C | Hey Google, Drive! | PyPy3 | O((R * C)^2 * F) | O(R * C) | Hard | ❤️ | Graph, BFS |
| D | Old Gold | PyPy3 | O(NlogN) | O(N) | Hard | ❤️ | Combinatorics, DP, Prefix Sum |
| E | Ring-Preserving Networks | Python3 | O(L) | O(L) | Medium | Graph, Constructive Algorithms, Clique, Greedy |