Até agora o nosso foco foi em escrever programas que executam corretamente o que pede a tarefa dada pelo problema que estamos a resolver. Vamos ver como o tempo que um programa demora a ser executado pode ser um fator a considerar e como analisá-lo.

Quanto tempo demora o meu programa a correr?

Vamos começar por considerar um problema de exemplo muito simples:

O Henrique tem dois baralhos de cartas muito especiais. Ao contrário de um baralho de cartas normal, nenhuma carta tem um naipe e cada cada carta contém um número entre 1 e 1000. O Henrique gosta de jogar um jogo que consiste em fazer pares de cartas, uma do primeiro baralho e uma do segundo baralho. As regras do jogo não são importantes, mas para saber se o jogo é justo o Henrique precisa de saber quantos pares há cuja soma dos dois números é par e quantos há cuja soma é impar. Consegues ajudar o Henrique?

Ora, desconstruindo este problema, são-nos dadas duas sequências de números. Vamos supor que a primeira tem $N_1$ números e a segunda $N_2$ números. Queremos agora contar quantas formas há de escolher um número da primeira sequência e um número da segunda sequência tal que a sua soma seja par e o mesmo para somas impares. Para resolver este problema só temos de ter dois ciclos encadeados, que passam por cada par de números, somar os dois números e determinar se um número é par. Só nos resta saber como determinar se um número é par.

Um número é par se for divisível por dois. Outra maneira de dizer isto é dizer que o resto da divisão do número por dois é zero. Como é que isto nos ajuda? Exite um operador em C++ (e em quase todas as linguagens de programação) que calcula exatamente isto, é o operador %, ou seja, 7 % 2 dá-nos o resto da divisão de 7 por 2, que é obviamente 1. Assim, podemos determinar facilmente se um número é par ou não e resolver o problema.

Vamos ainda assumir que o input vem da seguinte forma: primeiro recebemos um inteiro $N_1$ numa linha, seguido de $N_1$ inteiros entre 1 e 1000 na mesma linha e separados por espaços, depois um inteiro $N_2$ numa linha e finalmente $N_2$ inteiros entre 1 e 1000 na mesma linha e separados por espaços. Além disso, vamos supor que tanto $N_1$ como $N_2$ são sempre entre 1 e 100. O formato do output será dois inteiros numa linha, o primeiro representa o número de pares cuja soma é par e o segundo o número de pares cuja soma é impar. O código seguinte faz exatamente isso:

#include <iostream>

using namespace std;

int seq1[100], seq2[100]; // Duas arrays para guardar as sequencias

int par(int numero) {
  return numero % 2 == 0;
}

int main() {
  int n1, n2;

  cin >> n1;                    // Vamos ler a primeira sequencia
  for (int i = 0; i < n1; i++)
  cin >> seq1[i];

  cin >> n2;                    // Vamos ler a segunda sequencia
  for (int i = 0; i < n2; i++)
  cin >> seq2[i];

  int npares = 0, nimpares = 0; // Os contadores de pares e impares
  for (int i = 0; i < n1; i++) // Para cada par de numeros possivel
    for (int j = 0; j < n2; j++)
      if (par(seq1[i] + seq2[j])) // Verificar se a soma e par
        npares++;
      else
        nimpares++;

  cout << npares << " " << nimpares << endl;

  return 0;
}

Podemos agora tentar estimar o tempo que o nosso programa demora a correr. Para tal, vamos primeiro focar-nos na linha do nosso programa que se encontra dentro dos dois ciclos for, ou seja, a linha if (par(seq1[i] + seq2[j])). Quantas vezes é esta linha executada? Ora, o primeiro ciclo for fará $N_1$ iterações, para cada uma delas o segundo ciclo for fará $N_2$ iterações e para cada uma delas será executada a linha que nos interessa. Isto significa que esta linha será executada $N_1 \times N_2$ vezes.

O processo de execução de uma linha de um programa não é completamente trivial, mas para já vamos assumir que a linha mencionada é executada como uma única instrução e que o computador consegue executar várias destas instruções por segundo. Na prática, uma linha de código é dividida em várias instruções pelo computador (na verdade quem faz esta tarefa é o nosso amigo compilador), de acordo com as chamadas de funções, operações aritméticas/Booleanas, etc, que a linha contém. O número de instruções que um computador consegue executar por segundo depende de vários fatores relacionados com o seu hardware e com a natureza da instrução a executar, mas uma boa estimativa para o tipo de hardware normalmente usado pelas máquinas das Olimpíadas (equivalente a um computador portátil comum) é de $10^9$ instruções por segundo.

