- 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.
| # | 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 |
| # | 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 |
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 |