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).
# | 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/4) | 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(log(L + R)) | 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 Jump) |
# | 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 |