- 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. A6-minutetimer is set for uploading the result this year. - A problem was marked as
Very Hardmeans that it was an unsolved one during the contest and may not be that difficult.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Second Hands | Python3 | O(N) | O(N) | Easy | Greedy | |
| B1 | Second Friend | Python3 | O(R * C) | O(1) | Easy | Constructive Algorithms | |
| B2 | Second Second Friend | Python3 | O(R * C) | O(R * C) | Medium | Constructive Algorithms, BFS | |
| C1 | Second Meaning | Python3 | O(N^2) | O(N) | Easy | Constructive Algorithms | |
| C2 | Second Second Meaning | Python3 | O(NlogN) | O(logN) | Medium | Constructive Algorithms | |
| D | Second Flight | Python3 Python3 | O(N + Q + M * min(sqrt(Q), N)) | O(N + M + Q) | Hard | Graph, Memoization |
| # | 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 |
|---|---|---|---|---|---|---|---|
| A1 | Perfectly Balanced - Chapter 1 | Python3 | O(N + Q) | O(N) | Easy | Prefix Sum | |
| A2 | Perfectly Balanced - Chapter 2 | Python3 | O((N + Q) * logN) | O(N) | Medium | Hash, BIT, Fenwick Tree | |
| B | Balance Sheet | Python3 | O(NlogN + N * K) | O(N * K) | Medium | Sort, Greedy, DP | |
| C | Balance Scale | Python3 | precompute: O(MAX_N * MAX_C) runtime: O(N) |
precompute: O(MAX_N * MAX_C) runtime: O(1) |
Easy | Combinatorics, Probability | |
| D1 | Work-Life Balance - Chapter 1 | Python3 | O((N + M) * logN) | O(N) | Medium | BIT, Fenwick Tree, Greedy | |
| D2 | Work-Life Balance - Chapter 2 | Python3 | O((N + M) * logN) | O(N) | Hard | BIT, Fenwick Tree, Greedy |
| # | 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 |