- Python3 solutions of Google Kick Start 2022. Solution begins with
*means it will get TLE in the largest data set. - Total computation amount >
10^8is not friendly for Python3 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.
| # | 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 |
| # | 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 |
| # | 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 |
| # | 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 |
| # | 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 |