- Python3 solutions of Meta Hacker Cup 2023. 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 |
|---|---|---|---|---|---|---|---|
| A1 | Cheeseburger Corollary 1 | Python3 | O(1) | O(1) | Easy | Math | |
| A2 | Cheeseburger Corollary 2 | Python3 | O(1) | O(1) | Medium | Math | |
| B | Dim Sum Delivery | Python3 | O(1) | O(1) | Easy | Game | |
| C | Two Apples a Day | Python3 | O(NlogN) | O(1) | Easy | Sort, Two Pointers | |
| D | Road to Nutella | Python3 Python3 | O(N + M + QlogQ) | O(N + M + Q) | Hard | Tarjan's Algorithm, Biconnected Components, DFS, Bipartite Coloring, BFS, LCA, Binary Lifting, Counting Sort, Union Find, DSU |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Here Comes Santa Claus | Python3 | O(N) | O(1) | Easy | Math | |
| B1 | Sum 41 (Chapter 1) | Python3 Python3 Python3 | precompute: O(sqrt(MAX_P)) runtime: O(logP + sqrt(P)/log(sqrt(P))) |
O(sqrt(MAX_P) + K) | Easy | Constructive Algorithms, Greedy, Number Theory, Linear Sieve of Eratosthenes, Backtracking, Unique Partitions |
|
| B2 | Sum 41 (Chapter 2) | Python3 Python3 | O(89166 + K^2) | O(K) | Medium | Backtracking, Unique Partitions | |
| C1 | Back in Black (Chapter 1) | Python3 | O(NlogN + Q) | O(N) | Easy | Number Theory, Greedy | |
| C2 | Back in Black (Chapter 2) | Python3 | O(NlogN + Q) | O(N) | Medium | Number Theory, Greedy | |
| D | Today is Gonna be a Great Day | Python3 | O(NlogN + QlogN) | O(N) | Medium | Segment Tree | |
| E | Bohemian Rap-sody | PyPy3 | O(QlogN + QlogQ + (L + Q) * sqrt(N)) | O(Q + N) | Hard | Trie, Offline Solution, Binary Search, Sqrt Decomposition, Mo's Algorithm, Freq Table, Prefix Sum, Math |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A1 | Ready, Go (Part 1) | Python3 | O(R * C) | O(R * C) | Easy | BFS | |
| A2 | Ready, Go (Part 2) | Python3 | O(R * C) | O(R * C) | Easy | BFS, DP | |
| B | Meta Game | Python3 | O(N) | O(1) | Easy | Array | |
| C | Wiki Race | Python3 Python3 | O(N + SUM_M * MAX_LEN_S) | O(N + SUM_M * MAX_LEN_S) | Medium | DFS, Freq Table, Tree DP | |
| D | Tower Rush | Python3 | precompute: O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H))) runtime: O(N + (max_h) * log(max_h)) |
O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H))) | Hard | Number Theory, Bézout's Identity, Combinatorics, Inclusion-Exclusion Principle, Möbius Function, Linear Sieve of Eratosthenes |