开源软件名称（OpenSource Name）：

kamyu104/GoogleKickStart-2021

开源软件地址(OpenSource Url)：

https://github.com/kamyu104/GoogleKickStart-2021

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.

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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

#	Title	Solution	Time	Space	Difficulty	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