11646. Olimpíadas

Olá meus amigos nerds! Vendo os problemas que nós já resolvemos aqui no blog, nesses seis meses, descobri que não tínhamos resolvido sequer um único problema de ordenação. E como ordenação é um dos temas mais importantes e úteis de computação resolvi fazer esse post para amenizar nossa falha.

Hoje vamos falar de olimpíadas, já que o problema 11646. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas de ouro. Se houver empate entre países no número de medalhas de ouro, o melhor colocado entre esses é o país que conseguiu o maior número de medalhas de prata. Se houver empate também no número de medalhas de prata, o melhor colocado entre esses é o país que recebeu o maior número de medalhas de bronze. Se ainda assim houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.

Solução

Esse é um típico problema de ordenação, basta ordenar os países de acordo com a regra dada e pronto. O único cuidado que devemos ter é usar um algoritmo de ordenação rápido, isto é, um algoritmo com complexidade O(n*log n) para não recebermos um TLE.

Esse problema não teria graça nenhuma, caso não falássemos um pouco sobre os algoritmos de ordenação. Sendo assim decidi explicar um pouco sobre o Quicksort (principal e mais rápido algoritmo de ordenação para a maioria dos problemas de ordenação).

O Quicksort é um algoritmo de divisão e conquista. Sua estratégia consiste em rearranjar os elementos de modo que os elementos "menores" que um dado elemento, chamado pivô, precedam esse elemento, enquanto os elementos "maiores" que o pivô o sucedam. Em seguida o Quicksort ordena recursivamente as duas sublistas definidas pelo pivô e as extremidades do array.

De forma mais algorítmica:

1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

O Quicksort é um algoritmo tão famoso que nós deveríamos, não só entende-lo, como também, ser capazes de implementá-lo. Se você nunca tentou implementar o Quicksort, eu o convidaria a tentar.

Uma boa referência, não só a respeito de ordenação, mas também de algoritmos e estruturas de dados de um modo geral é o livro do Cormem. Se você quer se aprofundar um pouco no assunto, eu recomendaria a leitura do capítulo 2 desse livro.

Implementação

Observe como o problema fica simples usando o sort da lib algorithm :)