8. Problemas interativos

Nos artigos anteriores vimos vários exemplos de diferentes problemas. No entanto todos estes problemas tinham uma coisa em comum, nomeadamente que recebemos um input sobre o qual temos de fazer alguma tarefa e escrever um output que reflita esse resultado. E se quisermos algo mais dinâmico, onde o nosso input é dependente do que o nosso programa faz? Nas Olimpíadas temos um tipo de problema que faz exatamente isto, ao que chamamos um problema interativo.

Vamos ver como funciona um problema interativo e olhar para um exemplo.

Como funciona um problema interativo?

Para resolver um problema interativo o nosso objetivo é implementar uma (ou mais) função, cujo formato será dado num ficheiro template. Cada problema tem 2 ficheiros associados, um avaliador (normalmente chamado avaliador.cpp) e um template (normalmente chamado resolver.cpp). Existe uma versão de cada um dos ficheiros anteriores para cada linguagem, por exemplo se programarem em Java, vão querer usar os ficheiros avaliador.java e resolver.java. O ficheiro template contém a (ou as) função que devem implementar e é o único ficheiro que têm de submeter. Podem adicionar outras funções, variáveis e importar o que quiserem na vossa implementação, desde que não alterem o nome e os parâmetros da função a implementar. O ficheiro do avaliador contém o código que irá "simular" a interação, ou seja, esse ficheiro irá ler o input, chamar as funções do vosso programa, ver o resultado e escrever o resultado para o output. Não é suposto alterarem este ficheiro, ele vem completo para o poderem usar, mas podem no modificar se quiserem (para testar alguma coisa ou para motivos de debug). De notar que não precisam de submeter o ficheiro do avaliador para o Mooshak, por isso todas as modificações que fizerem não serão consideradas na vossa submissão. O código do avaliador que o Mooshak executa pode ser distinto do código de exemplo que vos é fornecido (por razões técnicas), mas se o vosso código funciona com o exemplo, também deve funcionar com o código no Mooshak.

É importante dizer que a vossa solução deve usar o avaliador como uma caixa negra, ou seja, não devem assumir nada sobre o seu código. Nalguns problemas existe alguma informação "escondida" que devem descobrir (como veremos no exemplo a seguir), que normalmente o avaliador tem acesso.

Dissecar um exemplo

O Rodrigo tem uma coleção de $N$ moedas numeradas de 1 a $N$, cada uma com um peso diferente, que é infelizmente desconhecido. O Rodrigo que avaliar o valor da sua coleção, para isso precisa de saber qual é a sua moeda mais pesada e a mais leve. Para isso, vai usar uma balança muito precisa. Esta balança consegue determinar qual a moeda mais pesada dado um par de moedas (não é possível comparar grupos de moedas, apenas um par de moedas). Visto que a balança é muito delicada, ele quer minimizar o número de vezes que a usa, mas quer descobrir qual a moeda mais leve e a mais pesada na mesma, consegues descobri-lo no menor número de comparações?

Agora que já vimos o objetivo do problema, vamos ver como funciona a interação neste problema.

Implementação

Comecemos por olhar para o template a implementar. Os templates de outras linguagens assim como as instruções de como os usar estão disponíveis no Mooshak. Ainda que usem outra linguagem devem ler o resto desta secção pois contém informação importante.

#include "avaliador.h"

void resolver(int N)
{
  int a = comparar(0, 1);
  resposta(0, a);
}

O nosso objetivo será implementar a função void resolver(int N), que recebe um inteiro $N$, o número de moedas na coleção do Rodrigo e não devolve qualquer valor. Para tal é suposto usarmos a função int comparar(int m1, int m2), que compara duas moedas, de índice m1 e m2 e retorna 0 caso o peso da moeda de índice m1 for a mais leve ou 1 caso a moeda de índice m2 for a mais leve. É importante que sempre que chamarmos a função comparar os parâmetros m1 e m2 sejam dois inteiros distintos entre 1 e $N$, caso contrário o nosso programa será considerado errado. Notem que não precisam de implementar esta função, a função comparar é implementada pelo avaliador e funciona como uma ferramenta para nós usarmos. Finalmente, para indicarmos a resposta do nosso programa, devemos invocar a função void resposta(int l, int p), que recebe dois inteiros l e p, onde l deve ser o índice da moeda mais leve de todas e p o índice da moeda mais pesada de todas. Só podemos invocar esta função uma vez, ou o nosso programa será considerado errado. Novamente, esta função é implementada pelo avaliador, não é suposto a implementarmos.

