FacebookHackerCup-2020 [](https://creativecommons.org/licenses/by-nc/3.0/)
August 30, 2021 ยท View on GitHub
Python solutions of Facebook Hacker Cup 2020. 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.
Qualification Round
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Travel Restrictions | Python | O(N^2) | O(1) | Easy | Two Pointers | |
| B | Alchemy | Python | O(N) | O(1) | Easy | Math | |
| C | Timber | Python | O(NlogN) | O(N) | Medium | DP | |
| D1 | Running on Fumes - Chapter 1 | Python | O(N) | O(M) | Medium | Mono Deque | |
| D2 | Running on Fumes - Chapter 2 | Python | O(NlogN) | O(N) | Hard | DFS, BFS, Segment Tree |
Round 1
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A1 | Perimetric - Chapter 1 | Python | O(N) | O(N) | Easy | Mono Deque | |
| A2 | Perimetric - Chapter 2 | Python | O(NlogN) | O(N) | Medium | Skip List, Line Sweep | |
| A3 | Perimetric - Chapter 3 | PyPy | O(NlogN) | O(N) | Hard | Skip List, Line Sweep | |
| B | Dislodging Logs | Python | O(NlogN + MlogM + (M + N) * log(max(max(Q)-min(P), max(P)-min(Q)))) | O(N + M) | Easy | Binary Search, Greedy | |
| C | Quarantine | Python | O(N) | O(N) | Hard | Preorder Traversal, Flood Fill, DP |
Round 2
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Ca-pasta-ty | Python | O(N) | O(1) | Easy | Math | |
| B | Elimination | Python | O(N^2) | O(N^2) | Medium | Math, DP | |
| C | Circular Circles | PyPy | O((N * M + E) * (logN + logM)) | O(N) | Medium | Skip List | |
| D | Log Drivin' Hirin' | Python | O(N * (logN)^2 + MlogN) | O(N) | Hard | Skip List, Dynamic Convex Hull Trick |
Round 3
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Chain Explosions | Python | O(K^(1/2)) | O(1) | Easy | Math | |
| B | Railroad Renovations | Python | O(N^3) | O(N * K) | Medium | DP, Math | |
| C | Mail Security | PyPy | O((N + M) * (logN + logM)^2) | O(N + M) | Hard | Binary Search, Skip List, Greedy | |
| D | Smart Carts | PyPy | O(N^3) | O(N) | Hard | Math, Precompute |
Final Round
You can relive the magic of the 2020 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| A | Cryptoconference | Python | O(NlogN) | O(N) | Easy | Skip List, Counting | |
| B | Somebody Else's Problem | Python | O(N) | O(H) | Easy | Tree Traversal, DP | |
| C | Pond Precipitation | Python | O(N^5) | O(N^2) | Medium | DP, Euler's Theorem, Expected Value | |
| D | Spider Spring | *PyPy PyPy PyPy | O((N + M) * logN) | O(N) | Medium | Skip List, Segment Tree, BIT, Fenwick Tree, Counting | |
| E | Tree Training | PyPy | O(N * (logN)^2) | O(N) | Hard | Binary Search, Counting | |
| F | Cake-Cutting Committee | PyPy | O(N^2 * logN) | O(N) | Hard | Geometry, Line Sweep, Segment Tree |