- 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
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 copied to clipboard
kamyu104
kamyu104