FacebookHackerCup-2019 [](https://creativecommons.org/licenses/by-nc/3.0/)
November 14, 2020 · View on GitHub
Python solutions of Facebook Hacker Cup 2019. 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 |
|---|---|---|---|---|---|---|---|
| 1 | Leapfrog: Ch. 1 | Python | O(N) | O(1) | Easy | Math | |
| 2 | Leapfrog: Ch. 2 | Python | O(N) | O(1) | Easy | Math | |
| 3 | Mr. X | Python Python | O(E) | O(D) | Medium | String | |
| 4 | Trees as a Service | Python | O(N^2 * (N + M)) | O(N) | Hard | Recursion |
Round 1
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Graphs as a Service | Python | O(N^3) | O(N^2) | Easy | Floyd-Warshall Algorithm | |
| 2 | Class Treasurer | Python | O(N) | O(N) | Easy | Greedy | |
| 3 | Ladders and Snakes | Python | O(N^4) | O(N^2) | Hard | Line Sweep, Dinic's Algorithm, Max-Flow Min-Cut Theorem | |
| 4 | Connect the Dots | Python | O(NlogN) | O(N) | Hard | Heap, Sort |
Round 2
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | On the Run | Python | O(1) | O(1) | Easy | Math | |
| 2 | Bitstrings as a Service | Python | O((M + N) * N) | O(N^2) | Medium | Union Find, DP | |
| 3 | Grading | PyPy | O(S * H^2) | O(H) | Hard | DP, Binary Search | |
| 4 | Seafood | Python | O(NlogN) | O(N) | Hard | Mono Stack, Binary Search, DP |
Round 3
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Light Show | Python | O(N^2) | O(N) | Easy | DP | |
| 2 | Integers as a Service | Python | O(NlogN) | O(1) | Medium | Euclidean Algorithm, GCD, LCM | |
| 3 | Renovations | Python | O(NlogK) | O(N) | Medium | Probability, Euler's Theorem | |
| 4 | Chain of Command | Python | O(N * (logN)^2) | O(N) | Hard | Heavy-Light Decomposition, Stack, Recursion, BIT, Fenwick Tree |
Final Round
You can relive the magic of the 2019 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Strings as a Service | Python Python | O(KlogK) | O(1) | Easy | Greedy | |
| 2 | Khajiit | Python | O(N * M) | O(1) | Easy | Greedy | |
| 3 | Scoreboard | Python | O(N ^2* M) | O(1) | Easy | Set | |
| 4 | Little Boat on the Sea | PyPy | O(NlogN) | O(NlogN) | Medium | Preorder Traversal (Stack), Tree Ancestors (Binary Lifting), Line Sweep, Segment Tree (Lazy Propagation), RMQ | |
| 5 | Cold Storage | PyPy | O(N^2) | O(N^2) | Medium | DP | |
| 6 | Temporal Revision | Python | O((S + N) * logN + (K + M) * α(N)) | O(NlogN) | Hard | Union Find, DP, Preorder Traversal (Stack), Tree Ancestors (Binary Lifting) |