Skip to content

🏁 πŸƒ Python3 Solutions of All 20 Problems in GCJ Farewell Rounds

License

Notifications You must be signed in to change notification settings

kamyu104/GoogleCodeJam-Farewell-Rounds

Folders and files

NameName
Last commit message
Last commit date

Latest commit

Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 

Repository files navigation

Language License Progress Visitors

  • 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

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