kamyu104/googlecodejam-2021

🏃 Python Solutions of All 27 Problems in GCJ 2021

GoogleCodeJam 2021

• Python solutions of Google Code Jam 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

• Code Jam 2020
• Qualification Round
• Round 1A
• Round 1B
• Round 1C
• Round 2
• Round 3
• Virtual World Finals
• Code Jam 2022

Qualification Round

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Reversort	Python	O(N^2)	O(1)	Easy		Simulation
B	Moons and Umbrellas	Python	O(N)	O(1)	Easy		DP
C	Reversort Engineering	Python Python	O(N)	O(1)	Easy		Greedy
D	Median Sort	Python	O(N^2)	O(1)	Medium		Ternary Search, Insertion Sort
E	Cheating Detection	Python Python Python Python	O(S * Q)	O(S + Q)	Hard		Uniform Distribution, Inversions Counting, Correlation Coefficient

Round 1A

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Append Sort	Python Python	O(N * log(MAX_X))	O(1)	Easy		Greedy
B	Prime Time	Python	O((MAX_P * logX) * (M + logX))	O(1)	Medium		Math, Prime Factorization, Pruning
C	Hacked Exam	Python	precompute: O(MAX_Q^2) runtime: O(Q)	O(MAX_Q^2)	Hard		Binomial Coefficients, DP, Math, Expected Value

Round 1B

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Broken Clock	Python	O(1)	O(1)	Medium		Math, Linear Congruence
B	Subtransmutation	Python Python	O(MAX_M^2)	O(MAX_M)	Medium		Math, Bézout's Identity, Greedy
C	Digit Blocks	Python	precompute: O(N^3 * B * D) runtime: O(N * B)	O(N^3 * B * D)	Hard		DP, Math, Expected Value

Round 1C

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Closest Pick	Python	O(NlogN)	O(N)	Easy		Math, Sort
B	Roaring Years	Python	O(D^2 * logD)	O(D)	Medium		Math, Binary Search
C	Double or NOTing	Python Python Python	O(|E| + |S|)	O(|E| + |S|)	Hard		Math, Bit Manipulation, KMP Algorithm

Round 2

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Minimum Sort	Python	O(ClogN)	O(1)	Easy		Selection Sort
B	Matrygons	Python	precompute: O(NlogN) runtime: O(1)	O(N)	Medium		Precompute, DP
C	Hidden Pancakes	Python Python	O(N)	O(N)	Medium		Math, Binomial Coefficients, DP
D	Retiling	Python	O((R * C)^3)	O((R * C)^2)	Hard		Hungarian Weighted Bipartite Matching

Round 3

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Build-A-Pair	PyPy PyPy Python	O(N)	O(1)	Easy		Enumeration, Greedy
B	Square Free	Python	O(R^2 * C^2)	O(R + C)	Medium		Max Flow, Greedy
C	Fence Design	PyPy	O(NlogN) on average	O(N)	Hard	❤️	Geometry, Convex Hull, Divide and Conquer, Random
D	Binary Search Game	PyPy PyPy Python	O(2^(2^(L-1)) * (2^L + N^2) + N^3)	O(N^2 + L)	Hard	❤️	Combinatorics, Counting, DP, Greedy, Polynomial, Faulhaber's Formula, Lagrange Interpolation

Virtual World Finals

You can relive the magic of the 2021 Code Jam Virtual World Finals by watching the Live Stream Recording of the competition, problem explanations, and announcement of winners.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Cutting Cake	Python	O(NlogN)	O(N)	Medium		Math, Line Sweep
B	Slide Circuits	Python Python Python	O(B + N + SlogS)	O(SlogS)	Medium		Graph, Hash, Prefix Sum
C	Ropes	PyPy	O(N^3)	O(N^2)	Hard	❤️	Greedy
D	Divisible Divisions	Python Python	O(|S|logD)	O(min(|S|logD, D))	Medium		Math, Linear Congruence, Chinese Remainder Theorem, DP, Prefix Sum
E	Infinitree	PyPy PyPy3	O(N^3.5 * logN + N^3 * logB)	O(N^2.5 * logN + N^2 * logB)	Very Hard	❤️	Graph, Binary Tree, Matrix Exponentiation, Matrix Power Series, Prefix Sum, Binary Search, LCA, Tarjan's Algorithm

googlecodejam-2021's Issues

Can you explain the solution of round2 C?

You solution is much simpler than official solution, I want to learn but I don't understand how it works. I would be appreciated if you explain the details of the code.
Thanks in advance.