É importante notar que o nosso programa não deve ler nem escrever para os canais de entrada/saída padrão, ou poderá ser considerado errado. Também é de notar que a implementação das funções comparar e resposta são eficientes, ou seja, podemos chama-las o número máximo de vezes permitida pelas restrições do problema e o tempo total da execução de todas será inferior a 0.1 segundos (iremos ver mais sobre as restrições do problema na secção seguinte).

Vamos ver um exemplo de um caso de teste e como se poderia comportar um programa correto. Vamos supor que $N = 4$ e que a ordem relativa dos pesos das moedas é: 1 4 3 2, ou seja, a moeda 1 é a mais leve, a 4 a segunda mais leve, a 3 a terceira mais leve e a 2 a mais pesada. Claro que o nosso programa não terá acesso a esta informação, apenas ao valor de $N$ e à função de comparação. O nosso programa poderia fazer o seguinte:

Notem que o exemplo anterior apenas ilustra o que o programa pode fazer, não é necessário que o vosso programa tenha o mesmo comportamento (de facto, as comparações que fizemos não são suficientes para distinguir a moeda mais leve e pesada).

Solução exemplo

Ainda não falámos de limites, por isso vamos considerar que $N$ é no máximo 1000. A ideia mais simples de uma solução deve ter sido imediata quando leram o enunciado do problema. Ao ler as instruções anteriores deve ser agora fácil de implementar uma solução, mas vamos ver um exemplo de solução que faz o seguinte: começa por ter a moeda 1 como candidata a moeda mais leve. De seguida, compara a moeda candidata a mais leve com a moeda 2, se a moeda 2 for mais leve, passa a ser a moeda candidata a mais leve e repetidamente compara a moeda candidata com a moeda 3, 4, etc. Finalmente faz o mesmo para a moeda mais pesada e no fim devolve as duas.

#include "avaliador.h"

void resolver(int N)
{
  int candidata_leve = 1;
  for (int i = 2; i <= N; i++)
    if (comparar(candidata_leve, i) == 1)
      candidata_leve = i;

  int candidata_pesada = 1;
  for (int i = 2; i <= N; i++)
    if (comparar(candidata_pesada, i) == 0)
      candidata_pesada = i;

  resposta(candidata_leve, candidata_pesada);
}

O código é muito simples, por isso não o vamos explicar, mas serve para ilustrar como usar as funções do avaliador.

Outra noção de eficiência

Se já tentaram submeter o código acima no Mooshak devem ter reparado que não obtiveram 100 pontos, mas sim o resultado de "Wrong Answer". Este é um resultado muito estranho, o código parece estar correto, o que poderá estar errado?

Algo comum a vários problemas de interação (e uma das razões porque são tão interessantes) é que a métrica de eficiência não é o tempo que o programa leva a executar, mas algo diferente. Isto não significa que o vosso programa tem "tempo infinito" para ser executado, mas sim que a parte mais difícil não será otimizar a eficiência temporal do programa.

No problema de exemplo que estamos a considerar, a métrica de eficiência que vamos usar é o número de comparações que fizermos, ou seja, o número de vezes que chamamos a função comparar. Vamos fazer as contas para a solução anterior. Ora, para encontrar a moeda mais leve precisamos de $N - 1$ comparações (com a moeda 2, 3, ..., com a $N$) e mais $N - 1$ para encontrar a moeda mais pesada, ou seja, um total de $2(N - 1)$ comparações. Agora, podemos melhorar isto para cerca de $(3/2)N$ comparações, ou seja, para $N = 1000$ como o limite máximo dado para este problema, podemos usar no máximo $1500$ comparações. Para obtermos 100 pontos temos de conseguir este número de comparações. Reparem que aqui não podemos usar análise de big-O, como faziamos para as nossas contas de eficiência temporal, as constantes são muito importantes. É fácil de ver que $2(N - 1) = O((3/2)N)$, mas a solução inicial faz comparações a mais. Neste tipo de problemas temos de ter algum cuidado para ver o quão importantes são as constantes (ou seja, se $2N$ é muito diferente de $(3/2)N$) e regra geral são muito importantes, ao contrário de quando fazemos uma análise de complexidade temporal. Isto não é uma regra definitiva, pode haver problemas onde uma análise em que ignoramos constantes é suficiente, é preciso pensar um pouco para perceber quando, algo que se treina fazendo problemas e analisando problemas.

Deixamos a tarefa de pensar e implementar a solução de 100 pontos para vocês, mas já têm todas as ferramentas para o fazer.

Problema K: As moedas do Rodrigo

Este problema está disponível no Mooshak de treino como o problema K