GoogleCodeJam Farewell Rounds

• Python solutions of Google Code Jam Farewell Rounds. Solution begins with * means it will get TLE in the largest data set.
• Total computation amount > 10^8 is not friendly for Python 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

• Kick Start 2022
• Code Jam to I/O for Women 2022
• Code Jam 2022
• Round A
• Round B
• Round C
• Round D

Round A

• Round A is appropriate for beginners.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Colliding Encoding	Python3	O(N)	O(N)	Easy		Hash Table
B	Illumination Optimization	Python3	O(N)	O(1)	Medium		Greedy
C	Rainbow Sort	Python3	O(N)	O(N)	Easy		Hash Table
D	ASCII Art	Python3	O(1)	O(1)	Easy		Math
E	Untie	Python3	O(N)	O(1)	Medium		Greedy

Round B

• Round B is about the level of a Kick Start round or a Code Jam Round 1.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Collecting Pancakes	Python3	O(N)	O(1)	Medium		Greedy, Prefix Sum
B	Intruder Outsmarting	Python3	O(W * log(min(D, N)))	O(1)	Medium		Extended Euclidean Algorithm
C	Spacious Sets	Python3	O(NlogN)	O(N)	Easy		Binary Search, DP
D	Railroad Maintenance	PyPy3	O(N + L)	O(N + L)	Hard		DFS, Biconnected Components, Articulation Points
E	Railroad Management	Python3	O(N)	O(N)	Hard		Graph, Cycle

Round C

• Round C is harder than a Code Jam Round 2 but easier than a Code Jam Round 3.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Game Sort: Part 1	Python3	O(P * L)	O(1)	Easy		Greedy, Counting Sort, Freq Table
B	Immunization Operation	Python3	O(M + VlogV)	O(V)	Easy		Simulation, Heap
C	Evolutionary Algorithms	PyPy3	O(NlogN)	O(N)	Medium		DFS, BIT, Fenwick Tree, Coordinate Compression, Combinatorics
D	The Decades of Coding Competitions	PyPy3	O(K * (N + M + Q))	O(K * N)	Medium		Graph, Union Find, DSU
E	Game Sort: Part 2	Python3	O(N)	O(1)	Hard	❤️	Constructive Algorithms, Prefix Sum, Freq Table, Greedy

Round D

• Round D is meant for experienced competitors. It is between a Code Jam Round 3 and Finals difficulty.

#	Title	Solution	Time	Space	Difficulty	Tag	Note
A	Indispensable Overpass	Python3	O(W + E + C)	O(W + E)	Easy		Tree DP, Combinatorics
B	Genetic Sequences	PyPy3 PyPy3	O((N + M) * log(N + M) + Q * log(min(N, M)) * logN)	O((N + M) * log(N + M))	Medium		Suffix Array, LCP Array, Binary Search, RMQ, Sparse Table, Persistent BST, Persistent Treap
C	Hey Google, Drive!	PyPy3	O((R * C)^2 * F)	O(R * C)	Hard	❤️	Graph, BFS
D	Old Gold	PyPy3	O(NlogN)	O(N)	Hard	❤️	Combinatorics, DP, Prefix Sum
E	Ring-Preserving Networks	Python3	O(L)	O(L)	Medium		Graph, Constructive Algorithms, Clique, Greedy