Python solutions of Facebook Hacker Cup 2021. Solution begins with * means it will get TLE in the largest data set (total computation amount > 10^8, which is not friendly for Python to solve in 5 ~ 15 seconds). A 6-minute timer is set for uploading the result this year.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A1 | Consistency - Chapter 1 | Python Python | O(|S|) | O(1) | Easy | Greedy | |
| A2 | Consistency - Chapter 2 | Python Python | O(|S|) | O(1) | Easy | Floyd-Warshall Algorithm, Dijkstra's Algorithm | |
| B | Xs and Os | Python | O(N^2) | O(1) | Easy | Array | |
| C1 | Gold Mine - Chapter 1 | Python | O(N) | O(N) | Easy | Tree, DFS | |
| C2 | Gold Mine - Chapter 2 | Python | O(N * K^2) | O(N * K) | Hard | Tree, DFS, DP |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A1 | Weak Typing - Chapter 1 | Python | O(N) | O(1) | Easy | Array | |
| A2 | Weak Typing - Chapter 2 | Python Python | O(N) | O(1) | Easy | DP, Math, Counting | |
| A3 | Weak Typing - Chapter 3 | Python Python | O(N) | O(1) | Medium | DP, Matrix Exponentiation, Math, Counting | |
| B | Traffic Control | Python | O(N * M) | O(1) | Easy | Array, Constructive Algorithms | |
| C | Blockchain | Python | O(N * MAX_C) | O(N * MAX_C) | Hard | Sort, Union Find, Tree, DFS, DP |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Runway | Python | O(N * M) | O(M) | Easy | Simulation, Greedy | |
| B | Chainblock | Python Python | O(N) | O(N) | Medium | Tree Traversal, Tree Ancestors (Binary Lifting), Tarjan's Offline LCA Algorithm, Union Find | |
| C1 | Valet Parking - Chapter 1 | Python | O(R * C) | O(min(R, C)) | Medium | Array | |
| C2 | Valet Parking - Chapter 2 | (PyPy, Python) (PyPy, PyPy) (PyPy, Python) (PyPy, Python) | O((R * C + S) * logR) | O(R * C) | Hard | Array, BIT, Fenwick Tree, Skip List, Sorted List, Heap, Segment Tree | |
| D | String Concatenation | PyPy Python Python | O(N + L*(logN1)^2 + N2^3/6 + X*2^X*(N3-X)/C) | O(N) | Hard | Array, Pigeonhole Principle, Birthday Paradox, Sorted List, BIT, Fenwick Tree, Bitmask |
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Rep-ore-ting | Python | O(M + N) | O(N) | Easy | Intervals, Union Find, Counting | |
| B | Auth-ore-ization | PyPy | O((M + N) * log(M + N)) | O(M + N) | Medium | Sorted List, Segment Tree | |
| C | Perf-ore-mance | Python | O(N * K^2) | O(N * K) | Hard | Tree, DP | |
| D1 | Expl-ore-ation - Chapter 1 | Python | O((R * C) * log(R * C)) | O(R * C) | Easy | Union Find | |
| D2 | Expl-ore-ation - Chapter 2 | Python | O((R * C + K) * log(R * C + K) + ((R * C) * log(R * C) + K) * logK) | O(R * C + K) | Medium | Union Find, Intervals, Sorted List | |
| D3 | Expl-ore-ation - Chapter 3 | Python Python | O((R * C + K) * log(R * C)^2) | O(R * C) | Hard | Union Find, Tree Traversal, Tree Ancestors (Binary Lifting), Heavy-Light Decomposition, Sorted List, BIT, Fenwick Tree |
You can relive the magic of the 2021 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | And | Python | O(L * N) | O(L * N) | Medium | Greedy, Union Find | |
| B | SSSSSS | Python | O(NlogN) | O(N) | Hard | Greedy, Line Sweep | |
| C | Hire Flyers | PyPy | O(N * (logN)^2) | O(NlogN) | Hard | Line Sweep, 2D Segment Tree, BIT, Fenwick Tree | |
| D | Vacation | Python | O(NlogN) | O(N) | Medium | Tree, DFS, DP, Greedy | |
| E | Antisocial | *PyPy C++ | O(NlogN) | O(N) | Hard | Geometry, Voronoi Diagram (Fortune's Algorithm), Graph, Maximum Spanning Tree (Kruskal's Algorithm) | |
| F | Table Flipping | *PyPy PyPy PyPy | O(NlogN) | O(NlogN) | Hard | 2D Line Sweep, 2D Segment Tree, Implicit Segment Tree, Graph, DFS, BFS |