Problema D - Previsão meteorológica

O Problema

Dado o número de sensores $N$ numa determinada zona, um número de dias $T$ a prever e uma situação $S$ (que indica a que parte do problema se refere), prever se irá chover em cada dia, ao longo dos $T$ dias, através das previsões dos $N$ sensores, errando no máximo $Q$ vezes.

Restrições

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

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Nota prévia

Este problema é um pouco diferente dos problemas interativos que têm aparecido nas ONI. À primeira vista parece quase impossível! Como é que podemos adivinhar o tempo usando um monte de previsões aparentemente aleatórias?

Este estilo de problema é um problema comum na área de ciência de computadores e engenharia informática, normalmente conhecido como "aprendizagem de máquina" (ou "machine learning"). Claro que o nosso problema é apenas simplificação de um tipo de problema muito particular que é recorrente nesta área, mas serve para nos dar uma introdução de como funciona esta fascinante área.

Vamos ver e analisar várias soluções que resolvem as diferentes subtarefas, mas é importante dizer que existem imensas mais abordagens a este problema do que as que se encontram neste artigo.

Subtarefa 1

Começamos por abordar o caso em que sabemos que há pelo menos um sensor que acerta sempre a previsão e em que podemos dar até 2600 erros. Este número 2600 parece um número mágico, mas tem alguma razão de ser. Para esta solução mais simples vamos ignorar completamente as previsões dos sensores: temos até 5000 dias para prever, a resposta é sempre 0 ou 1, e podemos errar até 2600 vezes, qual é a coisa mais simples que podemos fazer? Ora, vamos atirar uma moeda ao ar, se calhar cara escolhemos 0, se calhar coroa escolhemos 1, que é equivalente a dizer escolhemos aleatoriamente 0 com probabilidade 50% e 1 com probabilidade 50%.

Alguns de vocês podem estar um pouco confusos: "como é que isto funciona e como é que escrevo um programa que manda uma moeda ao ar?". Vamos responder à primeira pergunta primeiro e vamos primeiro assumir que temos uma função mágica atira_moeda() que devolve 0 com 50% de probabilidade e 1 com 50% de probabilidade. Qual é o valor esperado de erros que vamos obter? Ou seja, em média quantos erros dá este algoritmo? Para cada previsão temos 50% de hipóteses de acertar, logo no total vamos acertar, em média, metade das previsões. A média em si não chega para este algoritmo ter sucesso, queremos que a probabilidade de falhar seja tão pequena que ele passe os casos de teste todos. Não vamos fazer as contas de porquê que isto funciona (mas acreditem que é possível fazer!), mas se experimentarem implementar esta solução verão que é muito raro fazer mais que 2550 erros.

Para implementar a função "mágica" referida podemos usar as bibliotecas de geração de números pseudo-aleatórios da linguagem que usarem (a razão para se chamar pseudo-aleatório em vez de aleatório é técnica, vamos ignorar este pormenor). Em C++, precisamos de importar a biblioteca stdlib.h (nota: esta biblioteca é de C, o C++ tem outras bibliotecas de aleatoriedade mais complexas) e depois temos de usar duas funções. A primeira função chama-se srand(seed) e recebe um inteiro a que chamamos a seed, que é um número usado para inicializar a geração de números aleatórios. De forma muito sumária e informal, um gerador de números pseudo-aleatórios funciona ao pegar num número aleatório e a partir dele gerar vários, por isso precisamos de lhe fornecer um inicializador (a seed). Podem escolher um número qualquer como seed. Depois podemos usar a função rand() que devolve um inteiro entre 0 e um valor grande (normalmente o maior valor que um int pode ser). Para o transformar num valor 0 ou 1 basta ver o seu resto de divisão por 2, ou seja, fazer rand() % 2.

Com isto tudo, a implementação desta solução é apenas:

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

void iniciar(int N, int T, int S) {
  srand(12345);
}

int prever(int previsoes[MAXN], int A) {
  return rand() % 2;
}

Infelizmente (felizmente?) esta solução não consegue fazer menos de 2500 erros consistentemente, por isso só consegue passar a primeira subtarefa.

Subtarefa 2

