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.

#include "avaliador.h"

int a[MAXN];

int escolher(int N) {
  for (int i = 0; i < N; i++)
    a[i] = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
      if(testar(i + 1, j + 1))
        a[i]++;
      else
        a[j]++;
    }
  }
    
  for (int i = 0; i < N; i++)
    if (a[i] == N / 2)
      return i + 1;
}

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):

#include "avaliador.h"
#include <algorithm>

using namespace std;

int a[MAXN + 5];

bool cmp(int i, int j) { return testar(j + 1, i + 1); }

int escolher(int N)
{
  for (int i = 0; i < N; i++)
    a[i] = i;

  sort(a, a + N, cmp);
  
  return a[(N + 1) / 2 - 1] + 1;
}

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:

#include "avaliador.h"
#include <stdlib.h>
#include <algorithm>

using namespace std;

int arr[MAXN + 5];

int select(int l, int r, int k) {
  if (r == l)
    return arr[l];

  // Escolhemos um pivot aleatorio
  int pivot = rand() % (r - l + 1) + l;

  swap(arr[pivot], arr[l]);
  pivot = l;

  // Agora efetuamos a particao (isto e so uma maneira de o fazer)
  for (int i = l + 1; i <= r; i++) {
    if (testar(arr[pivot] + 1, arr[i] + 1)) {
      swap(arr[pivot + 1], arr[i]);
      swap(arr[pivot], arr[pivot + 1]);
      pivot++;
    }
  }

  // E finalmente a escolha recursiva
  if (pivot - l == k)
    return arr[pivot];
  if (pivot - l > k)
    return select(l, pivot - 1, k);
  if (pivot - l < k)
    return select(pivot + 1, r, k - (pivot - l) - 1);
}

int escolher(int N) {
  // Notem que mesmo que usem aleatoriedade, os vossos programas devem
  // ser deterministicos. Podem para isso usar uma seed fixa
  srand(12345);
  for (int i = 0; i < N; i++)
    arr[i] = i;

  return select(0, N - 1, (N - 1) / 2) + 1;
}

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:

int m3(int a, int b, int c) {
  int c1 = testar(arr[a] + 1, arr[b] + 1);
  int c2 = testar(arr[b] + 1, arr[c] + 1);
  int c3 = testar(arr[a] + 1, arr[c] + 1);

  if (c1 && !c3)
    return a;
  if (c2 && c1)
    return b;
  return c;
}

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.