GoogleKickStart 2020 [](./LICENSE)
October 17, 2021 ยท View on GitHub
Python solutions of Google Kick Start 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.
Round A
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Allocation | Python | O(N) | O(MAX_A) | Easy | Greedy, Counting Sort | |
| B | Plates | Python | O(N * P * K) | O(P) | Easy | DP, Prefix Sum | |
| C | Workout | Python | O(Nlog(MAX_DIFF)) | O(1) | Easy | Binary Search, Greedy | |
| D | Bundling | Python | O(N * L) | O(T) | Medium | Trie, Greedy, DFS, Stack |
Round B
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Bike Tour | Python | O(N) | O(1) | Easy | Array | |
| B | Bus Routes | Python | O(N) | O(1) | Easy | Greedy | |
| C | Robot Path Decoding | Python | O(N) | O(N) | Easy | Stack | |
| D | Wandering Robot | Python Python | O(W + H) | O(W + H) | Hard | Binomial Coefficients, Probability, Log Representation, Prefix Sum |
Round C
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Countdown | Python | O(N) | O(1) | Easy | Array | |
| B | Stable Wall | Python | O(R * C) | O(1) | Easy | Topological Sort, DFS | |
| C | Perfect Subarray | PyPy | O(N * sqrt(N * MAX_A)) | O(N * MAX_A) | Medium | Math, Prefix Sum | |
| D | Candies | Python | O(N + QlogN) | O(N) | Medium | BIT, Fenwick Tree |
Round D
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Record Breaker | Python | O(N) | O(1) | Easy | Array | |
| B | Alien Piano | Python | O(K) | O(1) | Easy | Greedy | |
| C | Beauty of Tree | Python | O(N) | O(N) | Medium | DFS, Math | |
| D | Locked Doors | PyPy | O(NlogN + QlogN) | O(N) | Hard | Cartesian Tree, Binary Lifting |
Round E
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Longest Arithmetic | Python | O(N) | O(1) | Easy | Array | |
| B | High Buildings | Python | O(N) | O(N) | Easy | Constructive Algorithms | |
| C | Toys | Python | O(NlogN) | O(N) | Medium | Greedy, Heap | |
| D | Golden Stone | Python Python | O((N * S + M * S + R * N) * log(N * S)) | O(N * S + M) | Hard | Dijkstra's Algorithm |
Round F
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | ATM Queue | Python | O(NlogN) | O(1) | Easy | Sort | |
| B | Metal Harvest | Python | O(NlogN) | O(1) | Easy | Sort | |
| C | Painters' Duel | Python | O(2^(S^2)) | O(2^(S^2)) | Medium | Memoization, Alpha Beta Pruning | |
| D | Yeetzhee | Python | O(M * S) | O(M * S) | Hard | Math, Expected Value, Memoization, Greedy |
Round G
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Kick_Start | Python | O(N) | O(1) | Easy | Math | |
| B | Maximum Coins | Python Python | O(N^2) | O(1) | Easy | Matrix | |
| C | Combination Lock | Python Python | O(WlogW) | O(1) | Easy | Math, Median, Prefix Sum | |
| D | Merge Cards | Python Python | O(N) | O(N) | Medium | Math, Expected Value, DP, Precompute, Prefix Sum |
Round H
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Retype | Python | O(1) | O(1) | Easy | Math | |
| B | Boring Numbers | Python | O(logR) | O(1) | Easy | Math | |
| C | Rugby | Python | O(NlogN) | O(N) | Medium | Math, Median | |
| D | Friends | PyPy PyPy | O(A^3 + L^2 * (N + Q)) | O(A^2) | Medium | Floyd-Warshall Algorithm |