Skip to content

Latest commit

 

History

History
82 lines (71 loc) · 10.1 KB

README.md

File metadata and controls

82 lines (71 loc) · 10.1 KB
  • 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

# Title Solution Time Space Difficulty Tag Note
A Sort the Fabrics Python3 O(MAX_C * NlogN) O(MAX_C * N) Easy Sort
B Water Container System Python3 O(N) O(N) Easy BFS
C Story of Seasons Python3 Python3 O(NlogN) O(N) Medium Greedy, Heap
D Scheduling a Meeting Python3 O(D + N + M) O(D + N + M) Hard Line Sweep, Greedy

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