- Python3 solutions of Meta Hacker Cup 2022. Solution begins with
* means it will get TLE in the largest data set.
- Total computation amount >
10^8, which is not friendly for Python3 to solve in 5 ~ 15 seconds. A 6-minute timer is set for uploading the result this year.
- A problem was marked as
Very Hard means that it was an unsolved one during the contest and may not be that difficult.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|
| A1 | Consecutive Cuts - Chapter 1 | Python3 | O(N) | O(1) | Easy | | Constructive Algorithms, String |
| A2 | Consecutive Cuts - Chapter 2 | Python3 Python3 Python3 | O(N) | O(1) | Medium | | Constructive Algorithms, String, KMP Algorithm, Z-Function, Rabin-Karp Algorithm, Rolling Hash |
| B1 | Watering Well - Chapter 1 | Python3 | O(N + Q + min(N * Q, MAX_A_B_X_Y^2)) | O(min(N + Q, MAX_A_B_X_Y)) | Easy | | Math, Freq Table |
| B2 | Watering Well - Chapter 2 | Python3 | O(N + Q) | O(1) | Easy | | Math |
| C | Lemonade Life | PyPy3 | O(NlogN + V^2) | O(N + V) | Hard | | Geometry, Convex Hull, Monotone Chain Algorithm, Graph, Dijkstra's Algorithm |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|
| A | Fourth Player | Python3 | O(NlogN) | O(N) | Medium | | Games, Greedy |
| B | Third Trie | Python3 | O(N * M) | O(T) | Easy | | Trie, Combinatorics |
| C | Second Mistake | Python3 | O(3 * L * (N + Q)) | O(3 * L * N) | Easy | | Rabin-Karp Algorithm, Hash Table |
| D1 | First Time - Chapter 1 | Python3 | O(M + NlogN) | O(N) | Medium | | Unordered Set |
| D2 | First Time - Chapter 2 | Python3 | O(M + NlogN) | O(N) | Hard | | Unordered Set, Segment Tree, Number Theory |
| E1 | Zero Crossings - Chapter 1 | Python3 Python3 | O((N * M + Q) * log(N * M + Q)) | O(N * M + Q) | Hard | | Offline Solution, Geometry, Sort, Line Sweep, Treap, Sorted List, Binary Search, Tree, DFS, Hash |
| E2 | Zero Crossings - Chapter 2 | PyPy3 | O((N * M) * log(N * M) + Q * log(N * M)) | O((N * M) * log(N * M) | Hard | | Online Solution, Geometry, Sort, Line Sweep, Persistent Treap, Binary Search, Tree, DFS, Hash |
You can relive the magic of the 2022 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|
| A | ML Modeling | PyPy3 | O(MAX_X * MAX_Y * MAX_R * MIN_N + (MAX_X * MAX_Y)^2 + N) | O(MAX_X * MAX_Y) | Medium | | Geometry, Sampling |
| B | Emerald Exhibiting | PyPy3 | O(P * logN) | O(MAX_N) | Medium | | Combinatorics, Number Theory |
| C | Tile Transposing | PyPy3 PyPy3 | O(M * N * log(M * N)) | O(M * N) | Hard | | DFS, Persistent Union Find |
| D | Alphabet Adventuring | Python3 | O((R^2 + log(N + Q)) * (N + Q) + Q * (R^2 + log(N + Q))* log(N + Q)) | O((R^2 + log(N + Q)) * (N + Q)) | Hard | | Tree Traversal, Tree Ancestors (Binary Lifting), Heavy-Light Decomposition, Path Compression |
| E | Hazelnut Harvesting | Python3 | O(NlogN) | O(NlogN) | Hard | | Coordinate Compression, Segment Tree, Line Sweep, Mono Stack |
| F | Cup Counterbalancing | PyPy3 | O(N * S) | O(N) | Very Hard | | Geometry, Sampling |