View Code? Open in Web Editor
NEW
๐ ๐ Python3 Solutions of All 20 Problems in GCJ Farewell Rounds
License: MIT License
googlecodejam-farewell-rounds's Introduction
- 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.
- Round A is appropriate for beginners.
- Round B is about the level of a Kick Start round or a Code Jam Round 1.
- 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 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 |
googlecodejam-farewell-rounds's People
Contributors
Watchers