kamyu104 / metahackercup-2022

🏃 Python3 Solutions of All 30 Problems in MHC 2022

MetaHackerCup-2022

• Python3 solutions of Meta Hacker Cup 2022. Solution begins with * means it will get TLE in the largest data set.
• Total computation amount > 10^8, which is not friendly for Python3 to solve in 5 ~ 15 seconds. A 6-minute timer is set for uploading the result this year.
• A problem was marked as Very Hard means that it was an unsolved one during the contest and may not be that difficult.

Rounds

• Hacker Cup 2021
• Qualification Round
• Round 1
• Round 2
• Round 3
• Final Round
• Hacker Cup 2023

Qualification Round

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Second Hands	Python3	O(N)	O(N)	Easy		Greedy
B1	Second Friend	Python3	O(R * C)	O(1)	Easy		Constructive Algorithms
B2	Second Second Friend	Python3	O(R * C)	O(R * C)	Medium		Constructive Algorithms, BFS
C1	Second Meaning	Python3	O(N^2)	O(N)	Easy		Constructive Algorithms
C2	Second Second Meaning	Python3	O(NlogN)	O(logN)	Medium		Constructive Algorithms
D	Second Flight	Python3 Python3	O(N + Q + M * min(sqrt(Q), N))	O(N + M + Q)	Hard		Graph, Memoization

Round 1

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A1	Consecutive Cuts - Chapter 1	Python3	O(N)	O(1)	Easy		Constructive Algorithms, String
A2	Consecutive Cuts - Chapter 2	Python3 Python3 Python3	O(N)	O(1)	Medium		Constructive Algorithms, String, KMP Algorithm, Z-Function, Rabin-Karp Algorithm, Rolling Hash
B1	Watering Well - Chapter 1	Python3	O(N + Q + min(N * Q, MAX_A_B_X_Y^2))	O(min(N + Q, MAX_A_B_X_Y))	Easy		Math, Freq Table
B2	Watering Well - Chapter 2	Python3	O(N + Q)	O(1)	Easy		Math
C	Lemonade Life	PyPy3	O(NlogN + V^2)	O(N + V)	Hard		Geometry, Convex Hull, Monotone Chain Algorithm, Graph, Dijkstra's Algorithm

Round 2

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A1	Perfectly Balanced - Chapter 1	Python3	O(N + Q)	O(N)	Easy		Prefix Sum
A2	Perfectly Balanced - Chapter 2	Python3	O((N + Q) * logN)	O(N)	Medium		Hash, BIT, Fenwick Tree
B	Balance Sheet	Python3	O(NlogN + N * K)	O(N * K)	Medium		Sort, Greedy, DP
C	Balance Scale	Python3	precompute: O(MAX_N * MAX_C) runtime: O(N)	precompute: O(MAX_N * MAX_C) runtime: O(1)	Easy		Combinatorics, Probability
D1	Work-Life Balance - Chapter 1	Python3	O((N + M) * logN)	O(N)	Medium		BIT, Fenwick Tree, Greedy
D2	Work-Life Balance - Chapter 2	Python3	O((N + M) * logN)	O(N)	Hard		BIT, Fenwick Tree, Greedy

Round 3

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Fourth Player	Python3	O(NlogN)	O(N)	Medium		Games, Greedy
B	Third Trie	Python3	O(N * M)	O(T)	Easy		Trie, Combinatorics
C	Second Mistake	Python3	O(3 * L * (N + Q))	O(3 * L * N)	Easy		Rabin-Karp Algorithm, Hash Table
D1	First Time - Chapter 1	Python3	O(M + NlogN)	O(N)	Medium		Unordered Set
D2	First Time - Chapter 2	Python3	O(M + NlogN)	O(N)	Hard		Unordered Set, Segment Tree, Number Theory
E1	Zero Crossings - Chapter 1	Python3 Python3	O((N * M + Q) * log(N * M + Q))	O(N * M + Q)	Hard		Offline Solution, Geometry, Sort, Line Sweep, Treap, Sorted List, Binary Search, Tree, DFS, Hash
E2	Zero Crossings - Chapter 2	PyPy3	O((N * M) * log(N * M) + Q * log(N * M))	O((N * M) * log(N * M)	Hard		Online Solution, Geometry, Sort, Line Sweep, Persistent Treap, Binary Search, Tree, DFS, Hash

Final Round

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

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	ML Modeling	PyPy3	O(MAX_X * MAX_Y * MAX_R * MIN_N + (MAX_X * MAX_Y)^2 + N)	O(MAX_X * MAX_Y)	Medium		Geometry, Sampling
B	Emerald Exhibiting	PyPy3	O(P * logN)	O(MAX_N)	Medium		Combinatorics, Number Theory
C	Tile Transposing	PyPy3 PyPy3	O(M * N * log(M * N))	O(M * N)	Hard		DFS, Persistent Union Find
D	Alphabet Adventuring	Python3	O((R^2 + log(N + Q)) * (N + Q) + Q * (R^2 + log(N + Q))* log(N + Q))	O((R^2 + log(N + Q)) * (N + Q))	Hard		Tree Traversal, Tree Ancestors (Binary Lifting), Heavy-Light Decomposition, Path Compression
E	Hazelnut Harvesting	Python3	O(NlogN)	O(NlogN)	Hard		Coordinate Compression, Segment Tree, Line Sweep, Mono Stack
F	Cup Counterbalancing	PyPy3	O(N * S)	O(N)	Very Hard		Geometry, Sampling

metahackercup-2022's Issues

lemonade_life_input

I think you are losing some performance here using (a-b)**2 rather than writing (a-b)*(a-b)

https://github.com/kamyu104/MetaHackerCup-2022/blob/main/Round%201/lemonade_life.py3#L53

Also, I'm curious, what was your runtime on your local computer? I ran your code in pypy and it finished in 6 minutes and 30 seconds.