- Python solutions of Google Kick Start 2021. Solution begins with
* means it will get TLE in the largest data set.
- Total computation amount >
10^8 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.
- From 2021-04,
PyPy3 is supported by the online judge.
- From 2021-11,
Python2/PyPy2 is no longer supported by the online judge.
- You need to run
2to3 -n -W --add-suffix=3 solution.py to convert the solution into Python3/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
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 |
GoogleKickStart-2021 copied to clipboard
kamyu104
kamyu104