Primeira fase da Maratona de Programação 2018

No último fim de semana aconteceu a primeira fase da Maratona de Programação (a fase sub-regional da ACM-ICPC) no Brasil. Essa prova é feita em várias sedes no país e serve como classificatória para a fase nacional, que esse ano acontece em Salvador.

Participaram mais de 700 equipes, e cerca de 70 se classificam para a fase seguinte de acordo com múltiplas regras como a colocação no Brasil e a colocação na sede. Esse ano, participei com a equipe do ITA (CalopsITA) junto com o Lucas França e o Lucas Soares, todos no nosso último ano de participação, e conseguimos o quarto lugar no Brasil!

Melhoramos em relação ao nosso último ano, mas infelizmente ainda tivemos a maior penalidade de tempo dos participantes, utilizado como critério de desempate (empatamos na penalidade com o primeiro colocado que fez um problema a mais). Parece que é um problema recorrente para gente, já que ano passado, na fase nacional, também tivemos a maior penalidade de tempo do Brasil.

A prova foi bem mais difícil que a primeira fase dos últimos anos (no ano anterior, duas equipes fecharam a prova -- inclusive a da USP-SC que ficou em primeiro esse ano!).  A equipe da UFPE também foi excelente, conseguiram uma diferença de 300 minutos na penalidade do tempo para o terceiro colocado! No geral, o desempenho de todas as equipes tornou a competição definitivamente bem competitiva.

Na última hora de prova, tentamos dois problemas: o A e o K. Nos últimos 15 minutos, o Lucas França conseguiu finalizar uma ideia para o problema K, que pedia para calcular as intersecções entre N circuferências que continham o ponto (0,0) ou indicar que era maior que 2N. A ideia dele foi montar uma floresta de círculos, em que cada filhos da árvore está contido dentro do seu pai. O problema é o tempo, mas a ideia parecia ter complexidade proporcional a N + I, onde I é o número de intersecções. Posteriormente, numa discussão do reddit vimos que a ideia tem tempo N sqrt(N), mas como N é no máximo 150000 e a constante multiplicativa é baixa, foi suficiente para receber o balão. No problema A, por outro lado, havia algum erro que não conseguimos achar -- demos sorte na K e azar na A.

A fase nacional deve ser competitiva, e espero que seja tão divertida quanto essa também. Definitivamente estamos ansiosos por ela :)