kamyu104 / googlecodejam-2022

🏃 Python3 Solutions of All 27 Problems in GCJ 2022

GoogleCodeJam 2022

• Python3 solutions of Google Code Jam 2022. Solution begins with * means it will get TLE in the largest data set.
• Total computation amount > 10^8 is not friendly for Python3 to solve in 5 ~ 15 seconds.
• A problem was marked as Very Hard means that it was an unsolved one during the contest and may not be that difficult.

Rounds

• Code Jam 2021
• Qualification Round
• Round 1A
• Round 1B
• Round 1C
• Round 2
• Round 3
• Virtual World Finals
• Code Jam Farewell Rounds

Qualification Round

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Punched Cards	Python3	O(R * C)	O(1)	Easy		Array
B	3D Printing	Python3	O(1)	O(1)	Easy		Math
C	d1000000	PyPy3 Python3	O(NlogN)	O(1)	Easy		Sort
D	Chain Reactions	Python3 Python3	O(N)	O(N)	Medium		Topological Sort, Greedy
E	Twisty Little Passages	Python3 Python3	O(min(K, N))	O(min(K, N))	Hard		Probability, Importance Sampling

Round 1A

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Double or One Thing	Python3	O(|S|)	O(1)	Easy		String
B	Equal Sum	Python3 Python3	O(N)	O(1)	Medium		Math, Constructive Algorithms
C	Weightlifting	Python3	O(E^2 * W + E^3)	O(E^2 + W)	Hard		DP

Round 1B

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Pancake Deque	Python3	O(N)	O(1)	Easy		Greedy
B	Controlled Inflation	Python3	O(N * P)	O(1)	Medium		DP
C	ASeDatAb	Python3 Python3 Python3	O(L * 2^L)	O(L)	Hard		Precompute, BFS, Topological Sort, Constructive Algorithms

Round 1C

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Letter Blocks	Python3	O(N * L)	O(N)	Easy		String
B	Squary	Python3	O(N)	O(1)	Medium		Math, Constructive Algorithms
C	Intranets	Python3 Python3	precompute: O(MAX_M) runtime: O(1)	O(MAX_M)	Hard		Inclusion‐Exclusion Principle, Combinatorics, Catalan Number

Round 2

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Spiraling Into Control	Python3	O(N)	O(1)	Easy		Constructive Algorithms, Greedy, Math
B	Pixelated Circle	Python3	O(R)	O(1)	Medium		Math
C	Saving the Jelly	PyPy3	O(N^2 * sqrt(N))	O(N^2)	Medium		Bipartite Matching, Hopcroft-Karp Algorithm
D	I, O Bot	Python3	O(NlogN)	O(N)	Hard		DP, Prefix Sum, Hash Table

Round 3

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Revenge of GoroSort	Python3	O(C * N)	O(N)	Easy		Math, Expected Value, Trial and Error
B	Duck, Duck, Geese	PyPy3 C++	O(NlogN)	O(N)	Medium		Segment Tree
C	Mascot Maze	Python3	O(N)	O(N)	Medium		Topological Sort, Greedy
D	Win As Second	Python3 Python3 Python3 PyPy3	precompute: O(N^5) on average runtime: O(N^3 + M * N^2)	O(N^2)	Hard		Bitmasks, Submask Enumeration, Sprague-Grundy Theorem, BFS, Constructive Algorithms, Precompute, Trial and Error

Virtual World Finals

You can relive the magic of the 2022 Code Jam Virtual World Finals by watching the Live Stream Recording of the competition, problem explanations, and announcement of winners.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Wonderland Chase	Python3	O(J + C)	O(J + C)	Easy		Graph, BFS
B	Goose, Goose, Ducks?	*PyPy3 C++	O(N + M + S * (logM + logS))	O(N + S)	Hard		Logic-Based, Sorted List, Graph, BFS, SCC, Tarjan's Algorithm
C	Slide Parade	PyPy3	O(B * S + S^2)	O(B * S)	Medium		BFS, Constructive Algorithms, Bipartite Matching, Hungarian Algorithm, Eulerian Path, Hierholzer's Algorithm
D	Schrödinger and Pavlov	PyPy3	O(N)	O(N)	Hard	❤️	Graph, Probability, DP
E	Triangles	PyPy3 C++	O(N^2)	O(N)	Very Hard	❤️	Geometry, Constructive Algorithms, Greedy