Python solutions of Google Code Jam 2018. 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).
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Saving The Universe Again | Python | O(P) | O(P) | Easy | Greedy | |
| B | Trouble Sort | Python | O(NlogN) | O(N) | Easy | Sort | |
| C | Go, Gopher! | Python | O(P) | O(1) | Medium | Probability, Simulation | |
| D | Cubic UFO | Python | O(1) | O(1) | Medium | Rotation Matrix, Geometry |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Waffle Choppers | Python | O(R * C) | O(R + C) | Easy | Array, Accumulation Sum | |
| B | Bit Party | Python | O(ClogC * log(max(S)*B+max(P))) | O(C) | Medium | Binary Search | |
| C | Edgy Baking | Python | O(N^2) | O(N) | Medium | Intervals |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Rounding Error | Python | O(NlogN) | O(N) | Medium | Greedy, Memoization | |
| B | Mysterious Road Signs | Python | O(S) | O(1) | Medium | Graph, Sliding Window | |
| C | Transmutation | C++ *Python | O(M^3 * logS) | O(M^2) | Hard | Binary Search, Overflow Pruning |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | A Whole New Word | Python | O(T) | O(T) | Easy | Trie | |
| B | Lollipop Shop | Python | O(N^2) | O(N) | Easy | Probability | |
| C | Ant Stack | C++ *Python | O(N * K) | O(K) | Medium | DP |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Falling Balls | Python | O(C^2) | O(C^2) | Easy | Greedy | |
| B | Graceful Chainsaw Jugglers | C++ *Python | O(R^(4/3)*B^(4/3)) | O(R^(4/3)*B^(4/3)) | Medium | DP, Memoization | |
| C | Costume Change | C++ *Python | O(N^2 * sqrt(N)) | O(N) | Medium | Bipartite Matching | |
| D | Gridception | C++ *Python | O(2^4 * R^2 * C^2) | O(R * C) | Medium | Graph, DFS |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Field Trip | Python | O(N) | O(1) | Easy | Greedy | |
| B | Name-Preserving Network | Python | O(LlogL) | O(L) | Medium | Probability, Topology | |
| C | Raise the Roof | Python | O(N^2) | O(N) | Hard | Geometry, Vector | |
| D | Fence Construction | Python | O(FlogF) | O(F) | Hard | Dual Graph, Greedy |