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