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 | 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 + N23/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 |