O tempo limite para executar um programa para um problema das Olimpíadas é geralmente de 1 segundo (nunca mais do que 5 segundos, sendo que os tempos limite são indicados para cada prova). Visto que $N_1$ e $N_2$ são menores ou iguais a 100, isto significa que o nosso programa corre confortavelmente abaixo de 1 segundo. Mas e se $N_1$ e $N_2$ fossem maiores, por exemplo, da ordem de 100.000 ($10^5$)? Bom nesse caso, pelas nossas contas, seriam precisos pelo menos 10 segundos para executar o nosso programa (e notem que estamos a ignorar o resto do programa e a considerar que a linha mencionada é executada numa instrução pelo computador), ou seja, o programa não correria dentro do limite de tempo estabelecido.

Melhorar o programa anterior

Vamos tentar modificar o programa anterior para conseguir que corra em menos de um segundo quando $N_1$ e $N_2$ são da ordem de 100.000. Começamos por fazer a seguinte observação muito simples: ao somar dois números pares o resultado é sempre par, ao somar dois números impares o resultado é sempre par e ao somar um impar com um par o resultado é sempre impar. Isto significa que não interessa quais os números em cada sequência, apenas a quantidade de números pares e impares em cada. Podemos contar facilmente cada um destes números usando a função int par(int n) que já escrevemos, e guardar cada um numa variável. Vamos supor que fizemos o anterior e guardámos a quantidade de números pares da primeira sequência numa variável p1, a quantidade de números impares da primeira sequência numa variável i1, a quantidade de números pares da segunda sequência numa variável p2, a quantidade de números impares da segunda sequência numa variável i2. Então, para contar o número de pares de números cuja soma é par, só temos de contar o número de formas de escolher um número par da primeira sequência e um número par da segunda sequência, que é exatamente p1 * p2, e somar-lhe o número de formas de escolher um número impar da primeira sequência e um número impar da segunda sequência, que é exatamente i1 * i2. Analogamente, podemos contar o número total de pares com soma impar.

Porquê que o parágrafo é importante? Reparem que para preencher o valor das variáveis p1, i1, p2, i2, só precisamos de dois ciclos for em que percorremos todos os elementos das duas sequências. Isto significa que o número de instruções que este novo programa executa seria $N_1 + N_2$. Para as nossas contas anteriores, este programa para $N_1$ e $N_2$ da ordem de 100.000 corre bem abaixo de 1 segundo, que é exatamente o que queríamos.

Deixamos a escrita do programa com esta ideia ao vosso critério, e se quiserem podem submetê-lo no Mooshak.

Problema F: O jogo do Henrique

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

Nota de implementação

Ao escrever uma solução com a ideia anterior devem ter cuidado com a representação de inteiros das variáveis a usar. Um inteiro do tipo int é representado com 32 bits, isto significa que pode representar números desde $-2^{31}$ a $2^{31} - 1$. Isto é importante porque para $N_1$ e $N_2$ iguais a $100.000$, o número de pares e impares será da ordem de $10^{10}$, que excede $2^{31} - 1$ (uma mnemónica para não esquecerem o valor máximo que o tipo int pode representar é que é da ordem de $2\times10^9$). Assim, terão de usar um tipo de inteiro que permita representar um intervalo de valores maior. O tipo que normalmente usamos é long long int, que é uma representação de 64 bits, ou seja, pode representar números desde $-2^{63}$ a $2^{63} - 1$.

Até agora não abordamos este tema, mas é importante terem a cuidado com os tipos de variável que estão a usar, especialmente a representar inteiros. Isto também se aplica às outras linguagens! Esta pode ser uma boa altura para revisitarem um dos artigos de aprender a programar e voltarem a ler sobre tipos de variáveis. Agora que já são mais experientes a sua informação será mais relevante.

Eficiência e eficácia

Os programas das duas seções anteriores ambos resolvem o problema dado corretamente. Porém, são claramente diferentes ao nível do tempo que necessitam para serem executados. Reparem que se quisessemos valores de $N_1$ e $N_2$ ainda maiores, por exemplo, da ordem de 1.000.000 ($10^6$) esta diferença de tempo de execução ainda ficaria mais pronunciada. Por isso, quando estamos a resolver um problema queremos uma solução que é não só eficaz, ou seja, que corretamente resolve o problema (devolve o output correto para todos os casos de teste), mas também eficiente, ou seja, o seu tempo de execução é menor que o limite de tempo estabelecido.

