GoogleCodeJam 2018
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).
Qualification Round
# | 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 |
Round 1A
# | 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 |
Round 1B
# | 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 |
Round 1C
# | 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 |
Round 2
# | 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 |
Round 3
# | 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 |