- 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. 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 | Walk the Line | Python3 | O(1) | O(1) | Easy | Greedy | |
| B | Line by Line | Python3 | O(1) | O(1) | Easy | Math | |
| C | Fall in Line | Python3 | O(K * N) | O(1) | Medium | Randomized Algorithm | |
| D1 | Line of Delivery (Part 1) | Python3 | O(NlogN) | O(1) | Medium | Sort | |
| D2 | Line of Delivery (Part 2) | Python3 | O(NlogN) | O(1) | Hard | Sort |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Subsonic Subway | Python3 | O(N) | O(1) | Easy | Math | |
| B | Prime Subtractorization | Python3 | precompute: O(MAX_N) runtime: O(1) |
O(MAX_N) | Medium | Number Theory, Linear Sieve of Eratosthenes, DP |
|
| C | Substantial Losses | Python3 | O(1) | O(1) | Medium | Expected Value | |
| D | Substitution Cipher | Python3 | O(N) | O(1) | Hard | Greedy, DP | |
| E | Wildcard Submissions | PyPy3 | O(N * L * S) | O(L * S) | Hard | DP, Inclusion-Exclusion Principle |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A1 | Cottontail Climb (Part 1) | Python3 | O(285) | O(45) | Easy | Precomputation | |
| A2 | Cottontail Climb (Part 2) | PyPy3 | precompute: O(17 * 73025424) runtime: O(73025424) |
O(73025424) | Easy | Precomputation, Backtracking | |
| B | Four in a Burrow | PyPy3 | O((R * C) * (R + 1)^C) | O(C * (R + 1)^C) | Medium | BFS | |
| C | Bunny Hopscotch | PyPy3 | O((R * C * log(min(R, C))) * log(max(R, C))) | O(R * C) | Medium | Binary Search, Two Pointers, Sliding Window, BIT, Fenwick Tree | |
| D | Splitting Hares | Python3 | O(N + MAX_W^2) | O(N + MAX_W) | Hard | Greedy, DP, Backtracing |
| # | 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, Deque, Mono Deque | |
| F | Pizza Broiler | Python3 | O(W + NlogW) | O(W + NlogW) | Hard | Geometry, Binary Search, Prefix Sum, Count Lattices |