FacebookHackerCup-2018 [](https://creativecommons.org/licenses/by-nc/3.0/)
February 11, 2020 ยท View on GitHub
Python solutions of Facebook Hacker Cup 2018. 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 | Tourist | Python | O(K) | O(1) | Easy | Math | |
| 2 | Interception | Python | O(1) | O(1) | Easy | Math | |
| 3 | Ethan Searches for a String | Python | O(N) | O(1) | Easy | String |
Round 1
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Let It Flow | Python | O(N) | O(W) | Easy | DP | |
| 2 | Ethan Traverses a Tree | Python | O(N) | O(N) | Easy | Graph | |
| 3 | Platform Parkour | Python | O(N * (M + logZ)) | O(N) | Medium | Intervals | |
| 4 | Evening of the Living Dead | Python | O(N * M) | O(N) | Hard | DP, Probability |
Round 2
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Ethan Finds the Shortest Path | Python | O(N) | O(1) | Easy | Graph, Greedy | |
| 2 | Jack's Candy Shop | Python | O(N * (logN)^2) | O(N) | Medium | Greedy, Heap, Stack, Recursion | |
| 3 | Replay Value | PyPy | O(N^5) | O(N^4) | Hard | DP | |
| 4 | Fossil Fuels | PyPy | O(NlogN) | O(N) | Hard | DP, Mono Deque, Segment Tree, RMQ |
Round 3
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Jammin' | Python | O(N) | O(1) | Easy | Simulation | |
| 2 | Ethan Finds the Maximum Subarray Sum | Python | O(M^2 * K) | O(1) | Medium | Greedy | |
| 3 | Graph Gift | PyPy | O(N^2) | O(N) | Medium | Greedy | |
| 4 | Finshakes | Python | O(M^3) | O(M^2) | Hard | DP |
Final Round
You can relive the magic of the 2018 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.
| # | Title | Solution | Time | Space | Difficulty | Tag | Note |
|---|---|---|---|---|---|---|---|
| 1 | Contest Environment | Python | O(N) | O(1) | Easy | Math | |
| 2 | Stockholm | Python | O(logA + logB) | O(logA + logB) | Easy | Binary Tree, Bit Manipulation, Greedy | |
| 3 | Ethan Sums Shortest Distances | Python Python Python Python | O(N^3) | O(N^2) | Easy | Prefix Sum, DP | |
| 4 | Personal Space | PyPy | O(NlogN) | O(N) | Medium | Skip List, Line Sweep, DP | |
| 5 | City Lights | PyPy PyPy | O(S^2 * W^2) | O(S * W * min(S, W)) | Hard | Skip List, Binary Search, Recursion, Prefix Sum, DP | |
| 6 | The Claw | Python | O(NlogN) | O(N) | Medium | Mono Stack, Binary Search, Segment Tree, DP |