Skip to content

kamyu104/GoogleKickStart-2020

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

Python solutions of Google Kick Start 2020. Solution begins with * means it will get TLE in the largest data set (total computation amount > 10^8, which 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.

Round A

# Title Solution Time Space Difficulty Tag Note
A Allocation Python O(N) O(MAX_A) Easy Greedy, Counting Sort
B Plates Python O(N * P * K) O(P) Easy DP, Prefix Sum
C Workout Python O(Nlog(MAX_DIFF)) O(1) Easy Binary Search, Greedy
D Bundling Python O(N * L) O(T) Medium Trie, Greedy, DFS, Stack

Round B

# Title Solution Time Space Difficulty Tag Note
A Bike Tour Python O(N) O(1) Easy Array
B Bus Routes Python O(N) O(1) Easy Greedy
C Robot Path Decoding Python O(N) O(N) Easy Stack
D Wandering Robot Python Python O(W + H) O(W + H) Hard Binomial Coefficients, Probability, Log Representation, Prefix Sum

Round C

# Title Solution Time Space Difficulty Tag Note
A Countdown Python O(N) O(1) Easy Array
B Stable Wall Python O(R * C) O(1) Easy Topological Sort, DFS
C Perfect Subarray PyPy O(N * sqrt(N * MAX_A)) O(N * MAX_A) Medium Math, Prefix Sum
D Candies Python O(N + QlogN) O(N) Medium BIT, Fenwick Tree

Round D

# Title Solution Time Space Difficulty Tag Note
A Record Breaker Python O(N) O(1) Easy Array
B Alien Piano Python O(K) O(1) Easy Greedy
C Beauty of Tree Python O(N) O(N) Medium DFS, Math
D Locked Doors PyPy O(NlogN + QlogN) O(N) Hard Cartesian Tree, Binary Lifting

Round E

# Title Solution Time Space Difficulty Tag Note
A Longest Arithmetic Python O(N) O(1) Easy Array
B High Buildings Python O(N) O(N) Easy Constructive Algorithms
C Toys Python O(NlogN) O(N) Medium Greedy, Heap
D Golden Stone Python Python O((N * S + M * S + R * N) * log(N * S)) O(N * S + M) Hard Dijkstra's Algorithm

Round F

# Title Solution Time Space Difficulty Tag Note
A ATM Queue Python O(NlogN) O(1) Easy Sort
B Metal Harvest Python O(NlogN) O(1) Easy Sort
C Painters' Duel Python O(2^(S^2)) O(2^(S^2)) Medium Memoization, Alpha Beta Pruning
D Yeetzhee Python O(M * S) O(M * S) Hard Math, Expected Value, Memoization, Greedy

Round G

# Title Solution Time Space Difficulty Tag Note
A Kick_Start Python O(N) O(1) Easy Math
B Maximum Coins Python Python O(N^2) O(1) Easy Matrix
C Combination Lock Python Python O(WlogW) O(1) Easy Math, Median, Prefix Sum
D Merge Cards Python Python O(N) O(N) Medium Math, Expected Value, DP, Precompute, Prefix Sum

Round H

# Title Solution Time Space Difficulty Tag Note
A Retype Python O(1) O(1) Easy Math
B Boring Numbers Python O(logR) O(1) Easy Math
C Rugby Python O(NlogN) O(N) Medium Math, Median
D Friends PyPy PyPy O(A^3 + L^2 * (N + Q)) O(A^2) Medium Floyd-Warshall Algorithm