- Python3 solutions of Google Kick Start 2022. Solution begins with
* means it will get TLE in the largest data set.
- Total computation amount >
10^8 is not friendly for Python3 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.
Rounds
Round A
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Speed Typing |
Python3 |
O(|P|) |
O(1) |
Easy |
|
String |
| B |
Challenge Nine |
Python3 |
O(logN) |
O(logN) |
Easy |
|
Math, Greedy |
| C |
Palindrome Free Strings |
Python3 Python3 |
O(N) |
O(1) |
Medium |
|
Backtracking, DP |
| D |
Interesting Integers |
Python3 Python3 |
precompute: O(2835 * log(MAX_B)^2)
runtime: O(9 * (logB)^2) |
O(2835 * log(MAX_B)^2) |
Hard |
|
Counting, Memoization |
Round B
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Infinity Area |
Python3 |
O(logR) |
O(1) |
Easy |
|
Math |
| B |
Palindromic Factors |
Python3 |
O(sqrt(A) * logA) |
O(1) |
Easy |
|
Math, String |
| C |
Unlock the Padlock |
Python3 |
O(N^2) |
O(N^2) |
Medium |
|
Memoization |
| D |
Hamiltonian Tour |
Python3 PyPy3 Python3 |
O(R * C) |
O(R * C) |
Hard |
|
DFS, Constructive Algorithms, BFS, Spanning Tree, Wall Follower |
Round C
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
New Password |
Python3 |
O(N) |
O(1) |
Easy |
|
String |
| B |
Range Partition |
Python3 |
O(N) |
O(1) |
Easy |
|
Math, Greedy |
| C |
Ants on a Stick |
Python3 Python3 |
O(NlogN) |
O(N) |
Medium |
|
Sort, Deque |
| D |
Palindromic Deletions |
PyPy3 |
O(N^3) |
O(N^2) |
Hard |
|
Math, Expected Value, Combinatorics, DP, Inclusion-Exclusion Principle |
Round D
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Image Labeler |
Python3 Python3 |
O(N) on average |
O(1) |
Easy |
|
Greedy, Sort, Quick Select |
| B |
Maximum Gain |
PyPy3 PyPy3 |
O(K^2 + N + M) |
O(1) |
Easy |
|
Prefix Sum, Sliding Window, Brute Force |
| C |
Touchbar Typing |
PyPy3 |
O(N * M) |
O(N * M) |
Medium |
|
Greedy, DP |
| D |
Suspects and Witnesses |
PyPy3 |
O(N * K) |
O(K) |
Hard |
|
Logic-Based, Graph, BFS |
Round E
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Coloring Game |
Python3 |
O(1) |
O(1) |
Easy |
|
Greedy, Math |
| B |
Students and Mentors |
Python3 Python3 |
O(NlogN) |
O(N) |
Easy |
|
Sort, Binary Search, Two Pointers |
| C |
Matching Palindrome |
Python3 Python3 Python3 |
O(N) |
O(N) |
Medium |
|
Brute Force, Manacher's Algorithm, KMP Algorithm |
| D |
Pizza Delivery |
Python3 |
O(M * N^2 * 2^P) |
O(N^2 * 2^P) |
Hard |
|
BFS, DP |
Round F
Round G
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Walktober |
Python3 |
O(M * N) |
O(N) |
Easy |
|
Array |
| B |
Curling |
Python3 |
O(N + M) |
O(N + M) |
Easy |
|
Array |
| C |
Happy Subarrays |
Python3 Python3 |
O(N) |
O(N) |
Medium |
|
Prefix Sum, Mono Stack |
| D |
Cute Little Butterfly |
PyPy3 Python3 |
O(NlogN) |
O(N) |
Hard |
|
DP, Segment Tree, Coordinate Compression, Sorted List |
Round H
| # |
Title |
Solution |
Time |
Space |
Difficulty |
Tag |
Note |
| A |
Running in Circles |
Python3 |
O(N) |
O(1) |
Easy |
|
Simulation, Math |
| B |
Magical Well Of Lilies |
Python3 |
O(MAX_L * log(MAX_L)) |
O(MAX_L) |
Medium |
|
DP |
| C |
Eelectricity |
Python3 Python3 Python3 |
O(N) |
O(N) |
Medium |
|
Tree DP, Topological Sort, BFS, DFS |
| D |
Level Design |
PyPy3 |
O(N * sqrt(N)) |
O(N) |
Hard |
|
DP, Greedy, Mono Deque |
GoogleKickStart-2022 copied to clipboard
kamyu104
kamyu104