Soluções da Qualificação das ONI'2020
Problema D - Equipa de Salvamento
Tipo de problema: Algoritmos de Seleção
Autor do problema: Ricardo Pereira (FCUP - DCC)
Dificuldade do problema: Médio
O Problema
Dada uma sequência de $N$ inteiros distintos ($N$ impar), calcular a mediana da sequência.
Restrições
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ $N$ ≤ $10^4$ | Número de robots |
1 ≤ $Q$ ≤ 200 000 | Número de testes |
Brute Force
Queremos calcular a mediana da sequência, ou seja, o elemento que é menor que metade dos outros elementos e maior que metade dos outros elementos. Este é um problema clássico em informática. Vamos ver como implementar a solução mais simples possível, que utiliza $N^2$ testes. Para cada robot $i$, vamos calcular quantos robot há mais fracos que o robot $i$. A resposta será aquele que é mais forte que exatamente $N / 2$ robots.
Esta solução é obviamente muito pouco eficiente, e por isso só consegue os primeiros 10 pontos.
Ordenar
É muito fácil de ver que a mediana de uma sequência é o elemento que se encontra extamente a meio da sequência após a ordenarmos. Por isso, uma solução possível é ordenar!
Artigo: Artigo de ordenação
No 5o artigo deste guia abordamos o ordenação e pesquisa.
Ordenar requer $C \cdot N\log N$ testes, onde $C$ é uma constante. Para algo como um quicksort ou mergesort, esta constante é bastante próxima de 1.5, logo é suficiente para as primeiras duas subtarefas, ou seja, 35 pontos.
Usando a STL de C++, há uma forma mesmo simples de implementar esta ideia (mas aconselhamos a implementarem um dos algoritmos de ordenação se nunca o fizeram):
Selecionar
Agora vamos ver algoritmos mais eficientes. Vamos ver como calcular a mediana usando $O(N)$ testes (e veremos que a constante não é demasiado grande). Para isto vamos analisar um algoritmo conhecido como quickselect, que é baseado no algoritmo de quicksort.
O algoritmo comum de quicksort aplicado a uma array $A$ tem dois passos: particionar e recursão. Particionar significa que escolhemos um elemento $p$ (normalmente conhecido por pivot) e partimos a array em duas metades, a dos elementos maiores que $A_p$ e dos elementos menores que $A_p$. Efetuar esta partição é fácil em tempo $O(N)$. De seguida, basta nos ordenar cada uma das novas metades (aplicando a mesma ideia recursiva de quicksort) e juntá-las.
Como devem saber (por exemplo, se tiverem lido o artigo linkado em cima), a complexidade temporal do quicksort está muito dependente da escolha do pivot. Se o valor que escolhermos dividir sempre a array em duas metades de igual tamanho (ou muito parecido), então estamos efetivamente a dividir o trabalho que precisamos de fazer em dois. Se pelo contrário, o nosso pivot dividir a array numa metade muito pequena e numa muito grande, então não estamos a dividir nada o trabalho que precisamos. Uma forma comum de mitigar este fator é usar aleatoriedade, isto é, escolher o pivot de forma aleatória.
A ideia do quickselect é semelhante, mas antes de a descrevermos vamos generalizar ligeiramente o problema (é importante). Vamos supor que em vez da mediana, queremos o $K$-ésimo menor elemento (a mediana é o $N / 2$ maior elemento). Se aplicarmos a mesma ideia, nomeadamente, de escolher um pivot $p$ e particionarmos a array em duas metades, uma maior que $A_p$ e uma menor que $A_p$, podemos agora saber em que metade se encontra o $K$-ésimo elemento. Esta partição diz-nos quantos elementos há menores que $A_p$, vamos supor que este número é $X$:
- Se $X < K$, então o $K$-ésimo menor elemento estará na segunda metade, isto é, na metade que contém os elementos maiores que $A_p$;
- Se $X > K$, então o $K$-ésimo menor elemento estará na primeira metade, isto é, na metade que contém os elementos menores que $A_p$;
- Se $X = K$, então o $K$-ésimo menor elemento é $p$!
Assim, podemos recursivamente aplicar a mesma ideia do quickselect (exatamente como no quicksort), mas apenas na metade que nos interessa, ou seja:
- Se $X < K$, então queremos o $K-X$-ésimo menor elemento da segunda metade;
- Se $X > K$, então queremos o $K$-ésimo menor elemento da primeira metade;
Reparem como no primeiro caso queremos olhar para o $K-X$-ésimo menor elemento, visto que descartamos os $X$ elementos da primeira metade. Para perceberem melhor isto, observem uma possível implementação:
A complexidade desta ideia também depende da escolha do pivot, por isso escolher um aleatoriamente é importante. Não é óbvio, mas este algoritmo faz apenas $C \cdot N$ testes, para uma certa constante $C$, com uma escolha de pivot completamente aleatória. A análise desta complexidade não é muito fácil (nunca é quando o algoritmo é aleatório). Com alguma intuição é possível ver que o seu comportamento é $O(N)$ (se quiserem ver uma prova formal que assim o é, podem ver uma aqui). Para este problema o que podem (e devem!) fazer é tentar determinar o número de testes experimentalmente. Isto significa gerar vários casos de teste aleatórios e observar o comportamento do vosso algoritmo. Se o fizerem, conseguem determinar que o valor de $C$ é no máximo cerca de 6, o que significa que conseguem as primeira 4 subtarefas e um total de 85 pontos.
Otimizar
Se otimizarmos a constante do quickselect e a reduzirmos de cerca de $6$ para cerca de $3$, então o problema fica resolvido. Para isto é muito importante usarem a ideia de testes empíricos, ou seja, analisarem o comportamento do vosso código ao gerar vários testes e ver o número de testes que ele faz.
Com isto, podem experimentar várias ideias. Há muita coisa que consegue otimizar a constante para cerca de 3, mas a mais simples faz simplesmente o seguinte. Em vez de escolher o pivot uniformemente aleatoriamente, vamos ser mais inteligentes. Vamos escolher 3 pivots (novamente, cada um uniformemente aleatoriamente) e vamos calcular a mediana dos 3. Podem calcular esta mediana fazendo exatamente 3 testes, como no código seguinte:
Agora usamos a mediana dos 3 pivots como o pivot para a partição. Ao escolhermos uma mediana de 3 valores aleatórios, é mais provavel escolher um valor central, e só gastamos 3 testes a fazer isto. Se implementarem isto e testarem, conseguem ver que a constante desce para próximo de 4, mas não é bem suficiente para ser sempre menor que 4. Por isso vamos repetir a ideia! Em vez de 3 pivots, escolhemos 9 e calculamos a mediana dos 9. Ou ainda, escolhemos 3 grupos de 3, para cada um calculamos a sua mediana (usando o código acima) e depois calculamos a mediana das medianas (novamente, usando o código acima). Podem brincar um pouco com estes valores, por exemplo, não precisamos de aplicar estes 9 pivots em toda a recursão, se tivermos a calcular o quickselect de uma subarray pequena (por exemplo, com apenas 100 elementos) podemos apenas escolhes 3 pivots.
Se fizerem este processo de escolher medianas diferentes números de pivots e usando testes empíricos para determinar o quão bom é o vosso algoritmo, conseguem facilmente chegar a um algoritmo cuja constante é muito próxima de 3.