MetaHackerCup-2023 [](./LICENSE)
September 23, 2024 · View on GitHub
- 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.
Rounds
Practice Round
| # | 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 |
Round 1
| # | 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, Pruning | |
| B2 | Sum 41 (Chapter 2) | Python3 Python3 | O(89166 + K^2) | O(K) | Medium | Backtracking, Unique Partitions, Pruning | |
| 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 |
Round 2
| # | 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_LEN_S) | O(N + SUM_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 |
Round 3
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Spooky Splits | Python3 | O(S * sqrt(N) * logN) | O(S * sqrt(N)) | Easy | BFS, Backtracking, Pruning, Hash Table | |
| B | Hash Slinger | Python3 | O(N^2 + M^2) | O(N * M) | Medium | DP, Dijkstra's Algorithm | |
| C | Krab-otage | Python3 | O(R * C * (R + C)) | O(R * C) | Hard | DP, Prefix Sum | |
| D | Double Stars | Python3 Python3 | O(N) | O(N) | Hard | DFS, BFS, Prefix Sum, Tree DP, Sort, Counting Sort, Freq Table, Two Pointers, Greedy | |
| E | Similar Ships | Python3 Python3 | O(N) | O(N) | Hard | Constructive Algorithms, Tree Diameter, BFS, Tree DP |
Final Round
You can relive the magic of the 2023 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A1 | Programming Paths (Part 1) | Python3 Python3 | precompute: O(R * C) runtime: O(R * C) | O(R * C) | Easy | Constructive Algorithms, BFS, Bitmasks, DFS | |
| A2 | Programming Paths (Part 2) | Python3 Python3 | precompute: O(R * C + K^2 * D) runtime: O(R * C) | O(R * C + K^2) | Hard | Constructive Algorithms, BFS, DP, Backtracing | |
| B | Transposing Tiles | PyPy3 | O(R * C * 3136) | O(R * C + 16) | Easy | Freq Table, DP | |
| C | Resisting Robots | Python3 | O(NlogN + M) | O(N + M) | Easy | Sort, Union Find, DSU, DP | |
| D | Nearly Nim | Python3 | O(N) | O(N) | Medium | Game, Prefix Sum, Greedy | |
| E | Dealing Decks | PyPy3 | O(NlogN) | O(NlogN) | Medium | Game, Sprague-Grundy Theorem, Persistent Trie, Binary Search | |
| F | Cacti Cartography | Python3 Python3 | O(N^2 * min(K, L)) | O(N^2) | Hard | Cactus Graph, BFS, DFS, Tree DP, Linear Programming |