GoogleCodeJam 2022 [](./LICENSE)
April 16, 2023 · View on GitHub
- Python3 solutions of Google Code Jam 2022. Solution begins with
*means it will get TLE in the largest data set. - Total computation amount >
10^8is not friendly for Python3 to solve in 5 ~ 15 seconds. - A problem was marked as
Very Hardmeans that it was an unsolved one during the contest and may not be that difficult.
Rounds
- Code Jam 2021
- Qualification Round
- Round 1A
- Round 1B
- Round 1C
- Round 2
- Round 3
- Virtual World Finals
- Code Jam Farewell Rounds
Qualification Round
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Punched Cards | Python3 | O(R * C) | O(1) | Easy | Array | |
| B | 3D Printing | Python3 | O(1) | O(1) | Easy | Math | |
| C | d1000000 | PyPy3 Python3 | O(NlogN) | O(1) | Easy | Sort | |
| D | Chain Reactions | Python3 Python3 | O(N) | O(N) | Medium | Topological Sort, Greedy | |
| E | Twisty Little Passages | Python3 Python3 | O(min(K, N)) | O(min(K, N)) | Hard | Probability, Importance Sampling |
Round 1A
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Double or One Thing | Python3 | O(|S|) | O(1) | Easy | String | |
| B | Equal Sum | Python3 Python3 | O(N) | O(1) | Medium | Math, Constructive Algorithms | |
| C | Weightlifting | Python3 | O(E^2 * W + E^3) | O(E^2 + W) | Hard | DP |
Round 1B
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Pancake Deque | Python3 | O(N) | O(1) | Easy | Greedy | |
| B | Controlled Inflation | Python3 | O(N * P) | O(1) | Medium | DP | |
| C | ASeDatAb | Python3 Python3 Python3 | O(L * 2^L) | O(L) | Hard | Precompute, BFS, Topological Sort, Constructive Algorithms |
Round 1C
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Letter Blocks | Python3 | O(N * L) | O(N) | Easy | String | |
| B | Squary | Python3 | O(N) | O(1) | Medium | Math, Constructive Algorithms | |
| C | Intranets | Python3 Python3 | precompute: O(MAX_M) runtime: O(1) | O(MAX_M) | Hard | Inclusion‐Exclusion Principle, Combinatorics, Catalan Number |
Round 2
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Spiraling Into Control | Python3 | O(N) | O(1) | Easy | Constructive Algorithms, Greedy, Math | |
| B | Pixelated Circle | Python3 | O(R) | O(1) | Medium | Math | |
| C | Saving the Jelly | PyPy3 | O(N^2 * sqrt(N)) | O(N^2) | Medium | Bipartite Matching, Hopcroft-Karp Algorithm | |
| D | I, O Bot | Python3 | O(NlogN) | O(N) | Hard | DP, Prefix Sum, Hash Table |
Round 3
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Revenge of GoroSort | Python3 | O(C * N) | O(N) | Easy | Math, Expected Value, Trial and Error | |
| B | Duck, Duck, Geese | PyPy3 C++ | O(NlogN) | O(N) | Medium | Segment Tree | |
| C | Mascot Maze | Python3 | O(N) | O(N) | Medium | Topological Sort, Greedy | |
| D | Win As Second | Python3 Python3 Python3 PyPy3 | precompute: O(N^5) on average runtime: O(N^3 + M * N^2) | O(N^2) | Hard | Bitmasks, Submask Enumeration, Sprague-Grundy Theorem, BFS, Constructive Algorithms, Precompute, Trial and Error |
Virtual World Finals
You can relive the magic of the 2022 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 | Wonderland Chase | Python3 | O(J + C) | O(J + C) | Easy | Graph, BFS | |
| B | Goose, Goose, Ducks? | *PyPy3 C++ | O(N + M + S * (logM + logS)) | O(N + S) | Hard | Logic-Based, Sorted List, Graph, BFS, SCC, Tarjan's Algorithm | |
| C | Slide Parade | PyPy3 | O(B * S + S^2) | O(B * S) | Medium | BFS, Constructive Algorithms, Bipartite Matching, Hungarian Algorithm, Eulerian Path, Hierholzer's Algorithm | |
| D | Schrödinger and Pavlov | PyPy3 | O(N) | O(N) | Hard | ❤️ | Graph, Probability, DP |
| E | Triangles | PyPy3 C++ | O(N^2) | O(N) | Very Hard | ❤️ | Geometry, Constructive Algorithms, Greedy |