Universidade-Livre/rinha-de-algoritmos

Você está prestes a entrar na Rinha de Algoritmos, uma competição incrível que desafia você a mostrar o seu talento no mundo dos algoritmos e estruturas de dados. Nesta aventura, você vai enfrentar problemas reais que exigem soluções criativas e eficientes. Você vai se surpreender com casos curiosos, onde a sua habilidade em resolver desafios computacionais fará toda a diferença. Prepare-se para se divertir em um ambiente estimulante, onde o seu domínio algorítmico será testado. Venha para a Rinha de Algoritmos e embarque nessa jornada desafiadora!

O que é?

A rinha de algoritmos é uma competição amistosa baseada em competições similares, como a Rinha de Compiladores, Rinha de Frontend, e Rinha de Backend. O projeto possui como objetivo avaliar a capacidade dos participantes no design de algoritmos e estruturas de dados para resolver problemas práticos.

Para avaliar os participantes, a descrição de algum caso prático será proposta. Caberá aos participantes identificar o problema e propor a melhor solução para resolvê-lo. Seguindo o mesmo modelo de maratonas de programação, serão fornecidas uma lista de entradas e de resultados esperados, em formato de texto, que poderão ser utilizados para guiar a criação do algoritmo. A pontuação e o ranking correspondente serão baseados em instâncias privadas que serão liberadas apenas ao final da competição.

Cada participante deverá entregar um algoritmo, sinalizando para qual problema aquele algoritmo foi criado, podendo utilizar apenas 2 unidades de CPU e 2GB de memória. Para mais detalhes sobre as submissões, veja como submeter um algoritmo.

Caso hajam dúvidas, por favor abram uma issue ou utilizem o nosso servidor do Discord!

Regras

• Embora estaremos sempre incentivando a conversa e colaboração entre os participantes em prol do estabelecimento de um ambiente de aprendizado, não será permitido compartilhar as soluções nos canais de comunicação da UBL¹;

• Para essa competição é importante ressaltar que não é permitido o uso de solvers².

• Caso sejam utilizados algoritmos de Monte Carlo³, o valor de solução a ser considerado será o melhor dentre $40$ iterações do algoritmo, ou o valor mais próximo possível dessa quantidade de iterações, a depender do tempo necessário para uma solução ser computada.

¹: Note que isso não proibe tirar dúvidas de outros participantes ou fornecer direções. Não esperamos que cada candidato submeta uma solução única, até mesmo porque uma implementação inteligente pode fazer a diferença entre ambas as submissões.

²: Um solver é um programa de computador que, quando aplicado a um problema, é capaz de encontrar a solução automaticamente, sem intervenção direta ou ajuste significativo por parte do usuário. Geralmente, o objetivo de um solver é encontrar a melhor solução ou uma solução aproximada para o problema, tornando-o um mecanismo automatizado de resolução. Na Rinha de Algoritmos, seu uso é proibido. A justificativa é incentivar a resolução manual e criativa dos problemas.

³: Aos participantes interessados em aprender mais sobre algoritmos probabilisticos, vejam os livros recomendados para a Rinha e a página na Wikipedia.

Pontuação

Uma função $f: \mathbb{R}^2 \rightarrow \mathbb{R}$ determinará a pontuação dos participantes. Antes de descrevê-la, denotaremos por $\mathbf{x} = [x_1 ; x_2]^T$ o vetor de saída do algoritmo, onde $x_1$ é o tempo, em segundos, para obtenção da solução, e $x_2$ é o valor da solução viável¹ encontrada.

A pontuação é dada por $f(\mathbf{x}) = \min(100, ; C_{1} / x_{1}) + \min(100, ; C_{2} / |x^{\star} - x_{2}|)$, onde $x^{\star}$ é o valor da solução ótima. As constantes $C_1$ e $C_2$ serão definidas para cada problema, e servem para penalizar o tempo de execução e o quão distante a solução viável está do ótimo, respectivamente.

Vale ressaltar que quanto maior for o valor de $f(\mathbf{x})$, melhor será a pontuação.

¹: Uma solução viável é toda solução que satisfazem as restrições do problema, embora talvez não seja a solução ótima.

Problemas

Problema 01: Lucro de Plantação no Stardew Valley

Descrição: Na busca por otimizar seus ganhos enquanto joga Stardew Valley, você analisa as opções de sementes disponíveis em determinado momento e registra a quantidade de espaços disponíveis para o plantio.

