kamyu104 / facebookhackercup-2021

🏃 Python Solutions of All 27 Problems in FHC 2021

FacebookHackerCup-2021

Python solutions of Facebook Hacker Cup 2021. 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.

• Hacker Cup 2020
• Qualification Round
• Round 1
• Round 2
• Round 3
• Final Round
• Hacker Cup 2022

Qualification Round

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A1	Consistency - Chapter 1	Python Python	O(|S|)	O(1)	Easy		Greedy
A2	Consistency - Chapter 2	Python Python	O(|S|)	O(1)	Easy		Floyd-Warshall Algorithm, Dijkstra's Algorithm
B	Xs and Os	Python	O(N^2)	O(1)	Easy		Array
C1	Gold Mine - Chapter 1	Python	O(N)	O(N)	Easy		Tree, DFS
C2	Gold Mine - Chapter 2	Python	O(N * K^2)	O(N * K)	Hard		Tree, DFS, DP

Round 1

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A1	Weak Typing - Chapter 1	Python	O(N)	O(1)	Easy		Array
A2	Weak Typing - Chapter 2	Python Python	O(N)	O(1)	Easy		DP, Math, Counting
A3	Weak Typing - Chapter 3	Python Python	O(N)	O(1)	Medium		DP, Matrix Exponentiation, Math, Counting
B	Traffic Control	Python	O(N * M)	O(1)	Easy		Array, Constructive Algorithms
C	Blockchain	Python	O(N * MAX_C)	O(N * MAX_C)	Hard		Sort, Union Find, Tree, DFS, DP

Round 2

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Runway	Python	O(N * M)	O(M)	Easy		Simulation, Greedy
B	Chainblock	Python Python	O(N)	O(N)	Medium		Tree Traversal, Tree Ancestors (Binary Lifting), Tarjan's Offline LCA Algorithm, Union Find
C1	Valet Parking - Chapter 1	Python	O(R * C)	O(min(R, C))	Medium		Array
C2	Valet Parking - Chapter 2	(PyPy, Python) (PyPy, PyPy) (PyPy, Python) (PyPy, Python)	O((R * C + S) * logR)	O(R * C)	Hard		Array, BIT, Fenwick Tree, Skip List, Sorted List, Heap, Segment Tree
D	String Concatenation	PyPy Python Python	O(N + L*(logN1)^2 + N2^3/6 + X*2^X*(N3-X)/C)	O(N)	Hard		Array, Pigeonhole Principle, Birthday Paradox, Sorted List, BIT, Fenwick Tree, Bitmask

Round 3

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Rep-ore-ting	Python	O(M + N)	O(N)	Easy		Intervals, Union Find, Counting
B	Auth-ore-ization	PyPy	O((M + N) * log(M + N))	O(M + N)	Medium		Sorted List, Segment Tree
C	Perf-ore-mance	Python	O(N * K^2)	O(N * K)	Hard		Tree, DP
D1	Expl-ore-ation - Chapter 1	Python	O((R * C) * log(R * C))	O(R * C)	Easy		Union Find
D2	Expl-ore-ation - Chapter 2	Python	O((R * C + K) * log(R * C + K) + ((R * C) * log(R * C) + K) * logK)	O(R * C + K)	Medium		Union Find, Intervals, Sorted List
D3	Expl-ore-ation - Chapter 3	Python Python	O((R * C + K) * log(R * C)^2)	O(R * C)	Hard		Union Find, Tree Traversal, Tree Ancestors (Binary Lifting), Heavy-Light Decomposition, Sorted List, BIT, Fenwick Tree

Final Round

You can relive the magic of the 2021 Hacker Cup World Finals by watching the Live Stream Recording of the announcement of winners.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	And	Python	O(L * N)	O(L * N)	Medium		Greedy, Union Find
B	SSSSSS	Python	O(NlogN)	O(N)	Hard		Greedy, Line Sweep
C	Hire Flyers	PyPy	O(N * (logN)^2)	O(NlogN)	Hard		Line Sweep, 2D Segment Tree, BIT, Fenwick Tree
D	Vacation	Python	O(NlogN)	O(N)	Medium		Tree, DFS, DP, Greedy
E	Antisocial	*PyPy C++	O(NlogN)	O(N)	Hard		Geometry, Voronoi Diagram (Fortune's Algorithm), Graph, Maximum Spanning Tree (Kruskal's Algorithm)
F	Table Flipping	*PyPy PyPy PyPy	O(NlogN)	O(NlogN)	Hard		2D Line Sweep, 2D Segment Tree, Implicit Segment Tree, Graph, DFS, BFS