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
Round 1
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) |
FacebookHackerCup-2019 copied to clipboard
kamyu104
kamyu104