Maratona O Poderoso Balão - Behind the Scenes

No dia 07 de junho de 2025, o BRUTE organizou a Maratona O Poderoso Balão, na UDESC. Contarei neste artigo um pouco sobre cada etapa do preparo da competição, desde a idealização e criação até a realização. O contest está disponível no Codeforces e é recomendável fazer o contest antes de ler sobre ele, pois o texto contém leves spoilers.

Idealização

Todo ano (e às vezes duas vezes ao ano!), ocorre uma competição de programação na UDESC chamada Maratona Interna. Esse contest é preparado com carinho especialmente para estudantes da região de Joinville, mas também sempre é aberto para participações externas. Nesta edição, contamos com a participação de 16 times presencialmente e 44 times online, de forma remota. Foi a maior Interna "externa" que já tivemos.

O evento presencial contou com patrocínio da empresa Becomex, apoiadora frequente dos eventos e das viagens do BRUTE, para o coffee break :)

Elaboração dos problemas

A prova foi settada por mim (Eric Grochowicz), Eduardo Schwarz Moreira, Enzo de Almeida Rodrigues e João Marcos de Oliveira. Todas as questões tinham temática de filmes, tema decidido por nós como forma de deixar a prova mais coesa e divertida para quem lê.

O jeito que costumamos elaborar problemas é meio informal a princípio: temos uma página no Notion compartilhada entre nós onde listamos várias ideias de problemas, separadas por dificuldade. Frequentemente, nos reunimos para fazer brainstorming de ideias de problemas e validação das ideias que temos.

Quando temos uma quantidade que julgamos boa de problemas de cada dificuldade, criamos cada problema no Polygon. Já usamos o Box uma vez, mas as ferramentas do Polygon nos servem muito bem, apesar da plataforma ser um pouco lenta.

Algumas curiosidades sobre os problemas:

• O problema Absolute Cinema foi o primeiro a ser criado e settado especialmente para a prova;
• Os problemas Biblioteca Mágica e Las Tortuguitas não haviam sido selecionados para a Interna 2024 e pudemos aproveitá-los agora;
• O problema John Wick surgiu da necessidade de um problema fácil de implementação para servir de passo intermediário entre os problemas "de graça" e os médio-fáceis;
• O problema Ni era originalmente chamado "Tung Tung Tung Sahur'', e o input seria a quantidade de "Tung"s antes de "Sahur''.
• O problema Clichês surgiu da necessidade de um problema muito difícil de strings, e escrevemos a solução primeiro e a história em torno da mesma.

Problemas descartados

Originalmente, havia um problema sobre máximo divisor comum do qual uma versão mais difícil caiu na Fase Zero, que ocorreu duas semanas antes da Interna. Assim, tivemos tempo de trocar o problema por outro no mesmo nível de dificuldade.

Também, um problema que na prática era igual ao problema Dentro da Matriz caiu em um AtCoder Beginner Contest uma semana antes da Interna. Só ficamos sabendo na mesma semana durante a fase de testes e não tivemos tempo de substituir o problema. Pensando especialmente nos fins educativos da Interna para os estudantes da UDESC, optamos por deixar a questão na prova pois sabíamos que eles não tinham feito o contest. Por outro lado, aceitamos o risco de times de fora terem feito o contest.

Resultado dos testes

A prova foi testada pelos nossos colegas Fernando Kiotheka, João Ayalla, Mateus Cosenza, Pedro da Silva, Thiago Trannin e Vinícius Silva.

Os testes nos permitiram ver algumas soluções alternativas e, principalmente, a perspectiva de um competidor quando lê o enunciado. Muitas vezes, nós setters estamos tão acostumados a saber a solução a partir do problema mais abstraído que pensamos originalmente.

Um ponto interessante que observamos durante os testes foi recebermos várias tentativas de soluções gulosas no problema Kill Bill Vol. 1 que, felizmente, não passaram, e pudemos ter uma boa garantia de que os casos de teste estavam fortes.

Um problema que teve uma solução errada aceita durante os testes foi o Absolute Cinema. A solução modelo não tinha pior caso dependendo dos valores do vetor, então eles eram gerados aleatoriamente. Porém, uma solução que deveria ter excedido o tempo limite no caso 1, 2, 3, ..., N passou e criamos casos novos para que isso não ocorresse durante a prova.

Também com os testes, pudemos conferir erros de digitação ou partes que não estavam claras nos enunciados. Por exemplo, pudemos perceber que o enunciado original do problema Hierarquia Cinematográfica não fazia sentido nenhum e a direção das arestas não estava clara. Obrigado, testers!

O evento - Maratona Interna

Contamos com 15 times presentes no evento, 13 destes da UDESC Joinville e 2 da UFSC Joinville. Tivemos um pouco menos participantes do que o esperado com base nas edições passadas, o que atribuímos à divulgação do contest ocorrer mais de última hora do que o normal.

Durante a competição, entregamos vários balões, respondemos a alguns clarifications, mandamos vários arquivos para imprimir e escrevemos algumas das soluções que faltavam para os slides no final da prova. Apenas nos últimos 20 minutos de prova é que recebemos um clarification sobre um exemplo não condizer com o texto, algo que passou batido nos testes e não vimos até os últimos 5 minutos. Foi muito satisfatório acompanhar o placar durante tudo isso.

O placar antes do freeze estava desfavorável para a UDESC: o primeiro time da UFSC estava com 10 balões e o da UDESC, com 9. Para a UDESC não perder em casa, seria preciso resolver 2 problemas durante o freeze, pois ainda perderiam por penalidade se fizessem um só.

Ao revelar o placar, o primeiro time da UDESC tinha uma submissão no problema L e outras duas no problema O. Eles passaram os dois problemas.

Com isso, o time da UDESC Como Importar o Seu João foi o campeão da Maratona O Poderoso Balão. Em segundo lugar, ficou o time da UFSC Truque de (Candidato a) Mestre e, em terceiro, o time da UDESC Titãs da Trombudo.

O evento - Maratona Externa

Com 44 times remotos, essa foi a maior Interna "externa'' que já tivemos. Foi também a primeira vez que algum time de fora do Brasil fez a nossa Interna, com 4 times do Peru participando.

A universidade (sem contar a UDESC) que teve mais inscrições foi a UFU, com 7 times inscritos. Aqui está um mapa de calor mostrando participação por estado brasileiro (eu fiz esse mapa assim):

É muito recompensador termos tanta participação no contest que preparamos.
O vencedor global da maratona O Poderoso Balão foi o time Peter Pão de Queijo, da UFU. Em segundo lugar, ficou o time Gunter123FanClub da UNSA. Em terceiro, o time Los tralalelitos dizem FLAMENGOOOOO!!!, da UnB.

Considerações finais

Somos muito gratos a todo mundo que participou da prova, seja presencialmente ou online. Somos gratos a quem ajudou a entregar balões presencialmente. Somos gratos a quem testou a prova. Somos gratos pelo patrocínio. Logo mais vem a próxima Maratona Interna.