Skip to content

kamyu104/GoogleCodeJam-2018

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Python solutions of Google Code Jam 2018. 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).

Qualification Round

# Title Solution Time Space Difficulty Tag Note
A Saving The Universe Again Python O(P) O(P) Easy Greedy
B Trouble Sort Python O(NlogN) O(N) Easy Sort
C Go, Gopher! Python O(P) O(1) Medium Probability, Simulation
D Cubic UFO Python O(1) O(1) Medium Rotation Matrix, Geometry

Round 1A

# Title Solution Time Space Difficulty Tag Note
A Waffle Choppers Python O(R * C) O(R + C) Easy Array, Accumulation Sum
B Bit Party Python O(ClogC * log(max(S)*B+max(P))) O(C) Medium Binary Search
C Edgy Baking Python O(N^2) O(N) Medium Intervals

Round 1B

# Title Solution Time Space Difficulty Tag Note
A Rounding Error Python O(NlogN) O(N) Medium Greedy, Memoization
B Mysterious Road Signs Python O(S) O(1) Medium Graph, Sliding Window
C Transmutation C++ PyPy O(M^3 * logS) O(M^2) Hard Binary Search, Overflow Pruning

Round 1C

# Title Solution Time Space Difficulty Tag Note
A A Whole New Word Python O(T) O(T) Easy Trie
B Lollipop Shop Python O(N^2) O(N) Easy Probability
C Ant Stack C++ PyPy O(N * K) O(K) Medium DP

Round 2

# Title Solution Time Space Difficulty Tag Note
A Falling Balls Python O(C^2) O(C^2) Easy Greedy
B Graceful Chainsaw Jugglers C++ PyPy O(R^(4/3)*B^(4/3)) O(R * B) Medium DP, Memoization
C Costume Change C++ PyPy O(N^2 * sqrt(N)) O(N) Medium Bipartite Matching
D Gridception C++ *PyPy O(2^4 * R^2 * C^2) O(R * C) Medium Graph, DFS

Round 3

# Title Solution Time Space Difficulty Tag Note
A Field Trip Python O(N) O(1) Easy Greedy
B Name-Preserving Network Python Python O(LlogL) O(L) Medium Probability, Topology
C Raise the Roof Python O(N^2) O(N) Hard Geometry, Vector
D Fence Construction Python O(FlogF) O(F) Hard ❤️ Dual Graph, Greedy

World Finals

You can relive the magic of the 2018 Code Jam World Finals by watching the Live Stream Recording of the competition, problem explanations, interviews with Google and Code Jam engineers, and announcement of winners.

# Title Solution Time Space Difficulty Tag Note
A Jurisdiction Restrictions PyPy PyPy O(S^6 * log(R * C)) O(S^2) Medium Dinic's Algorithm, Max-Flow Min-Cut Theorem, Binary Search, Inclusion-Exclusion Principle, Math
B Two-Tiling Python O((1+8+8+65)^(N^2)) O(2^(2 * M^2 - 1) * N^2) Hard ❤️ Backtracking, Bit Manipulation, Union Find, Precompute
C Go, Gophers! Python O(M * (S + (S/W)^2)) O(S) Medium Multiple Binary Searches
D Swordmaster Python O(N * P) O(N * P) Hard ❤️ BFS, DFS, DAG, SCC, Tarjan's Algorithm
E The Cartesian Job Python O(K * N) O(N) Hard ❤️ DP, Intervals, Sort, Vector