Skip to content

Latest commit

 

History

History
85 lines (74 loc) · 10.7 KB

README.md

File metadata and controls

85 lines (74 loc) · 10.7 KB
  • 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

# Title Solution Time Space Difficulty Tag Note
A Increasing Substring Python O(N) O(1) Easy String
B Longest Progression Python Python O(N) O(1) Medium DP
C Consecutive Primes Python O(N^(1/4) * MAX_GAP) O(1) Medium Math, Prime Gap
D Truck Delivery PyPy O((N + Q) * (logN + log(MAX_A))) O(N) Hard DFS, Segment Tree

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