Vamos finalmente usar as previsões dos sensores para guiar a nossa solução. É muito importante que usemos o facto de que pelo menos um dos sensores acerta sempre. Assim, vamos tentar "adivinhar" que sensor acerta sempre. Suponhamos que escolhemos o sensor 1 como o sensor que acerta sempre e vamos seguir a sua previsão cegamente, ou seja, o que o sensor 1 prever nós devolvemos como a nossa previsão. Claro que isto pode ser uma péssima ideia, se o sensor 1 estiver sempre errado não iremos acertar uma única previsão!

Para corrigir o anterior, vamos seguir a previsão do sensor 1 até que ele se engane. Se o sensor 1 der uma previsão errada, então não pode ser o sensor que acerta sempre, por isso podemos ignorá-lo a partir dai. Assim que o sensor 1 se enganar, vamos começar a seguir o sensor 2. Assim que o sensor 2 se enganar seguimos o 3 e por ai fora. O código para uma solução como esta seria o seguinte:

#include "avaliador.h"

int _N, sensor_atual, previsao_anterior;

void iniciar(int N, int T, int S) {
  _N = N;
  sensor_atual = 0;
}

int prever(int previsoes[MAXN], int A) {
  if (A != -1) {
    if (previsao_anterior != A)
      sensor_atual++;
  }

  previsao_anterior = previsoes[sensor_atual];
  return previsoes[sensor_atual];
}

Reparem como guardamos a previsão que fizemos numa variável global para que na próxima ronda a possamos comparar com o valor real e assim saber se nos enganámos ou não.

Quantos erros podemos dar? Sabemos que há pelo menos um sensor que acerta sempre, logo se chegarmos a esse sensor não vamos avançar mais (a variável sensor_atual não é maior que o índice desse sensor). Adicionalmente, podemos errar no máximo uma vez por sensor, assim que erramos passamos à frente, logo no máximo erramos $N$ vezes, ou seja, erramos no máximo 100 vezes. Isto significa que é suficiente para a primeira e segunda subtarefas, mas infelizmente não para as restantes.

Subtarefa 3

Na solução anterior podemos ver que estamos a desperdiçar alguma informação. Por exemplo, se o sensor 1 errar passado 5 previsões e nesses 5 dias o sensor 2 também falhou uma vez, não vale a pena tentarmos seguir o sensor 2, já sabemos que falhou. Só esta informação não chega para melhorarmos a nossa solução, os sensores podem falhar de "forma ordenada" e assim o número de erros que teríamos tendo esta informação em conta seria o mesmo.

Mas vamos usar esta informação da seguinte forma: suponham que num certo dia sabemos que o conjunto de sensores $S$ nunca erro, ou seja, chamamos de $S$ o conjunto de sensores que nunca errou. Podemos ignorar as previsões de todos os outros sensores. Agora, para o dia em questão, os sensores em $S$ fizeram diferentes previsões, qual devemos escolher? Uma ideia intuitiva é escolher a maioria, ou seja, ver qual a previsão que é escolhida mais vezes por sensores em $S$. Esta ideia é muito poderosa! Imaginem que acertamos a nossa previsão, então tudo bem, vamos poder eliminar os sensores que tiveram uma previsão errada sem dar nenhum erro. E se a nossa previsão estiver incorreta? Então sabemos que pelo menos metade dos sensores em $S$ se enganaram, ou seja, vamos eliminar metade dos sensores em $S$ como potenciais sensores que acertam sempre. Se começamos com $N$ potenciais sensores que nunca se enganam e sempre que cometemos um erro diminuímos para metade o número de sensores potenciais, depois de darmos $\log(N)$ erros sabemos que temos exatamente 1 sensor potencial, ou seja, sabemos exatamente qual o sensor que acerta sempre! Logo só podemos dar no total $\log(N)$ erros, o que para os valores do problema é na ordem de $6$ erros no máximo. Isto permite-nos resolver todas as subtarefas relativas à parte I.

Uma possível implementação disto seria:

#include "avaliador.h"

int _N;
int previsoes_anteriores[MAXN];
int potencial[MAXN];

void iniciar(int N, int T, int S) {
  _N = N;

  for (int i = 0; i < _N; i++)
    potencial[i] = 1;
}

int prever(int previsoes[MAXN], int A) {
  if (A != -1) {
    for (int i = 0; i < _N; i++)
      if (previsoes_anteriores[i] != A)
        potencial[i] = 0;
  }

  for (int i = 0; i < _N; i++)
    previsoes_anteriores[i] = previsoes[i];

  int uns = 0, zeros = 0;
  for (int i = 0; i < _N; i++)
    if (potencial[i] == 1) {
      if (previsoes[i] == 0)
        zeros++;
      if (previsoes[i] == 1)
        uns++;
    }

  if (uns > zeros)
    return 1;
  else
    return 0;
}