E é aqui que se encontra a dificuldade (e interesse) das Olimpíadas: como fazer um programa correto e rápido para resolver um dado problema. Como podem ver no exemplo anterior, um programa mais rápido por vezes requer pensar de uma maneira diferente e de usar melhor a informação do problema. É por isso que dizemos que "não é preciso ter muita experiência de programação para ter sucesso nesta competição", pois sabendo os básicos de programação é suficiente, o desafio está em pensar em soluções eficientes para os problemas dados.

Noção de algoritmo e a sua análise

A discussão das secções anteriores motiva a introdução do conceito de algoritmo como abstração de um programa. Como viram, é útil poder descrever as ideias e passos de um programa sem ter de olhar para ele. Um algoritmo é exatamente isso, é uma sequência de instruções que indicam como processar um input. Esta definição parece ser a mesma que a definição que demos para um programa, mas notem que um algoritmo não está ligado a nenhuma linguagem de programação, é apenas uma forma abstrata de representar o que deve fazer um programa. Este conceito é útil pois por vezes queremos ser mais diretos a mencionar uma instrução a fazer, por exemplo, é muito mais simples perceber o que significa "percorremos todos os elementos da sequência" do que ler uma linha de código do tipo for (int i = 0; i < n; i++). De forma geral, quando começamos a resolver um problema, primeiro pensamos no algoritmo na nossa cabeça (ou no papel) e depois é que escrevemos um programa que implementa esse algoritmo.

Agora, dados dois algoritmos que resolvem (corretamente) o mesmo problema, qual é o mais eficiente? Obviamente que esta pergunta é muito difícil de responder no geral, mas para o caso do problema de exemplo dado no início deste artigo fizemos exatamente isso: o segundo algoritmo é claramente mais eficiente. No geral esta análise requer perceber qual a dependência da execução das várias instruções nos parâmetros do input e perceber quais dominarão o tempo de execução.

Neste website onde se encontram os vários artigos de introdução às Olimpíadas alojamos ainda um conjunto de outros artigos e guias sobre diferentes tópicos de resolução de problemas de programação. Um deles aborda exatamente este assunto de análise de algoritmos:

Artigo: Introdução à Análise de Algoritmos

Um artigo introdutório sobre análise de algoritmos.

É muito importante que leiam este artigo, é impossível resolver um problema sem saber o quão eficientes são as nossas ideias. Com o tempo, este processo ficará muito mais simples e analisar a eficiência de um algoritmo será quase instantâneo.

Sistema de pontos e subtarefas em problemas

Antes de passarmos ao próximo tema, vamos clarificar como funciona o sistema de pontos do Mooshak (ou seja, como são avaliadas as vossas submissões de programas). Cada programa é corrido com um vasto conjunto de casos de teste (o número de casos de teste depende de problema para problema). Cada caso de teste tem um input e o output correto respetivo e o programa submetido é corrido com cada input e se terminar no tempo limite estabelecido e devolver o output correto, então recebe os pontos atribuidos a esse caso de teste. Todos os problemas têm um máximo de 100 pontos, dai o resultado "100 Accepted" quando submetem um problema correto, significa que o vosso programa passou todos os casos de teste.

Adicionalmente, os casos de teste estão agrupados em subtarefas. Até agora nenhum dos problemas que vimos tiveram este agrupamento, mas todos os problemas das provas oficiais das Olimpíadas têm esta propriedade (e os restantes problemas deste artigos também a terão). Cada grupo de casos de teste tem um conjunto de restrições diferentes, por exemplo, para o problema introduzido no início deste artigo poderiamos ter um grupo de casos de teste a valer 40 pontos onde $N_1, N_2 \leq 100$ e um grupo a valer 60 pontos onde $N_1, N_2 \leq 100.000$. Isto significaria que o primeiro programa que fizemos obteria 40 pontos (pois passaria o primeiro grupo, mas excederia o tempo limite para o segundo) e o segundo programa 100 pontos.

A existência de subtarefas serve para dividir soluções intermédias (ou seja, que não são eficientes o suficiente para obter os 100 pontos). Assim, quando lerem um problema das Olimpíadas, leiam as subtarefas (que são referenciadas na secção "Restrições") e pensem quais resolve o potencial algoritmo que estão a considerar. Adicionalmente, certas subtarefas podem introduzir subproblemas do problema original que podem ser resolvidos com um algoritmo diferente, específico a essa subtarefa. Por exemplo, para o problema anterior podíamos ter uma subtarefa onde "todos as cartas do primeiro baralho têm um número par". Resumidamente, é muito importante ler as subtarefas existentes e pensar nelas.