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