Por ser um fazendeiro organizado, você já tem conhecimento sobre a quantia de moedas que pode obter ao plantar cada tipo de semente durante um período específico, bem como a quantidade de espaços necessários para cada uma delas. Seu objetivo é, portanto, maximizar seu lucro ao plantar o maior número possível de sementes, levando em consideração a capacidade de plantio disponível, ao final do período escolhido. Para fins de simplicidade, assumiremos que todas as sementes possuem o mesmo tempo de plantio e maturação.

Para este problema, definiremos $C_{1} = 1$, $C_{2} = 0.2$, e uma pontuação bônus por cada instância resolvida de $C_{3} = 50$.

Confira os detalhes em como participar.

Problema 02: Age of Empires - A Grande Fronteira

Descrição: Na vastidão estratégica do Age of Empires, o participante ousa enfrentar o desafio supremo denominado "A Grande Fronteira". Neste épico, os líderes imperiais, incluindo você, são convocados a traçar uma trama intrincada de postos avançados não apenas para expandir os domínios do império, mas para construir uma defesa intransponível contra os astutos adversários.

Esses postos avançados, transcendendo meras construções, tornam-se os pilares cruciais na busca pela supremacia. A singularidade deste desafio coloca você na posição de escolher sabiamente os locais estratégicos, onde os postos avançados devem dominar as extremidades da fronteira, enquanto mantêm uma rede complexa que conecta todas as propriedades do império. O objetivo é criar uma teia que, ao expandir territorialmente, posiciona os postos avançados como sentinelas estratégicas, maximizando a muralha defensiva.

A vitória não está apenas na quantidade de território conquistado, mas na maestria de suas escolhas, destacando-se em "A Grande Fronteira". Como líder imperial, ao assegurar a máxima presença defensiva e conectar todas as propriedades do vasto império, você gravará seu nome na história estratégica do Age of Empires. Que a sua sagacidade e estratégia iluminem o caminho para a supremacia!

Para este problema problema, definiremos $C_{1} = 100$, $C_{2} = 25$, e uma pontuação bônus para cada instância resolvida de $C_{3} = 70$.

Problema 03: ???

Descrição: ???

Resultados

Nesta seção disponibilizaremos os resultados das submissões. Para cada instância resolvida, uma pontuação bônus será aplicada.

Incluiremos uma submissão secreta de um membro da moderação da UBL para fins de benchmarking inicial. Esta submissão não será considerada para fins de premiação.

A pontuação será calculada a partir da média de $40$ iterações do algoritmo.

Resultados do Problema 01:

Resultados do Problema 02:

Resultados do Problema 03:

Premiação

Forneceremos uma premiação simbólica para os três primeiros colocados. Esta premiação consiste em cargos comemorativos no servidor da UBL.

Leitura recomendada

Nesta seção incluiremos alguns livros recomendados que podem ajudar na elaboração de algoritmos para os problemas que serão trabalhados nesta Rinha. Quando gratuitos, incluiremos um link para acesso.

Não faremos a distinção entre um livro de nível básico ou avançado. Cabe ao participante conferir as primeiras páginas do livro e fazer esse juízo por si só.

Referências

• Carvalho, Cerioli, Dahab, Feofiloff, Fernandes, Ferreira, Guimarães, Miyazawa, Pina Jr, Soares, Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, IMPA, 2001. Disponivel aqui.

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). London, England: MIT Press.

• J.L. Szwarcfiter e L. Markenzon, Estruturas de Dados e seus Algoritmos, 2a.ed., Livros Técnicos e Científicos, 1994.

• Kleinberg, J., & Tardos, E. (2006). Algorithm design. Pearson Education India.

• Mitzenmacher, M., & Upfal, E. (2017). Probability and computing (2nd ed.). Cambridge, England: Cambridge University Press.

• Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge University Press.

• P. Feofiloff, Y. Kohayakawa, & Y. Wakabayashi. (2011). Uma Introdução Sucinta à Teoria dos Grafos. Disponível aqui.

• P. Feofiloff. Análise de Algoritmos. Disponível aqui.

• P. Feofiloff. (2019). Minicurso de Análise de Algoritmos. Disponível aqui.

• Vazirani, V. V. (2002). Approximation algorithms. Springer Science & Business Media.