ICPC Latin American Regionals and Brazil Subregionals Solutions

Solutions of previous ACM-ICPC Latin American Regional Contests and ACM-ICPC Brazil Subregional Contests (a.k.a. Maratona de Programação).

2018 ICPC Latin American Regional

ID	Problem	Contents
A	A Symmetrical Pizza	Basic math
B	Building a Field	Two pointers
C	Cheap Trips	Dyamic Programming
D	Database of Clients	Ad-hoc
E	Escape, Polygon!	Two pointers + Geometry
F	Fantastic Beasts	Chinese Remainder Theorem + Big Integer
G	Gathering Red-Black Fruits	Combinatorics
H	Highway Decommission	Dijkstra Algorithm
I	Ink Colors	Graph traversal + Greedy
J	Jeopardized Election	Ad-hoc
K	KryptoLocker Ate my Homework	Backtracking
L	Looking for the Risk Factor	Sieve of Eratosthenes + Fenwick Tree
M	Mount Marathon	Ad-hoc

2018 ICPC Brazil Subregional

ID	Problem	Contents
A	Aventurando-se no Slackline	Möbius inversion
B	Bolinhas de Gude	Nim, Sprague-Grundy Theorem
C	Cortador de Pizza	Fenwick Tree
D	Desvendando Monty Hall	Ad-hoc
E	Enigma	Ad-hoc
F	Festival	Dynamic Programming
G	Gasolina	Maximum Flow
H	Hipótese Policial	Heavy-Light Decomposition + Segment Tree + KMP
I	Interruptores	Ad-hoc
J	Juntando Capitais	Steiner Tree Problem
K	Kepler	Basic geometry + Graph traversal
L	Linhas de Metrô	Lowest Common Ancestor
M	Modificando SAT	Gaussian Elimination modulo 2

2017 ICPC Latin American Regional

ID	Problem	Contents
A	Arranging tiles	Minkowski Sum + Travelling Salesman Problem
B	Buggy ICPC	Ad-hoc
C	Complete Naebbirac’s sequence	Ad-hoc
D	Daunting device	Basic data structures
E	Enigma	Dynamic Programming with solution recovery
F	Fundraising	Fenwick Tree
G	Gates of uncertainty	Dynamic Programming
H	Hard choice	Ad-hoc
I	Imperial roads	Minimum Spanning Tree + Lowest Common Ancestor
J	Jumping Frog	Basic number theory
K	Keep it covered	Maximum Bipartite Matching
L	Linearville	Greedy
M	Marblecoin	Suffix Array

2017 ICPC Brazil Subregional

ID	Problem	Contents
A	Acordes intergaláticos	Segment Tree + Lazy Propagation
B	Brincadeira	Ad-hoc
C	Cigarras periódicas	Basic number theory
D	Despojados	Basic number theory
E	Escala musical	Ad-hoc
F	Fase	Ad-hoc
G	Ginástica	Dynamic Programming
H	Hipercampo	Dynamic Programming + Basic geometry
I	Imposto real	Graphs
J	Jogo de Boca	Ad-hoc
K	K-ésimo	Math + Fast matrix exponentiation
L	Laboratório de biotecnologia	Fast Fourier Transform
M	Máquina de café	Ad-hoc

2016 ICPC Latin American Regional

ID	Problem	Contents
A	Assigning Teams	Ad-hoc
B	Back to the Future	Graphs
C	Counting Self-Rotating Subsets	Combinatorics
D	Dating On-Line	Greedy + Basic geometry
E	Emission Spectrum	Persistent Segment Tree
F	Farm Robot	Ad-hoc
G	Game of Matchings	KMP algorithm
H	Hotel Rewards	Basic data structures
I	Internet Trouble	Dynamic Programming using Knuth Optimization
J	Just in Time	Basic number theory
K	Kill the Werewolf	Maximum Flow

2016 ICPC Brazil Subregional

ID	Problem	Contents
A	Andando no tempo	Ad-hoc
B	Batata quente	Persistent Segment Tree
C	Containers	Dijkstra Algorithm
D	Divisores	Basic math
E	Estatística hexa	Dynamic Programming
F	Fundindo árvores	Graphs
G	Go-	Dynamic Programming
H	huaauhahhuahau	Ad-hoc
I	Isósceles	Ad-hoc
J	Jogos olímpicos	Convex hull trick
K	Kit de encolhimento de polígonos	Geometry + Dynamic Programming
L	Ladrilhos	Flood fill

2015 ICPC Latin American Regional

ID	Problem	Contents
A	At most twice	Ad-hoc
B	Blood groups	Maximum Flow
C	Cake cut	Two pointers + Geometry
D	D as in Daedalus	Ad-hoc
E	Exposing Corruption	Graph traversal + Dynamic Programming
F	Fence the vegetables fail	Sweep line + Fenwick Tree
G	Galaxy taxes	Ternary Search + Dijkstra Algorithm
H	Height map	Ad-hoc
I	Identifying tea	Ad-hoc
J	Just a bit sorted	Combinatorics
K	Keep it energized	Dynamic Programming + Fenwick Tree

2015 ICPC Brazil Subregional

ID	Problem	Contents
A	Mania de par	Dijkstra Algorithm
B	Bolsa de Valores	Greedy
C	Tri-du	Ad-hoc
D	Quebra-cabeça	Constructive
E	Espiral	Binary search
F	Fatorial	Basic math
G	Guardiões Curiosos	Dynamic Programming
H	Praça do Retângulo	Basic geometry
I	Ominobox	Two pointers + bitmask
J	Jogo de Estratégia	Ad-hoc
K	Palíndromo	Dynamic Programming
L	Loteria	Linear independence modulo 2