- Python3 solutions of Meta Hacker Cup 2024. 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 |
|---|
| A | Set, Cover | Python3 | O(N^2) | O(N) | Easy | | Array |
| B | Least Common Ancestor | Python3 | O(N * (logN)^2) | O(N) | Easy | | Sort, DFS, Sorted List, Freq Table, Small-to-Large Merging |
| C | Coin Change | Python3 | O(min(N, THRESHOLD)) | O(1) | Hard | | Expected Value, Harmonic Series, Euler's Constant |
| D | Min-flow Max-cut | Python3 | O(N * logN * logM) | O(N) | Hard | | DFS, Treap, Prefix Sum, Small-to-Large Merging |
| E1 | All Triplets Shortest Path (Part 1) | Python3 | O(N) | O(N) | Medium | | Graph, Floyd-Warshall Algorithm |
| E2 | All Triplets Shortest Path (Part 2) | Python3 | O(N) | O(N) | Medium | | Graph, Floyd-Warshall Algorithm |
You can relive the magic of the 2024 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|
| A | Duplicate Order | Python3 | O(N + min(M1, M2) + H^2) | O(N + min(M1, M2) + H) | Easy | | Combinatorics, Prefix Sum, Fast Exponentiation |
| B | Distributed Server | Python3 | O((R + C)^2 * (R * C)^3) | O(R * C) | Easy | | Binary Search, Max Flow, Dinic's Algorithm |
| C | Chicken Tender | Python3 | O(N^2 * logR) | O(N) | Medium | | Ternary Search, Geometry |
| D | Sushi Platter | Python3 | O(N^3 * MAX_A + M! * ((M - 1) * 2^(M - 1))) | O(N^2 * MAX_A) | Medium | | Connected Component DP, Prefix Sum, Permutation, Bitmasks |
| E | Snake Cover | Python3 | O(M) | O(M) | Medium | | Simulation, Data Structures, Queue, Mono Deque |
| F | Pizza Broiler | Python3 | O(W + NlogW) | O(W) | Hard | | Geometry, Binary Search, Prefix Sum, Count Lattices |