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
Round 1
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 |