GoogleKickStart 2021 [](./LICENSE)
March 20, 2022 ยท View on GitHub
- Python solutions of Google Kick Start 2021. 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. - From 2021-04,
PyPy3is supported by the online judge. - From 2021-11,
Python2/PyPy2is no longer supported by the online judge. - You need to run
2to3 -n -W --add-suffix=3 solution.pyto convert the solution intoPython3/PyPy3.
Rounds
Round A
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | K-Goodness String | Python | O(N) | O(1) | Easy | String | |
| B | L Shaped Plots | Python | O(R * C) | O(min(R, C)) | Easy | DP | |
| C | Rabbit House | Python | O(R * C) | O(R * C) | Medium | Bucket Sort, BFS | |
| D | Checksum | Python | O(N^2) | O(N^2) | Hard | MST, Prim's Algorithm |
Round B
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Increasing Substring | Python | O(N) | O(1) | Easy | String | |
| B | Longest Progression | Python Python | O(N) | O(1) | Medium | DP | |
| C | Consecutive Primes | Python | O(N^(1/4) * MAX_GAP) | O(1) | Medium | Math, Prime Gap | |
| D | Truck Delivery | PyPy | O((N + Q) * (logN + log(MAX_A))) | O(N) | Hard | DFS, Segment Tree |
Round C
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Smaller Strings | Python | O(N) | O(1) | Easy | Math, Counting | |
| B | Alien Generator | Python | O(sqrt(G)) | O(1) | Easy | Math, Arithmetic Progression | |
| C | Rock Paper Scissors | Python Python | O(N) | O(1) | Medium | Math, Expected Value, DP, Backtracing, Precompute | |
| D | Binary Operator | Python Python Python | O(N * E) | O(N * E) | Hard | Math, Polynomial Calculator, Hash |
Round D
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Arithmetic Square | Python | O(1) | O(1) | Easy | Math, Counting | |
| B | Cutting Intervals | Python | O(NlogN) | O(N) | Medium | Line Sweep, Greedy | |
| C | Final Exam | PyPy PyPy | O(NlogN + M * log(N + M)) | O(N + M) | Medium | Skip List, Sorted List, Binary Search | |
| D | Primes and Queries | Python Python | O(N * (logN + log(log(MAX_A))) + Q * (logN + log(log(MAX_VAL)) + log(log(MAX_S)))) | O(N) | Hard | BIT, Fenwick Tree, LTE, Lifting The Exponent Lemma, Binary Search |
Round E
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Shuffled Anagrams | Python | O(N) | O(N) | Easy | String, Grouping | |
| B | Birthday Cake | Python | O(1) | O(1) | Hard | Math, Greedy | |
| C | Palindromic Crossword | Python Python Python | O(N * M) | O(N * M) | Easy | Graph, BFS, DFS, Union Find | |
| D | Increasing Sequence Card Game | Python | precompute: O(EPS^(-1)) runtime: O(1) | O(EPS^(-1)) | Medium | Math, Expected Value, Harmonic Series, DP, Precompute, Series Estimation with Integrals |
Round F
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Trash Bins | Python | O(N) | O(N) | Easy | DP | |
| B | Festival | Python PyPy Python Python | O(NlogN) | O(N) | Easy | Line Sweep, BIT, Fenwick Tree, Skip List, Sorted List, Heap | |
| C | Star Trappers | PyPy Python | O(N^3) | O(1) | Medium | Math, Geometry | |
| D | Graph Travel | Python | O(M + N * 2^N) | O(2^N) | Medium | DP, Bitmask |
Round G
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Dogs and Cats | Python Python | O(N) | O(1) | Easy | Simulation | |
| B | Staying Hydrated | Python Python Python | O(K) on average | O(K) | Easy | Prefix Sum, Binary Search, Math, Median, Quick Select | |
| C | Banana Bunches | PyPy | O(N^2) | O(min(N^2, K)) | Medium | Two Pointers, DP | |
| D | Simple Polygon | Python Python | O(N) | O(1) | Hard | Math, Pick's Theorem, Constructive Algorithms |
Round H
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Transform the String | Python Python | O(N) | O(1) | Easy | String | |
| B | Painter | Python Python | O(N) | O(1) | Easy | Greedy | |
| C | Silly Substitutions | Python Python | O(N) | O(N) | Medium | Simulation, Linked List | |
| D | Dependent Events | Python Python Python | O(NlogN + QlogN) | O(NlogN) | Hard | Euler's Theorem, Fermat's Little Theorem, Probability, DFS, LCA, Tree Ancestors (Binary Lifting), Tarjan's Offline LCA Algorithm, DP |