Problema A - Corridas de Berlindes

Parte I

Dados os $N$ berlindes, dados por um par de agilidade e velocidade $ (A_i, V_i) $, determinar quantos berlindes diferentes há.

Restrições

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Solução

Há várias formas de resolver este problema eficientemente, mas vamos ver a mais simples. É sempre muito importante verificar as restrições do problema. Neste problema sabemos que os valores de $A_i$ e $V_i$ são no máximo 10 e no mínimo 0, por isso há no máximo 121 (11 vezes 11) berlindes diferentes. São eles o (0, 0), o (0, 1), o (0, 2), ...

Isto significa que podemos manter uma array bidimensional onde marcamos que berlindes existem. Vamos chamar a array de berlindes e será uma array de 11 por 11, ou seja, int berlindes[11][11]. A entrada $i, j$ desta array, isto é, o valor de berlindes[i][j], representa se há um berlinde de agilidade igual a $i$ e velocidade igual a $j$. Para preenchermos esta array basta iterarmos por cada berlinde e marcar a posição correspondente, isto é, para o $i$-ésimo berlinde marcamos berlindes[A[i]][V[i]].

Finalmente, basta contabilizarmos o número total de berlindes que marcámos, o que podemos fazer iterando por todos os valores de $i$ e $j$ entre 0 e 11 (ou seja, todos os valores de agilidade e velocidade possíveis).

Esta solução pode ser implementada através do seguinte pedaço de código:

#include <stdio.h>

int A[100000];
int V[100000];
int berlindes[11][11];

int main() {
  int P;
  scanf("%d", &P);
  int N;
  scanf("%d", &N);

  for (int i = 0; i < N; i++)
    scanf("%d %d", &A[i], &V[i]);

  if (P == 1) {
    // Enche a array berlindes tipos de 0s
    memset(berlindes, 0, sizeof berlindes);
    for (int i = 0; i < N; i++)
      berlindes[A[i]][V[i]] = 1;

    int resultado = 0;
    for (int i = 0; i < 11; i++)
      for (int j = 0; j < 11; j++)
        resultado += berlindes[i][j];

    printf("%d\n", resultado);
  }
  return 0;
}

Vamos agora fazer a análise da complexidade temporal deste algoritmo. Se ainda não leste o conjunto de artigos de iniciação às ONI é muito importante que o faças. Entre outros temas mais introdutórios e avançados abordamos como analisar um programa de modo a conseguir estimar quantos pontos terá. Vamos fazer essa análise a seguir para o código acima a seguir.

Artigo: Guia de iniciação às ONI

No 4o artigo deste guia abordamos o tema de análise de complexidade.

Precisamos de dois ciclos: um que percorre todos os berlindes e um que percorre todos os tipos de berlindes possíveis. Em notação Big-O, a complexidade desta solução é traduzida por $O(N + B)$, onde $B$ representa o número de tipos de berlindes diferentes (ou seja 121). Isto é suficiente para resolver ambas as subtarefas da primeira parte e obtém assim os 50 pontos desta parte.

Parte II

Dados os $N$ berlindes, dados por um par de agilidade e velocidade $(A_i, V_i)$, determinar quantas vitórias terá o berlinde vencedor de um torneiro.

Restrições

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Solução

A que berlindes ganha o $i$-ésimo berlinde numa corrida? Ora, aos berlindes do tipo $(a, v)$ onde $a < A_i$ e $v < V_i$. Dado isto vamos fazer-nos a seguinte pergunta: como é que podemos obter o número de berlindes que perdem corridas contra o $i$-ésimo berlinde de forma eficiente?

A estratégia vai ser a mesma que na Parte I, nomeadamente, vamos contar quantos berlindes há de cada tipo. Fazemos isto mantendo a mesma array berlindes que guarda a contagem de berlindes de cada tipo. Agora que temos esta array, se quisermos responder à pergunta anterior só temos de somar os valores de berlindes[a][v] para todos os valores de a e v tais que $a < A_i$ e $v < V_i$, o que podemos fazer com dois ciclos. Basta fazermos isto para cada berlinde e manter o máximo número de vitórias que encontrámos.

Esta solução pode ser implementada através do seguinte pedaço de código:

#include <stdio.h>

int A[100000];
int V[100000];
int berlindes[11][11];

int main() {
  int P;
  scanf("%d", &P);
  int N;
  scanf("%d", &N);

  for (int i = 0; i < N; i++)
    scanf("%d %d", &A[i], &V[i]);

  if (P == 2) {
    memset(berlindes, 0, sizeof berlindes);
    for (int i = 0; i < N; i++)
      berlindes[A[i]][V[i]]++; // contar tipos de berlindes

    int resultado = 0;
    for (int b = 0; b < N; b++) {
      int vitorias = 0;
      for (int i = 0; i < A[b]; i++)
        for (int j = 0; j < V[b]; j++)
          vitorias += berlindes[i][j];
      resultado = max(resultado, vitorias);
    }

    printf("%d\n", resultado);
  }
  return 0;
}

Nesta solução temos um ciclo que para cada berlinde itera por todos os tipos de berlindes diferentes, por isso a complexidade final é de $O(NB)$, onde, novamente, $B$ representa o número de tipos de berlindes diferentes. Isto é suficiente para resolver ambas as subtarefas da primeira parte e obtém assim os 50 pontos desta parte.

Extra *

Há várias soluções alternativas e mais eficientes para ambas as partes. Listamos aqui as suas complexidades e algumas dicas de como as obter como exercício:

• Na Parte II, podemos obter um algoritmo cuja complexidade é $O(N + B)$ se précalcularmos algumas coisas. Consegues ver como?
• Vamos supor que os valores de agilidade e velocidade, em vez de serem no máximo 10, eram no máximo $10^5$. Neste caso as nossas soluções anteriores são pouco eficientes. Mas podemos obter uma solução $O(N \log N)$ que resolveria este caso, usando ideias de ordenação e pesquisa binária. Consegues pensar como fazê-lo?