Subtarefa 4

Vamos agora passar a um caso onde sabemos que o melhor sensor erra no máximo 1% das vezes, o que para os valores do problema significa que pode errar no máximo 50 vezes.

A primeira solução que vamos ver usa a solução que acabamos de ver para a subtarefa 3. Vamos aplicar o mesmo raciocínio de manter um conjunto, que vamos chamar novamente de $S$, que mantém os sensores que nunca erraram e vamos escolher a opção de maioria das previsões dos sensores em $S$. Agora, usando o mesmo raciocínio, sempre que erramos diminuímos para metade o tamanho deste conjunto, de tal forma que depois de errarmos no máximo $\log(N)$ vezes este conjunto estará vazio. No caso anterior este conjunto nunca ficava vazio, mas agora como o melhor sensor pode errar algumas vezes, o conjunto pode ficar vazio.

Se $S$ ficar vazio, sabemos que todos os sensores já erraram pelo menos uma vez e nós errámos no máximo $\log(N)$ vezes, ou seja, 7 vezes. Por isso agora vamos repetir a mesma ideia, mas com os sensores que erraram apenas uma vez, ou seja, vamos colocar todos os sensores novamente em $S$ e vamos escolher a opção da maioria. Novamente, $S$ pode ficar vazio, visto que o melhor sensor pode errar mais que uma vez, mas repetimos a mesma coisa.

Após no máximo 50 repetições, quando aplicarmos o mesmo algoritmo o conjunto $S$ nunca fica vazio, visto que há pelo menos um sensor que erra no máximo 50 vezes, logo não voltamos a errar. Por cada vez que corremos este algoritmo erramos 7 vezes e corremos o algoritmo no máximo 50 vezes, ou seja, erramos no máximo $7 \cdot 50 = 350$ vezes, o que é suficiente para a subtarefa 4!

Uma possível implementação disto seria (esta implementação é ligeiramente diferente da ideia descrita, mas funciona da mesma forma):

#include "avaliador.h"

int _N;
int previsoes_anteriores[MAXN];
int erros[MAXN], erros_em_S;

void iniciar(int N, int T, int S) {
  _N = N;

  erros_em_S = 0;
  for (int i = 0; i < _N; i++)
    erros[i] = 0;
}

int prever(int previsoes[MAXN], int A) {
  if (A != -1) {
    for (int i = 0; i < _N; i++)
      if (previsoes_anteriores[i] != A)
        erros[i]++;
  }

  erros_em_S = erros[0];
  for (int i = 0; i < _N; i++) {
    previsoes_anteriores[i] = previsoes[i];
    if (erros[i] < erros_em_S)
      erros_em_S = erros[i];
  }

  int uns = 0, zeros = 0;
  for (int i = 0; i < _N; i++)
    if (erros[i] == erros_em_S) {
      if (previsoes[i] == 0)
        zeros++;
      if (previsoes[i] == 1)
        uns++;
    }

  if (uns > zeros)
    return 1;
  else
    return 0;
}

Subtarefa 5

Não há uma solução em específico que consiga menos de 250 erros mas mais que 150, mas há várias heurísticas que com alguma "sorte" conseguem ficar neste patamar. É importante notar que é impossível gerar o pior caso para qualquer solução, os casos de teste são gerados com alguma aleatoriedade com padrões diferentes, por isso diferentes heurísticas inteligentes devem conseguir estar neste patamar mesmo que o seu pior caso seja mais que 250 erros.

Um exemplo de heurística que alguns tentaram e que podia conseguir os pontos deste patamar é olhar para os sensores que falharam menos vezes até agora e prever a opção da maioria. Até mesmo a solução que apresentámos na subtarefa 4 conseguia ser implementada para conseguir esta subtarefa. Para conseguir a subtarefa 6 era preciso uma heurística ainda mais inteligente ou a solução ótima que vamos apresentar a seguir.

Subtarefa 6

Vamos ver uma solução que nunca comete mais que 150 erros e até, em média, não passa dos 100. Vamos atribuir um peso a cada sensor, que indica a nossa confiança nesse sensor. Inicialmente o peso de cada sensor será 1. Agora, para fazermos a nossa previsão, vamos ver qual a soma do peso dos sensores que prevêem 1 e dos que prevêem 0 e vamos escolher a opção com o maior peso. Depois de fazermos a nossa previsão, quando obtermos o valor real vamos pegar em cada sensor cuja previsão estava incorreta e vamos dividir o seu peso por 2. Notem que isto implica que os pesos possam ser valores fracionários (embora haja um truque que permite implementar isto usando long long int em C++ ou long em Java, que fica para pensarem). Notamos ainda que a análise que vamos fazer é um pouco técnica e matemática, por isso podem precisar de a ler um par de vezes.

A solução é muito simples, mas porque é que funciona? Vamos fazer um tipo de análise que é normalmente conhecida como análise amortizada na literatura de algoritmos, é uma técnica muito genérica e poderosa. Para cada dia $i$, vamos representar por $\Psi_i$ a soma dos pesos de todos os sensores e vamos chamar a esta quantidade o potencial do dia $i$. Vamos fazer duas observações:

Primeiro, qual é o potencial mínimo ao fim dos $T$ dias? Bom, sabemos que pelo menos um dos sensores errou no máximo 50 vezes (1% dos 5000 dias), logo o seu peso foi dividido para metade no máximo 50 vezes, ou seja, é pelo menos $2^{-50}$. Isto implica que $\Psi_T \geq 2^{-50}$.

Segundo, vamos supor que usando o nosso algoritmo, a nossa previsão para o dia $i$ estava incorreta, como é que isto afeta o potencial do próximo dia? Outra maneira de fazer esta pergunta, qual a dependência de $\Psi_{i+1}$ em relação a $\Psi_i$? Se cometemos um erro, significa que o peso da resposta correta era menor que o peso da resposta errada. Isto implica que dividimos por 2 o peso de todos os sensores que se enganaram. Suponhamos que o peso dos sensores corretos era $C$ e dos sensores errados $E$. Sabemos que $E \geq C$, visto que previmos a resposta errada. Adicionalmente, pela definição de potencial sabemos que $\Psi_i = C + E$. Finalmente, dividimos por dois o peso dos sensores incorretos, ou seja, $\Psi_{i + 1} = C + E/2$. Com tudo isto podemos concluir que $\Psi_{i + 1} = C + E - E/2 = \Psi_i - E/2$, e ainda $\Psi_i \leq 2E$, ou seja, $\Psi_i / 2 \leq E$. Juntando tudo temos que $\Psi_{i+1} \leq (3/4) \Psi_i$.

Podemos agora aplicar a inequação da segunda observação repetidamente. Seja $M$ o número de erros que o nosso algoritmo dá. Sempre que erramos podemos aplicar a segunda observação e notem ainda que se não errarmos apenas sabemos que $\Psi_{i+1} \leq \Psi_i$. Chegamos então à conclusão que $\Psi_T \leq \Psi_1 \cdot (3/4)^M = N (3/4)^M$. Juntando as duas inequações temos que $2^{-50} \leq N (3/4)^M$. Para resolver esta inequação primeiro aplicamos o logaritmo de base $3/4$ dos dois lados (é uma função decrescente por isso é válido fazê-lo invertendo a inequação) e obtemos $-50 \log_{3/4}(2) \geq \log_{3/4}(N) + M$, movendo os termos ficamos com: $M \leq -(50 \log_{3/4}(2) + \log_{3/4}(N)) = 50 \log_{4/3}(2) + \log_{4/3}(N)$. Se substituirmos o valor máximo de $N$ chegamos à conclusão que $M \leq 136$, o que significa que o nosso algoritmo dá no máximo 136 erros!

De facto, até podemos melhorar esta análise (embora não seja muito fácil) para conseguir um limite de 127, modificando ligeiramente o algoritmo. Se usarmos aleatoriedade, ou seja, em vez de escolher a opção com o maior peso, mas sim escolher aleatoriamente usando o peso das duas opções como a probabilidade (se o peso dos uns for $X$ e dos zeros $Y$ então prevemos um com probabilidade $X / (X + Y)$ e zero com probabilidade $Y / (X + Y)$) e conseguimos reduzir o valor máximo para cerca de 80. Visto que os testes são ligeiramente aleatórios, esta solução nunca falha mais de 100 vezes para eles.