Aula 01 - Tópicos básicos do C++

Bem vindos ao Bixecamp, o curso introdutório à programação competitiva do MaratonUSP! Nas primeiras aulas faremos uma introdução à linguagem C++, que será utilizada ao longo de todos os nossos encontros. Para além disso, é a linguagem mais utilizada nas competições, por ser muito eficiente em velocidade e dispor de uma biblioteca com vários recursos úteis, recomendamos que também a usem! Ao final dessa aula esperamos que você já seja capaz de resolver seus primeiros problemas.

Estrutura básica de um programa em C++

A estrutura inicial de um código em C++ para nós será sempre a mesma, vamos analisá-la abaixo:

#include <bits/stdc++.h>
using namespace std;

int main(){

}

Na primeira linha, estamos incluindo uma biblioteca que contém quase todas as funcionalidades da linguagem que usaremos ao longo do código, facilitando nossa vida. Nesse momento inicial, você não precisa se preocupar com isso.

Na segunda linha, definimos o uso de um namespace. Não se preocupe também em entender o que isso significa nesse momento, é um tópico bem mais avançado e é algo da sintaxe da linguagem, apenas nos poupa um certo trabalho.

Nas próximas linhas, temos a função principal do código. Estudaremos o que é uma função na quarta aula, mas nesse momento é importante saber que todo nosso código será escrito no espaço em branco dentro dessas chaves.

Em resumo, usaremos na maior parte do tempo essa estrutura como caixa preta, e para nós é suficiente! Mas para os entusiastas, há muita documentação disponível na internet, nossa sugestão é sempre utilizar o CPP Reference para consultas técnicas da linguagem. O site pode não parecer muito intuitivo num primeiro momento, mas fique à vontade para sempre pedir ajuda!

Variáveis

Uma variável é um objeto que possui um nome e armazena algum valor. Assim, sempre que quisermos armazenar algo, seja um número, uma palavra ou qualquer outro dado, faremos uso de uma variável. Para usar uma variável, precisamos antes declará-la, ou seja, criá-la:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int var = 2;
}

No exemplo acima, criamos uma variável do tipo int (que armazena números inteiros) cujo nome é var e guardamos nela o número 2. Não necessariamente precisamos atribuir um valor à ela no momento da declaração (somente int var; seria suficiente), mas cuidado ao usá-la sem ter feito uma atribuição antes! Situações estranhas podem acontecer. Observe também que colocamos um ; ao final da linha, ele indica o final do comando atual e é exigido pela linguagem.

Em C++, os tipos de variáveis que usaremos e os valores que podem assumir são:

• bool: true (verdadeiro) ou false (falso);
• int: Números inteiros no intervalo [−2.147.483.648, 2.147.483.647];
• long long: Números inteiros no intervalo [−9.223.372.036.854.775.808, 9.223.372.036.854.775.807];
• double: Números fracionados;
• char: Caractere (letras, números, caracteres especiais).

Exemplo de declaração dos tipos:

#include <bits/stdc++.h>
using namespace std;

int main(){
    bool verdadeiro = true;
    int inteiro = 2;
    long long inteirao = 10000000000;
    double fracionado = 2.5;
    char caractere = 'x';
}

Note que a atribuição do caractere deve ser feita utilizando aspas simples e utilizamos um . em números fracionários.

Entrada e saída

Para se comunicar com o usuário, usaremos os comandos cout e cin, que nos permitem escrever na saída padrão e ler na entrada padrão, respectivamente. No nosso caso, a saída padrão e entrada padrão será o terminal, através do qual o usuário poderá interagir com o programa.

Saída

Para escrever para o usuário, ou seja, escrever algo na tela, utilizamos o comando cout da seguinte maneira:

#include <bits/stdc++.h>
using namespace std;

int main(){
    cout << "Olá mundo!" << endl;
}

Qualquer texto que quisermos escrever deve ser colocado entre as aspas duplas. O comando endl indica uma quebra de linha, ou seja, indicamos ao programa que queremos pular para a próxima linha após a impressão.

Se quisermos imprimir uma variável a estrutura é bem parecida, mas apenas referenciado-a com seu nome, sem aspas. Podemos ainda imprimir texto e variáveis juntos através do mesmo comando:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int var1 = 2;
    cout << var1 << endl;
    
    int var2 = 3;
    cout << "Variável var1 = " << var1 << " e variável var2 = " << var2 << endl;
}

Sempre que quisermos intercalar entre texto e variáveis na impressão, ou mesmo entre uma sequência de variáveis, devemos utilizar <<.

Para a impressão de números fracionários, no início do cout podemos definir a quantidade de casas decimais a serem exibidas usando o comando fixed << setprecision(n), onde n é quantidade de casas que desejamos:

#include <bits/stdc++.h>
using namespace std;

int main(){
    double var1 = 3.14159, var2 = 3.0;
    cout << fixed << setprecision(10) << var1 << " = " << var2 << endl;
}

O resultado impresso será 3.1415900000 = 3.0000000000.

Entrada

Para ler do usuário, ou seja, receber alguma entrada, utilizamos o comando cin da seguinte maneira:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int var;
    cin >> var;
}

Note que a entrada do usuário precisa ser armazenada em algum lugar, logo precisamos utilizar uma variável! No exemplo acima, estamos lendo um número inteiro informado pelo usuário. Podemos ainda ler mais de uma variável em sequência:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int var1, var2;
    cin >> var1 >> var2;
}

Sempre que quisermos ler várias variáveis na leitura, devemos utilizar >>.

Operações aritméticas

Já vimos o uso do operador = para atribuição ao longo dos exemplos acima. Vamos agora ver os operadores aritméticos:

• Soma: utilizamos o operador + . Exemplo: a + b.
• Subtração: utilizamos o operador -. Exemplo: a - b.
• Multiplicação: utilizamos o operador *. Exemplo: a * b.
• Divisão: utilizamos o operador /. Exemplo: a / b.
• Módulo (resto): utilizamos o operador %. Exemplo: a % b.

Os operadores de multiplicação, divisão e módulo possuem precedência em relação aos operadores de soma e subtração. Para operadores com mesma precedência, a ordem da esquerda para a direita é respeitada. Podemos ainda usar parênteses para definir a procedência, como por exemplo (2 + 2) * 5 resultará em 20.

Tome muito cuidado também ao misturar tipos no uso dos operadores! Em especial na divisão, a divisão de inteiros sempre ignora a parte decimal, ou seja, sempre tomamos o piso. Por exemplo, 5 / 2 resultará em 2. Note que o operador da divisão é o mesmo tanto para a divisão de inteiros quanto usando números reais, o tipo das variáveis envolvidas é o que determina o tipo do resultado.

Compilação

Para executarmos nosso código, precisamos antes gerar um executável. Tal processo recebe o nome de compilação. No GNU/Linux, siga o passo a passo:

1. Salve seu código num diretório de sua escolha com a extensão .cpp. Por exemplo, podemos salvar o código como codigo.cpp. Faltou criatividade.
2. Usando o navegador de arquivos, vá até o diretório escolhido em que nosso código está salvo e abra um terminal no diretório (botão direito > "Abrir no terminal").
3. Utilize o seguinte comando no terminal para compilar o código: make [NOME DO ARQUIVO SEM EXTENSÃO]. No nosso exemplo, utilizaríamos o comando make codigo, gerando um novo arquivo de nome apenas codigo, nosso executável. Se tudo deu certo, nenhuma mensagem de erro será exibida.
4. Para executar o código, utilize no terminal o comando: ./[NOME DO EXECUTÁVEL]. No nosso exemplo, ./codigo.

Se você se encontrar preso dentro do código em execução, utilize CTRL+C para pará-lo e liberar o terminal.

No passo 3, se seu sistema acusar que não encontrou o comando make, então você não o possui instalado. Uma alternativa (além da possibilidade de instalar o GNU Make, fica a dica) é utilizar em seu lugar o comando g++ [NOME DO ARQUIVO SEM EXTENSÃO] -o [NOME DO EXECUTÁVEL]. No exemplo, g++ codigo.cpp -o codigo.

Você precisa de pelo menos 0 problems problemas.

Aula 02 - Condicionais e Loops

Estruturas condicionais e de repetição permitem que haja uma alteração no fluxo do código ou que haja uma automatização de operações.

Contudo, primeiramente, antes é necessário conhecer as operações relacionais e as lógicas, que servirão de start para essas estruturas.

Operações Relacionais

Operações relacionais são binárias, isto é, envolvem a comparação entre dois objetos por vez e retornam um valor booleano true ou false. Nesse caso, é possível comparar dois caracteres, duas strings, dois inteiros ou dois floats (embora suas representações decimais possam corroborar para alguns erros matemáticos). Em suma, é necessário que sejam do mesmo tipo.

Operações

• > Menor que
• < Maior que
• >= Maior ou igual a
• <= Menor ou igual a
• != Diferente a
• == Igual a

Note que uma operação de comparação de igualdade envolve a utilização de dois símbolos de igual "==". Ao passo que uma operação de atribuição, apenas um. Em outras palavras, dadas as variáveis a e b, a operação a = b apenas atribui o valor contido em b para a. E, se utilizada erroneamente em algum loop, na linguagem C++, a condição é automaticamente true.

Operações Lógicas

As operações lógicas podem ser binárias ou unárias, que envolvem dois valores booleanos e retornam um terceiro valor booleano. Ainda assim, pode haver composição de operações lógicas.

Além disso, essas operações são regidas por uma precedência. A priori, tem-se prioridade ao Not. Em seguida, o And. E, por fim, o Or. A menos que estejam protegidos por um par de parênteses. E, também, a ocorrência se dá da esquerda para a direita.

   int numero = 9;

   cout << ((numero < 3) && !(numero % 7 == 2) || (numero + 1 == 10));

Retorna um verdadeiro, sendo os booleanos
(false) && !(true) = (false) && (false) = false
E, também, (false) || (true) = true

Operações

• && And (E)
• || Or (Ou)
• ! Not (Não)

Tabelas Lógicas

As operações lógicas seguem alguns conjuntos de regras, conforme a álgebra de Boole.

And

• true and true = true
• true and false = false
• false and true = false
• false and false = false

Apenas quando ambos os valores são verdadeiros, a operação retorna verdadeiro.

Or

• true or true = true
• true or false = true
• false or true = true
• false or false = false

Apenas quando ambos os valores são falsos, a operação retorna falso.

Not

• not true = false
• not false = true

Esta é uma operação unária, e apenas inverte os valores booleanos.

Exemplos

   int numero = 5;
   cout << ((numero % 4 == 0) || (numero == 5) && (numero != 7)); // true

   int ano = 2024;
   string mes = "Março";
   cout << ano % 3 == 0 || mes == "Março" << endl; // true, em razão da segunda booleana

Estruturas Condicionais

Uma vez observadas as operações lógicas e as relacionais, agora, serão apresentadas as estruturas condicionais e as de repetição.

If e else

Essa é uma estrutura conjunta que, essencialmente, é composta por um if e um else. Ela serve para tratar de possíveis alterações no fluxo do código a depender, unicamente, da condição imposta dentro do if.

A primeira parte é dada pela palavra reservada if, sucedida por uma condição dentro de um par de parênteses. Assim, se tal condição for obedecida, o código contido no par de chaves a seguir é executado e, encerrado, não executa o else e segue o código.

   if( <condição> ){
       Bloco de comandos...;
   }

Mas, caso a condição não seja obedecida, a sequência executa automaticamente o else, uma estrutura complementar. Essa parte é composta pela palavra reservada else, sucedida por um bloco de comandos a serem executadas dentro do par de chaves.

   else{
       Bloco de comandos...;
   }

Exemplo

   int numero;
   cin >> numero;

   if(numero % 2 == 0){
       cout << numero << " é um numero é par" << endl;
   }
   else{
       cout << numero << " é um numero é ímpar" << endl;
   }

   return 0;

Se o número recebido em numero for par, o bloco de comandos internos a if é executado. Caso contrário, o que está após o else é executado.

Else if

Apesar de, essencialmente, a estrutura condicional ser baseada para funcionar em casos duais e disjuntos (Se obedece a condição, faça isso. Caso o contrário, faça isso), é possível estender a condição para mais casos.

Nesse sentido, existe a estrutura condicional else if, que possibilita que uma situação possa ser dividida em três ou mais casos. Essa parte deve estar após o if, mas, antes do else. Ela é composta da palavra reservada else if, sucedida por uma condição intermediária interna a um par de parênteses. Assim, caso a condição de if não seja verdadeira, mas, a de else if, sim, apenas o bloco de comandos internos a este serão executados.

   else if( <condição> ){
       Bloco de comandos...;
   }

Exemplo

   int numero;
   cin >> numero;

   if(numero > 0){
       cout << numero << " é um número positivo" << endl;
   }
   else if(numero < 0){
       cout << numero << " é um número negativo" << endl;
   }
   else{
       cout << numero << " é 0" << endl;


   return 0;
   }

Se o número recebido em numero for positivo, o bloco de comandos interno a if é executado. Caso contrário, se a condição intermediária de que o número é negativo for obedecida, então, o bloco de comandos de else if é executado. Finalmente, caso o número não seja nem negativo, nem positivo, então, ele é o 0. Portanto o bloco de comandos de else é executado.

else if é uma simplificação para condicionais compostas. Caso a primeira condição não seja correspondida, então, testa-se uma segunda. Ela serve como uma estrutura intermediária. Quando o else if é aplicado, em outras palavras, quer se dizer:

   int numero;
   cin >> numero;

   if(numero > 0){
       cout << numero << " é um número positivo" << endl;
   }
   else{
       if(numero < 0){
           cout << numero << " é um número negativo" << endl;
       }
       else{
           cout << numero << " é 0" << endl;
       }
   }

   return 0;

If e Else if

As estruturas condicionais têm a propriedade de alterar o fluxo do código, dando um tratamento diferente aos valores e situações que obedecem a condição imposta.

Nesse viés, é possível utilizar o if, sem a necessidade do else. Neste caso, apenas os valores com características específicas receberão um tratamento especial. E, após, todos os valores serão processados igualmente.

   int numero1;
   int numero2;
   int soma = 0;
   cin >> numero1;
   cin >> numero2;

   if(numero1 > 0){
       soma = soma + numero1;
   }
   if(numero2 > 0){
       soma = soma + numero2;
   }

   cout << "A soma dos números positivos é " << soma << endl;

Note que, se somente numero1 for positivo, será impresso apenas o valor dele. Caso somente numero2 for positivo, será impresso apenas o valor dele. Se ambos forem positivos, a soma deles será impressa. E, finalmente, se os números não forem positivos, a soma será 0

Ainda assim, para todos os casos, a última linha sempre será impressa.

Contudo, o else if e um else estão interligados a um if. Portanto, a implementação de um código somente com essas estruturas, sem um if, resultará num erro. Afinal, o else compreende todas as situações no caso em que a condição imposta não for obedecida.

   int numero;
   cin >> numero;

   else{
       cout << "Este número é " << numero << endl;
   }

Será impressa uma mensagem de erro e o código não será compilado.

Todavia, um if também pode ser sucedido por um else if, e não de um else. Em palavras mais curtas, isso compreende a situação anterior. Mas, em que a primeira situação é falsa.

   int valor;
   cin >> valor;

   if(valor == 8){
       cout << "É 8" <<  endl;
   }
   else if(valor == 12){
       cout << "É 12" << endl;
   }

   cout << "O valor foi verificado :)" << endl;

Também pode ser escrito como

   int valor;
   cin >> valor;

   if(valor == 8){
       cout << "É 8" <<  endl;
   }
   else{
       if(valor == 12){
           cout << "É 12" << endl;
       }
   }

   cout << "O valor foi verificado :)" << endl;

Estruturas de Repetição

Estruturas de repetição tem a função de automatizar uma fração do código, repetindo o mesmo processo n vezes.

While

A estrutura de repetição while serve para repetir um processo n vezes, enquanto uma condição imposta for verdadeira. Nesse caso, pode ser desde iterar um índice de 0 a n a colocar uma condição composta.

   int indice = 0;

   while( indice < 15){
       cout << indice << endl;
       indice++;
   }

Note que, primeiro, a condição é verificada, para, após ser executado o bloco de comandos.

O laço verifica se n é menor do que 0. Como n = 0, então, o laço se inicia. O valor é impresso e n é acrescido por um. Agora, n = 1. A condição é obedecida e o valor é impresso. Isso continua, com impressões e acréscimos, até que n seja igual a 15, quando a condição se torna falsa e o laço se encerra, dando prosseguimento ao código. Note que 15 não será impresso.

   char letra = 'a';
   while(letra != 's'){
       letra += 1;
   }

   int numero = 10;
   while(numero < 30 && numero % 7 == 0){
       cout << numero << endl;
       numero++;
   }

Loop Infinito

Uma preocupação bastante razoável quando se trabalha com o while é o loop infinito. A condição do while apenas verifica se ela ainda é válida, contudo, ela por si só não altera nada. Assim, caso a condição verificada seja sempre verdadeira, o código interno a while será sempre executado e o programa pode não parar.

   int numero = 0;

   while(numero== 0){
       cout << numero << endl;
   }

Dado n = 0, o laço se inicia. O programa imprime "0" infinitas vezes e nunca sairá do laço, pois n nunca é modificado e sempre será 0 (o que confirma a condição do laço).

Assim, uma solução é sempre alterar (incrementar ou decrementar) o iterador ao final do laço. Veja que mudar o valor no inicio, às vezes, pode não ser útil, alterando o valor verificado pelo laço.

   int numero = 0;

   while(numero== 0){
       cout << numero << endl;
       numero++;
   }

For

O for é uma simplificação do while. Nesta estrutura de repetição, o laço é executado executado n vezes. Sua construção é dada pela palavra reservada for sucedida por um conjunto que define o intervalo inteiro de ocorrências. A seguir, entre chaves, está o bloco de comandos a ser executado.

   for(<intervalo>){
       Bloco de comandos...
   }

Nessa estrutura, é mais raro ter loop infinito, pois o iterador é atualizado todos os ciclos.

Coloca-se dentro dos parênteses exatamente o intervalo que o for deve percorrer (início, fim, passo).

Exemplo

   int soma = 0;

   for(int i = 0, i < 2024, i++){
       soma = soma + i;
   }

   cout << soma << endl;

O laço irá iterar 2024 vezes, somando todos os valores de 0 a 2023. Note que quando i = 2024, o laço se encerra e se imprime a soma.

Break e Continue

A função break tem o propósito de forçar o encerramento de um laço de repetição, embora a condição envolvida da estrutura ainda seja verdadeira.

   int numero = 0;

   while(numero < 15){
       if(n == 3){
           break;
       }
       numero++;
   }

Note que o laço tem sua condição como verdadeira quando n < 15. Contudo, quando n for 3, o laço para em razão do break, embora 3 seja menor do que 15.

A função continue tem o objetivo de encerrar um ciclo do laço de repetição e executar um novo.

   int n = 0;

   while(n < 15){
       cout << n << endl;
       if(n == 3){
           n++;
           continue;
       }
       cout << n << endl;
       n++;
   }

Neste caso, o laço repita 15 vezes e imprime cada valor. Contudo, quando n for igual a 3, n é acrescido de um e continua o laço, sem imprimir o 3.

É recomendado ter cuidado com o continue e com o while. Se o iterador não fosse acrescido, o laço iria continuamente repetir, pois não seria igual a 3 sempre e criaria um novo loop.

Laços Encaixados

É possível combinar duas ou mais estruturas de repetição. Nesse caso, antes de ingressar num laço interno, o de fora tem seu iterador pausado e continua após o término do outro. Como se seguisse a ordem natural do fluxo do código.

   int i = 0, j = 0;

   while(i <= 10){
       while(j <= 10){
           cout << i << " * " << j << " = " << i*j << endl;
           j++.
       }
       i++;
   }

Esta estrutura imprime todas as multiplicações de 0 a 10. Enquanto i for igual a 0, este valor é fixado e o laço interno é executado, utilizando o mesmo i, mas, variando o j. Quando j for igual a 11, o laço interno se encerra e i é acrescido por um, entrando, novamente, no while interior.

Algumas aplicações interessantes tem a ver com varredura de matrizes, combinação bruta de pares num array e busca do valor mínimo.

Escopo

Estruturas condicionais possuem um escopo próprio. Isso significa que todas as variáveis criadas entre as chaves só existem enquanto o laço existir e a condicional for verdadeira. Nesta situação, tentar acessar essas variáveis do lado de fora pode acarretar num erro.

   for(int i = 0, i < 15; i++){
       int valor = 9;
   }

   cout << valor << endl; // Esta implementação resultará num erro, pois, a variável valor não existe mais.

Aplicações

Estruturas de repetição e condicionais são amplamente utilizadas. Alguns exemplos práticos são:

1. Fazer a leitura de "n" elementos.

   int n, x;
   vector<int> valores;

   cin >> n;

   for(int i = 0; i < n; i++){
       cin >> x;
       valores.push_back(x);
   }

Dado um n, recebe n valores e coloca-os num vector

1. Fazer a varredura de uma estrutura de dados.

   for(int i = 0; i < v.size(); i++){ // v é um vector
       cout << v[i] << endl;
   }   

Imprime todos os valores contidos em v.

1. Condicionar e processar um elemento com características específicas.

   int lo = 0;
   int hi = v.size() - 1;

   while(lo <= hi){
       int mid = (hi + lo)/2;
       if(v[mid] == x){
           cout << "Achei" << endl;
           break;
       }
       else if(v[mid] < x){
           lo = mid + 1;
       }
       else{
           hi = mid - 1;
       }
   }

Esta estrutura é uma implementação da busca binária. E ela utiliza laços e estruturas condicionais. Procura por um valor x dentro de um vector v. Se o encontrar imprime uma mensagem e para o while. Caso o contrário (se for menor ou maior), continua a busca, seguindo alguns critérios.

Você precisa de pelo menos 0 problems problemas.

Aula 03 - Arrays, matrizes e strings

Nessa aula, vamos analisar algumas estruturas comumente usadas para armazenar grandes quantidades de dados. Em especial, vamos focar em arrays, matrizes e strings.

Arrays

Os arrays são usados para armazenar um conjunto de variáveis. Assim, cada espaço do array corresponde a uma variável. Para inicializar um array, a estrutura padrão é: tipo nome[tamanho]. Por exemplo, podemos declarar um array que armazena o equivalente a 10 variáveis da seguinte forma:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int meu_array[10];
}

Ao declarar o array da forma da forma descrita acima, imagine que temos 10 variáveis enfileiradas que podemos utilizar sem ter que declarar elas uma por uma. Podemos acessar uma variável na posição i do array da seguinte forma: nome[i]. Por exemplo:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int meu_array[10];
    meu_array[2] = 23;
    cout << "O meu array na posicao 2 eh " << meu_array[2] << endl;
}

O código irá imprimir: O meu array na posicao 2 eh 23

Como vimos na aula passado, o comando for pode ser usado para simular repetições. Assim, ele se torna muito útil quando utilizamos arrays. Observe o código abaixo:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arraydeint[5] = {1,2,3,4,5};
    bool arraydebool[5] = {1,0,0,1,0};
    double arraydedouble[5] = {1.1, 2, 3.5, 4.3, 1.9};
    char arraydechar[5] = {'a', 'b', 'c', 'd', 'e'};

    for(int i = 0; i < 5;  i++){
        cout << arraydeint[i] << ' ';
    }
	cout << endl;
    for(int i = 0; i < 3; i++){
        cout << arraydechar[i] << ' ';
    }
	cout << endl;
}

Nesse código, ao imprimir os valores dos arrays, temos como saída:

1 2 3 4 5
a b c

Note que o array começa indexado no zero, ou seja, podemos acessar apenas as posições em que i assume valores de 0 até tamanho-1. Desse modo: arraydeint[0] = 1 e arraydeint[4] = 5. Por isso, se quisermos utilizar o array começado indexado no 1 ou se quisermos acessar a posição n, precisamos inicializar como: tipo nome[tamanho+1].

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, posicao;
    cin >> n;

    int a[n+1];

    cin >> a[0] >> a[1] >> posicao;
    
    for(int i = 2; i <= n; i++){
        a[i] = a[i-1] + a[i - 2];
    }
    cout << a[posicao] << endl;
}

No código acima, inicializamos um array de tamanho n+1 e lemos os valores a[0], a[1] e posicao. Depois, utilizamos um for e atribuímos um valor para a[i] tal que a[i] é a soma dos dois anteriores. Assim, imprimimos o valor que está na posição do array. Em particular, se atribuirmos n = 6, a[0] = 1, a[1] = 1 e posicao = 6, o array armazenará a sequência de fibonacci e imprimiremos a[6] = 13.

Um erro comum ao utilizarmos arrays é o erro Segmentation Fault, ele ocorre quando acessamos uma posição do array que não foi declarada. Por isso, ao usar algoritmos mais complexos é comum inicializarmos o array com um espaço extra. Por exemplo:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int tamanho;
    cin >> tamanho;

    int a[tamanho+10];

    cin >> a[tamanho];
    cout << a[tamanho] << endl;
}

Assim, evitamos o erro causado por acessar a posição tamanho sem querer.

Matrizes

As matrizes são tabelas que armazenam n x m variáveis. De maneira semelhante ao array, cada espaço da matriz corresponde a uma variável. Para inicializar uma matriz, a estrutura é: tipo nome_da_matriz[quantidade_de_linhas][quantidade_de_colunas]. Por exemplo:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[100][43];
}

Além disso, podemos acessar uma variável na posição i, j da matriz da seguinte forma: nome_da_matriz[i][j]. Por exemplo: #include<bits/stdc++.h> using namespace std;

int main(){
    int a[100][43];
    a[10][20] = 451;
    cout << a[10][20] << endl;
}

O código irá imprimir 451.

Considere o seguinte exemplo:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int minha_matriz[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> minha_matriz[i][j];
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << minha_matriz[i][j] + i << endl;
        }
    }
}

Escopo de arrays e matrizes

Há várias ocasiões em que queremos inicializar todos os valores do array ou de uma matriz como sendo 0. Uma forma de fazer isso é a seguinte:

Para o array:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int meu_array[n];
    for(int i = 0; i < n; i++){
        meu_array[i] = 0;
    }
}

Para a matriz:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int minha_matriz[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            minha_matriz[i][j] = 0;
		}
    }
}

Entretanto, há outra maneira de inicializar arrays e matrizes como zero: declarar as variáveis fora da int main():

Para arrays:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;

int array[MAXN];

int main(){
...
}

Para matrizes:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;

int matriz[MAXN][MAXN];

int main(){
...
}

Dessa vez, inicializamos a matriz globalmente, fora do int main(). Assim, todos os valores da matriz começaram como 0. Perceba que, até agora, tivemos que ler o tamanho do array e depois inicializar o array com seu tamanho. Já, no código acima, como não sabemos o tamanho da matriz, apenas declaramos uma quantidade grande suficiente para ser o tamanho matriz. Em outras palavras, inicializamos uma constante MAXN que vale 1e3 + 10 para ser o tamanho da matriz. Obs: 1e3 significa 10 elevado a 3.

Um exemplo é o seguinte código que imprime a matriz identidade:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;

int matriz[MAXN][MAXN];

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        matriz[i][i] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << matriz[i][j] << ' ';
        }
        cout << endl;
    }
}

Declaramos a matriz globalmente e mudamos os valores das posições i, i para 1. Logo, se a entrada for 3, ficamos com a matriz:

1 0 0 
0 1 0
0 0 1

Limite de memória

Quando usamos o truque descrito no tópico anterior, temos que tomar cuidado com o seguinte fato: há um limite por código para a quantidade de variáveis que podemos ter. Para a variável do tipo int esse limite costuma ser por volta de 5e7. Por isso, devemos tomar cuidado com o tamanho dos nossos arrays e matrizes. Um exemplo isso, é no código:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;

int matriz[MAXN][MAXN];

Apesar do valor da constante MAXN ser 1e3, o tamanho da matriz será MAXN x MAXN, o que é aproximadamente 1e6.

Caso o valor de MAXN fosse 1e5, o tamanho da matriz seria 1e10, o que causaria um erro ao tentar compilar o código.

Strings

Há casos em que queremos uma forma de armazenar uma palavra inteira no nosso código. Pensando computacionalmente, palavras são simplesmente um conjunto de caracteres. Desse modo, seria totalmente possível armazenar uma palavra da seguinte forma:

#include<bits/stdc++.h>
#define MAXN 112345
using namespace std;

int main(){
    char palavra[MAXN];
    int tamanho;
    cin >> tamanho;
    for(int i = 0; i < tamanho; i++){
        cin >> palavra[i];
    }
    for(int i = 0; i < tamanho; i++){
        cout << palavra[i];
    }
	cout << endl;
}

O código acima, ao receber como entrada: 8 Maratona

Vai imprimir: Maratona

Note que, nesse caso, é necessário que o problema passe o tamanho da palavra para que possamos saber a quantidade de iterações do for. Uma outra estrutura, que pode ser mais conveniente em alguns casos, é usar uma estrutura chamada de string.

As strings são capazes de armazenar uma palavra inteira. Além disso, usar strings nos permitem:

• Acessar um índice da string
• acrescentar caracteres no final da string
• Descobrir o tamanho da string

Para declarar uma string, escanear uma palavra e imprimir, fazemos o seguinte:

#include<bits/stdc++.h>
using namespace std;

int main(){
    string palavra;
    cin >> palavra;
    cout << palavra << endl;
}

Ao fazer isso, estamos guardando a sequência de caracteres passados na entrada na nossa variável palavra do tipo string e imprimimos o valor na tela.

Assim, com a entrada:

Maratona

A saída será:

Maratona

Note que não foi necessário passar o tamanho da string na entrada, nosso código já entende automaticamente que, um conjunto de caracteres seguidos serão uma string. Outra observação importante é que a string sempre guarda todos os caracteres seguidos e, quando duas sequências de caracteres são separadas por um espaço ou quebra de linha, o código interpretará como duas strings diferentes. Por exemplo:

#include<bits/stdc++.h>
using namespace std;

int main(){
    string palavra1, palavra2;
    cin >> palavra1;
    cin >> palavra2;
    cout << palavra1 << endl;
}

No código acima, se a entrada for: Maraton USP

A saída será apenas: Maraton

E o valor guardado na variável palavra2 será: USP

Também podemos querer alterar um valor de um caractere em uma string, observe o seguinte código:

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    s = "Maratona???";

    int tamanho = s.size();

    for(int i = 8; i < tamanho; i++){
        s[i] = '!';
    }

    cout << s << endl;
}

O código declara uma string s e muda o valor dessa variável para Maratona???. Depois, guarda o tamanho dela (quantidade de caracteres) na variável tamanho. Em seguida muda o valor da string para Maratona!!!. Note que as strings também são indexadas em zero.

Outra operação que podemos fazer é adicionar caracteres no final da string:

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    s = "abcde";

    int tamanho = s.size();

    s.push_back('!');
    s.push_back('!');
    s.push_back('!');
    s.push_back('a');
    s.push_back('2');
    s.push_back('g');

    cout << s << endl;
}

Ao usar o comando .push_back() com o caractere dentro dos parênteses, adicionamos o caractere no final da string; No código acima, será impresso: abcde!!!a2g

Aplicações

Agora, vamos estudar alguns usos das estruturas vistas nessa aula.

Vetor frequência

Considere o seguinte problema: Imprima quantas vezes cada dígito aparece como ultimo algarismo nos n primeiros números na sequência de fibonacci. A sequência de fibonacci, pode ser definida por:

• fib[0] = 1
• fib[1] = 1
• fib[i] = fib[i-1] + fib[i-2] para i ≥ 2.

Observe que precisamos descobrir quantas vezes cada dígito aparece. Assim, ao invés de inicializar dez variáveis para contar quantas vezes cada dígito aparece, podemos usar um vetor frequência, ou seja, um array de tamanho 10 que armazena quantas vezes cada dígito aparece:

#include<bits/stdc++.h>
using namespace std;

int digito[10];

int main(){
    int n; cin >> n;

    int fib[n];

    fib[0] = 1;
    fib[1] = 1;

    digito[1] = digito[1] + 2;

    for(int i = 2; i <= n; i++){
        fib[i] = fib[i - 1] + fib[i - 2];
        int ultimo = fib[i]%10;
        digito[ultimo]++;
    }

    for(int i = 0; i < 10; i++){
        cout << digito[i] << " ";
    }

}

Observe que no código acima, declaramos o array digito globalmente(fora do int main), o array digito[x] guarda quantas vezes o dígito x apareceu no final. Assim, ele começa com todos os valores zero e digito[x] aumenta em 1 todas vez que o resto da divisão por 10 de fib[i] é x.

Soma prefixo

Considere o seguinte problema:

1. Entrada: Dado um array A de tamanho n e uma variável t. Considere também que são dados t pares i, j com i ≤ j, que representam o intervalo [i, j]. Cada um dos valores são índices do array.

2. Saída: Calcule, para cada um dost intervalos i, j, a soma A[i] + A[i+1] + ... + A[j].

Veja que uma maneira de calcular a soma dos intervalos pedidos é fazendo um for de i até j e somando cada termo individualmente. Entretanto, se o tamanho n e o número de intervalos t forem grandes, esse código se torna ineficiente.

Uma maneira mais eficiente é usando uma soma de prefixos. Nesse algoritmo, iremos criar um array somaprefixo de tamanho n. Assim, iremos guardar no índice i a soma dos elementos de 1 até i. Desse modo, temos:

soma_prefixo[i] = A[1] + ... + A[i - 1] + A[i].

soma_prefixo[j] = A[1] + ... + A[j - 1] + A[j].

Portanto, se queremos a soma dos elementos de i até j, com i ≥ j e i > 0.

Basta realizarmos a subtração:

soma_prefixo[i] - soma_prefixo[j - 1] = A[j] + A[j + 1] + ... + A[i -1] + A[i].

Com isso, o código se torna mais eficiente, pois podemos calcular o valor da soma em cada intervalo com apenas uma operação ao invés de criar um for para cada operação.

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, t;
    cin >> n >> t;
    int A[n + 10];
    long long soma_prefixo[n + 10];
    soma_prefixo[0] = 0;
	
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        soma_prefixo[i] = soma_prefixo[i - 1] + A[i];
    }
    for(int it = 1; it <= t; it++){
        int j, i; cin >> j >> i;
		cout << soma_prefixo[i] - soma_prefixo[j - 1] << endl;
    }
}

Você precisa de pelo menos 0 problems problemas.

Aula 04 - Funções e Recursão

Essa aula começa tratando de funções, uma estrutura de extrema importância para a organização de códigos. Em seguida, falamos sobre um conceito ligado às funções: a recursão, que em minha opinião traz algumas das ideias mais bonitas existentes em programação e abre a mente a pensar de novas formas.

Funções: da matemática à programação

Para falar de funções em programação é possível inicialmente fazer um paralelo com a matemática. O que sabemos sobre funções matemáticas? Vejamos por exemplo a função f:R->R, f(x) = 3*x+10. Podemos tirar 4 observações:

• A função tem um domínio que específica quais valores de entrada são aceitos, pode-se pensar como o "tipo dos dados de entrada". Nesse caso os números reais.

• A função tem um contradomínio, pode-se pensar como o "tipo dos dados de saída". Nesse caso, novamente os números reais.

• A função requer um valor de entrada (x).

• A função realiza operações sobre o valor de entrada e retorna um valor de saída (3*x + 10).

É de se esperar que dois conceitos com o mesmo nome carreguem semelhanças, e é verdade, todas as características apresentadas acima existem de alguma forma nas funções da programação. Em C++ as funções podem receber informações, podem devolver informações e também é necessário especificar tanto os tipos dos dados de entrada, quanto o tipo dos dados de saída. Mais do que isso, existe uma ideia geral compartilhada daquilo que é uma função: um objeto que manipula dados, realiza operações e retorna um resultado.

Apesar das semelhanças, também é de se esperar que haverão diferenças. Uma função matemática é um objeto puramente teórico, enquanto qualquer linha de código atua diretamente em um computador. Funções em programação tem muito mais usos e são bem menos limitadas. Além de receber e retornar informações, nossas funções podem criar e alterar dados da memória do computador, podem trocar informações com o usuário e podem chamar outras funções. Além disso, não lidamos apenas com números, funções podem receber e retornar textos, caracteres, valores booleanos, arrays, arrays de múltiplas dimensões, e mais.

Estrutura de uma função

No C++ a estrutura e sintaxe básica de uma função é a seguinte:

tipo nome(tipo parametro1, tipo parametro2, ...){
	...

	return saida;
}

Como mostrado acima, começamos especificando o tipo da variável de retorno da função, então definimos seu nome e dentro dos parênteses os parâmetros que queremos que a função receba, assim como seus respectivos tipos. Então, dentro dos colchetes, escrevemos todas as operações que a função irá realizar e por fim retornos um valor (que deve ser do tipo previamente especificado).

Para tornar isso um pouco mais concreto vamos ver como ficaria a implementação de uma simples função que soma dois números:

int sum_(int a, int b){
	return a+b;
}

Uma vez tendo criado a função ela pode ser chamada em qualquer parte do programa: na função main, dentro de outras funções e até mesmo dentro de si mesma. Abaixo vemos um exemplo de como chamar uma função:

#include<bits/stdc++.h>

using namespace std;

int sum_(int a, int b){
	return a+b;
}

int main(){
	cout << sum_(1,1) << "\n";
	cout << sum_(-10,2) << "\n";
	
	int a = 20;
	cout << sum_(a, 6) << "\n";
}

// Output: 2
//         -8
//         26

Atenção: não passar os parâmetros requisitados pela função ou passar parâmetros de um tipo diferente dos pedidos irá resultar em um erro.

Mais funções: as várias possibilidades

Até o momento só mostramos uma função bem básica e ainda em um formato bem parecido com aquele das funções matemáticas, porém existem várias outras formas, como mostraremos aqui.

Antes de mais nada, uma função não precisa sequer receber parâmetros e nem mesmo retornar um resultado. Quando uma função não retorna nada, no lugar de declarar o tipo da variável de retorno, escrevemos a palavra void, como no exemplo abaixo:

void hi(){
	cout << "Hi ;)\n";
}

A maior parte dos tipos de varíaveis (como int, float, bool, char, etc...) que já conhecemos, ao terem uma instância declarada na main e passada como parâmetro para uma função, não são alterados pela função. Ao invés disso, a função cria uma cópia interna do valor da variável. Exemplo:

#include<bits/stdc++.h>

using namespace std;

void teste(int x){
	x += 10;
	cout << x << " ";
}

int main(){
	int x = 0;
	test(x);
	cout << x << "\n";
}

Esse programa irá imprimir '10 0' indicando que o valor da variável x pertencente a função foi alterada, mas a variável x declarada dentro da main manteve seu valor.

Porém essa propriedade não vale para qualquer tipo, como é o caso de vários tipos e estruturas que veremos mais para frente. Existe uma estrutura de dados em particular que vimos que também não segue essa propriedade: os arrays.

#include<bits/stdc++.h>

using namespace std;

void range_sum(int[] arr, int start, int end, int k){
	for(int i = start; i < end; i++){
		arr[i] += k;
	}
}

int main(){
	int[10] test_arr = {1,2,3,4,5,6,7,8,9,10};

	range_sum(test_arr, 3, 7, 5);

	for(int i = 0; i < 10; i++){
		cout << arr[i] << " ";
	}
}

//Output: 1 2 3 9 10 11 12 8 9 10

Como podemos ver, apesar da função não ter retornado nada, ainda extraímos valores dela de certa forma. Essa função adiciona k a todos os elementos entre os índices start e end de qualquer que seja o arr que passarmos para ela.

Por fim, só para provar que funções não lidam apenas com números, aqui está uma função que recebe uma string e a retorna a mesma string, mas invertida:

string reverse_string(string s){
	for(int i = 0; i < s.size()/2; i++){
		char x = s[i];
		s[i] = s[n-1-i];
		s[n-1-i] = x;
	}

	return s;
}

Escopo de variáveis

Como mostrado anteriormente, existem variáveis que só existem dentro de uma função e outras que só existem fora dessa mesma função. Para finalizar então essa parte de funções, iremos buscar entender melhor como isso funciona e quais variáveis podem ser acessadas de onde.

As variáveis podem ser classificadas em dois grupos: variáveis locais e variáveis globais. Até agora só vimos variáveis locais: variáveis declaradas dentro da main e que portanto só existem dentro da main; parâmetros de funções, que só existem dentro de suas funções; e variáveis declaradas dentro de funções, que também só existem dentro de suas funções. Além disso temos as variáveis globais, que declaramos fora da main e fora de qualquer função. Essas variáveis podem ser acessadas em qualquer porção do código. Aqui vai uma ilustração disso:

#include<bits/stdc++.h>

using namespace std;

int variavel_global = 1;

void f(int parametro){
	int variavel_da_função = 2;

	// correto
	cout << parametro << "\n";
	cout << variavel_da_funcao << "\n";
	cout << variavel_global << "\n";

	//errado
	//cout << variavel_da_main << "\n";
}

int main(){
	int variavel_da_main = 3;
	
	f(4);

	// correto
	cout << variavel_da_main << "\n";
	cout << variavel_global << "\n";

	//errado
	//cout << parametro << "\n";
	//cout << variavel_da_funcao << "\n";
}

Output: 4
		2
		1
		3
		1

Exercício

1. Criar uma função que recebe um número inteiro como parâmetro e retorna um valor booleano dizendo se ele é primo.

2. Criar outra função que recebe um número inteiro n e retorna todos os primos de 1 a n, aplicando a primeira função.

Solução (spoiler):

#include<bits/stdc++.h>

using namespace std;

bool isPrime(int num){
	bool out = true;
	for(int x = 2; x <= sqrt(num); x++){
		if (num % x == 0){
			out = false;
			break;
		}
	}
	
	return out;
}

void print_primes(int n){
	for(int num = 2; num <= n; num++){
		if (isPrime(num)){
			cout << num << " ";
		}
	}
}

int main(){
	print_primes(10);
}	

Recursão

Antes de entrar a fundo em recursão é bom ter em mente: recursão não é apenas um conceito útil e bonito, é uma forma de pensar. Muitas vezes você pode acabar resolvendo um problema sem usar recursão na implementação do código, mas usando recursão em cada etapa do seu raciocínio para chegar lá. Não apenas aprenda recursão, aprecie a capacidade de abordar problemas de uma forma diferente que ela proporciona e todas as ideias que a orbitam.

Dito isso, antes que a coisa fique complicada vamos ter claro em mente o conceito super simples que define o que é recursão: Chamar uma função dentro de si mesma. Tendo feito isso você já está trabalhando com recursão. Podemos ver abaixo o exemplo mais simples possível:

void f(){
	f();
}

Essa é tecnicamente uma função recursiva, o problema é que o único propósito que ela realiza é quebrar seu programa e potencialmente explodir seu pc ao criar uma sucessão infinita de chamadas.

Com esse exemplo já é possível perceber que está faltando uma parte fundamental de funções recursivas: uma condição de parada. Podemos então tentar consertar a função anterior:

void f(int x){
	if (x == 0){
		return;
	}
	
	return f(x-1);
}

Agora ao invés de fazer infinitas chamadas essa função fará x chamadas e então parará (uma função não executa as linhas que faltam ao atingir um return). Embora não seja mais catastrófica, a função continua sem muito uso, vamos ver então um exemplo muito mais comum de recursão, uma função que calcula e retorna o valor do n-ésimo elemento da sequência de Fibonacci:

	int fib(int n){
		if(n == 1 or n == 2){
			return 1;
		}

		return fib(n-1) + fib(n-2);
	}

A própria definição da sequência de Fibonacci é que f(n) = f(n-1) + f(n-2), então é bastante natural implementá-la de forma recursiva, e é claro, precisamos ter o que chamamos de caso base (condição de parada) para que a função não comece a ir aos negativos e fique rodando para sempre. Sabemos que os primeiros dois elementos da sequência de Fibonacci tem valor 1, então eles formam nosso caso base.

Tudo o que fizemos pareceu bastante natural e intuitivo para a função que queríamos implementar, porém como veremos em seguida, os fundamentos por trás dela não se aplicam apenas ao Fibonacci, mas a qualquer função recursiva.

Estrutura básica de problemas recursivos

A condição necessária para que recursão possa ser aplicada em qualquer que seja o problema é o estabelecimento de uma relação entre cada possível estado/valor dos parâmetros da função e outros mais primitivos. No caso do Fibonacci a relação é f(n) = f(n-1) + f(n-2), onde n é o valor atual que queremos encontrar e n-1 e n-2 seriam o que descrevemos como valores mais primitivos, ou seja, "mais próximos" dos casos base. E temos então a segunda parte de qualquer programa com recursão, os casos base.

Vamos ver outro exemplo então, digamos que queremos implementar uma função que calcula o fatorial de x de forma recursiva. Responda então as seguintes questões: Qual é a relação recursiva mais simples que podemos estabelecer entre x e possíveis valores que o compõe? Qual é o caso base?

Solução: A relação recursiva mais simples seria f(x) = x*f(x-1) e o caso base seria f(0) = 1.

Implementação:

int factorial(int x){
	if (x == 0){
		return 1;
	}

	return x * f(x-1);
}

Desafios (acompanhe as soluções)

Agora que temos uma boa ideia dos princípios por trás da recursão, vamos tentar colocar isso em prática com problema difíceis, em que as relações entre estados nem sempre são tão fáceis de estabelecer e estabelecer corretamente.

Caminhos em uma grade

Você tem uma grade de NxM de tamanho. Começando do ponto superior esquerdo, movendo-se apenas uma posição em cada passo e se movendo apenas para direita ou para baixo em casa passo, você deve contar a quantidades de caminhos diferentes com que você pode chegar no ponto inferior direito.

S X O O O
X O O O O
O O O O O
O O O O O
O O O O E

Lembre-se, busque estabelecer uma relação entre diferentes estados da função. Para isso, primeiro identifique quais serão os parâmetros que a função receberá, então crie uma relação a partir deles.

Dica 1: Os parâmetros serão x,y indicando que você quer que a função retorne a quantidade de formas de chegar de 1,1 (o inicio) até x,y (variações dessa implementação são possíveis, mas a ideia principal permanece a mesma). Sabendo disso, o valor inicial de x,y será n,m.

Dica 2: Pense em um caminho válido, quais posições podem ser as imediatamente anteriores ao final?

Dica 3: Só é possível chegar na posição x,y a partir das posições x-1,y e y-1,x

Com as informações dadas nas dicas acima podemos concluir que a relação recursiva presente nesse problema é f(x,y) = f(x-1,y) + f(y,x-1). Quanto aos casos base, sabemos que só existe um caminho para chegar em qualquer elemento das bordas, então se x ou y valem 1 retornamos 1. Isso nos leva a seguinte implementação:

int paths(int x, int y){
	if (x == 1 or y == 1){
		return 1;
	}
	
	return paths(x-1,y) + paths(x,y-1);
}

Torre de Hanoi

Você tem 3 estacas e n discos, todos de tamanhos diferentes entre si. Inicialmente todos os discos se encontram na primeira estaca, organizados com o maior mais embaixo e menor mais em cima. Seu objetivo é descrever uma sequência de movimentos (exemplo de movimento: 1 3 - indica que você quer mover o disco no topo da estaca 1 para o topo da estaca 3) tal que todos os discos sejam transferidos para a última estaca, seguindo as seguintes regras: você só pode mover o disco no topo de cada estaca e você não pode posicionar um disco em cima de outro menor que ele.

Ilustração com 3 discos:

   ||          ||          ||
  oooo         ||          ||
 oooooo        ||          ||
oooooooo       ||          ||

Como é possível dividir essa tarefa em etapas de forma que consigamos implementar uma solução recursiva?

Tente experimentar um pouco como solucionar os casos mais simples manualmente e veja se consegue tirar informações disso.

Dica 1: O primeiro passo para resolver o problema é conseguir passar o maior disco para o final, pois nenhum disco poderá permanecer lá até que todos os discos maiores que ele já estejam posicionados. Use essa informação.

Dica 2: A única forma de passar o maior disco para o final é primeiro transferir todos os outros discos para estaca do meio.

Dica 3: Uma vez tendo passado o maior disco para o final o problema se torna o mesmo, porém com um disco a menos, pois o maior disco já está na posição final e qualquer disco pode ser colocado em cima dele, então não há motivo para movê-lo e teremos uma única pilha contendo todos os outros discos.

Solução: usando as informações deduzidas nas dicas é possível perceber que a solução pode ser modelada em 3 etapas da seguinte forma:

1. Mover os n-1 menores discos para estaca do meio (corresponde a resolver o mesmo problema para n-1)

2. Mover o maior disco para o final

3. Mover os n-1 menores discos para estaca final (corresponde a resolver o mesmo problema para n-1 novamente)

Como caso base temos que caso n seja igual a zero não precisamos realizar nenhuma ação.

Implementando tudo, chegamos no seguinte código:

void hanoi(int n, int start, int mid, int end){
	if (n == 0){
		return;
	}
	
	hanoi(n-1, start, end, mid);

	cout << "Move from " << start << " to " << end << "\n";

	hanoi(n-1, mid, start, end);
}

Exercícios

Se quiser continuar treinando, acesse essa planilha e entre na aba "Funções e Recursão" para encontrar outros problemas interessantes sobre o assunto: bit.ly/bixecampusp2024

Você precisa de pelo menos 0 problems problemas.

Aula 05 - Busca binária, ordenação e complexidade

Já perceberam que todo problema tem um limite de tempo para concluir sua execução? Já receberam o veredito TLE (Time Limit Exceeded)? Agora vamos adquirir consciência da eficiência de tempo dos nossos códigos e saberemos dizer quando ele é rápido ou lento. Além disso, vamos ainda estudar algoritmos de ordenação e uma nova técnica: a busca binária.

Complexidade

A eficiência de tempo de um algoritmo é parte importante da programação competitiva. Nós podemos estimar quanto tempo nosso algoritmo leva para executar a partir da sua complexidade.

Fazemos isso estimando o número de operações.

Exemplos

Soma de dois números

int soma(int a, int b) {
    return a + b; 
}

Realiza apenas 1 operação independente dos valores a e b. Dizemos então que a função é constante.

Troca de variáveis

int main () {
    int x1 = 20;
    int x2 = 24;
    
    // Troca x1 e x2
    int temp = x1;
    x1 = x2;
    x2 = temp;
    
    cout << "x1: " << x1 << ", x2: " << x2 << endl ;
}

Output: x1: 24, x2: 20 Realiza 6 operações independente de x1 e x2, também é constante.

Daqui em diante consideraremos todos os blocos de código constantes como sendo uma única operação.

Soma inteiros de 1 até n

int soma_inteiros(int n) {
    int soma = 0;
    for (int i = 1; i <= n; i++) {
        soma = soma + i;
    }
    return soma;
}

Não é constante pois a quantidade de operações depende da entrada n. Número de operações da função: 1 + n

Missing number

bool visto[200005];
int n; cin >> n;
for (int i = 1; i <= n; i++)  {
    visto[i] = false;
}
for (int i = 0; i < n-1; i++) {
    int a; cin >> a;
    visto[a] = true;
}
for (int i = 1; i <= n; i++)  {
    if (!visto[i]) {
        cout << i << endl;
        break;
    }
}

Número de operações no pior caso = 1 + n + (n-1) + n

Soma de elementos de uma matriz quadrada n por n

int soma_matriz_quadrada(int matriz[MAXN][MAXN], int n) {
    int soma = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            soma = soma + matriz[i][j];
        }
    }
    return soma;
}

Número de operações = 1 + n^2

Soma de elementos de uma matriz n por m

int soma_matriz(int matriz[MAXN][MAXM], int n, int m) {
    int soma = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            soma = soma + matriz[i][j];
        }
    }
    return soma;
}

Número de operações = 1 + n . m

Verificar se n é potência de 2

bool eh_potencia_de_dois(int n) {
    while (n > 1) {
        if (n % 2 == 0) {
            n = n / 2;
        }
        else {
            return false;
        }
    }
    return true;
}

Número de operações no pior caso = log n

Notação O grande

Usamos essa notação para descrever a complexidade de um algoritmo. Ela representa o limite superior de como nosso algoritmo se comporta no pior caso. Com ela é possível comparar a eficiência de diferentes algoritmos e estruturas.

Escrevemos O( f(n) ), onde f(n) é uma função que indica o número de operações do algoritmo em relação ao tamanho da entrada.

É uma ordem de grandeza, não o valor exato das operações do algoritmo.

Regras da notação O

• Ignoramos as constantes.
  • 9999n é O(n)
  • n^3+500 é O(n^3)
  • n+n/2 é O(n)
• Se temos somas com expoentes diferentes para uma mesma variável, a complexidade final será a maior delas.
  • n^2+2024n é O(n^2)
  • 9n+2 é O(n)
• Quando temos diferentes fatores, a complexidade terá diferentes variáveis.
  • 3n + 10m é O(n+m)

Complexidade dos exemplos

soma(int a, int b)

• Número de operações = 1
• O(1)

Troca de variáveis

• Número de operações = 6
• O(1)

soma_inteiros(int n)

• Número de operações: 1+n
• O(n)

Missing number

• Número de operações = 1 + n + (n-1) + n
• O(n)

soma_matriz_quadrada(int matriz[], int n)

• Número de operações = 1 + n^2
• O(n^2)

soma_matriz(int matriz[], int n, int m)

• Número de operações = 1 + n . m
• O(n . m)

eh_potencia_de_dois(int n)

• Número de operações no pior caso = log n
• O(log n)

Definição formal

Sejam f(n) de g(n) funções dos inteiros nos reais.

Dizemos que f(n) é O( g(n) ) se existem constantes positivas c e n0 tais que para todo n >= n0, f(n) <= c . g(n)

Imagem para visualização da definição

Classes de complexidade comuns

  Classe   |      Nome
O(1)       |  constante  
O(log n)   |  logarítmico  
O(n)       |  linear      
O(n log n) |  n log n   
O(n²)      |  quadrático
O($2^n$)   |  exponencial  
O(n!)      |  fatorial   

Aqui um gráfico de comparação das complexidades

No geral, evitamos soluções quadráticas ou piores e buscamos soluções lineares ou melhores.

Busca de elementos

Em uma array qualquer, como podemos verificar se ele contém um valor x? Exemplo:

int numeros[8] = {12, 11, 3, 4, 6, 4, 11, 10};

Uma forma é olhar para cada elemento do vetor a procura de x. Chamamos de busca sequencial. A função abaixo tem complexidade O(n).

bool contem(int numeros[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (numeros[i] == x) {
            return true;    
        }
    }
    return false;
}

E se tivéssemos uma array ordenada?

int numeros[8] = {3, 4, 4, 6, 10, 11, 11, 12};

A busca sequencial também funciona, mas como usar a informação da ordem ao nosso favor?

Exemplo do dicionário: Imagine que temos um dicionário q queremos encontrar a palavra "maratona" nele. Como fazemos? Com certeza não olhamos palavra por palavra desde a letra A. Para otimizar nosso tempo, fazemos algo parecido com o seguinte:

• Abrimos em uma página e olhamos uma palavra.
• Se a palavra é "maratona", eba! Encontramos.
• Se a palavra é lexicograficamente menor que "maratona", descartamos ela e as palavras em posições anteriores.
• Se a palavra é lexicograficamente maior que "maratona", descartamos ela e as palavras em posições adiante.
• Repete para as palavras restantes.

Busca binária

Isso é uma busca binária! Agora faremos semelhante com a nossa array.

int numeros[8] = {3, 4, 4, 6, 10, 11, 11, 12};

Guardamos quatro valores:

• x: o elemento que procuramos.
• ini: posição inicial do intervalo em consideração.
• fim: posição final do intervalo em consideração.
• mid: posição central do intervalo (ini+fim) / 2

Começamos com ini = 0 e fim = n-1

int arr[8] = {3, 4, 4, 6, 10, 11, 11, 12};

ini = 0;
fim = 7;

• Calcula mid
• Se arr[mid] == x, retorna mid
• Se x < arr[mid], o intervalo passa a ser [ini, mid-1]
• Se arr[mid] < x, o intervalo passa a ser [mid+1, fim]
• Repete enquanto ini <= fim

A complexidade da busca binária é O(log n)! Para efeito de comparação, em uma array de tamanho 1.000.000 a busca binária visita no máximo apenas cerca de 20 valores para encontrar (ou decidir que não existe) um elemento enquanto a busca sequencial poderia eventualmente percorrer todos os 1.000.000 elementos.

Podemos implementar a busca binária de forma iterativa ou recursiva. Veremos elas a seguir:

Busca binária iterativa A função retorna uma posição de x no array ou -1 se x não foi encontrado.

int busca_binaria_iterativa(int arr[], int n, int x) {
    int ini = 0, fim = n-1;

    while (ini <= fim) {
        int mid = (ini+fim) / 2;
        if (arr[mid] == x)
            return mid;
        
        if (x < arr[mid])
            fim = mid-1;
        else // arr[mid] < x
            ini = mid+1;
    }
    return -1;
}

Busca binária recursiva A função retorna uma posição de x no array ou -1 se x não foi encontrado.

int busca_binaria_recursiva(int arr[], int x, int ini, int fim) {
    if (fim < ini)
        return -1;
    
    int mid = (ini+fim) / 2;
    
    if (x < arr[mid])
        return busca_binaria_recursiva(arr, x, ini, mid-1);
    else if (arr[mid] < x)
        return busca_binaria_recursiva(arr, x, mid+1, fim);
    else // arr[mid] == x
        return mid;
}

Funções de busca binária do C++

A biblioteca do C++ possui algumas funções de busca binária já implementadas. São elas:

• binary_search(iteradorIni, iteradorFim, x): retorna true se x é encontrado e false caso contrário.
• lower_bound(iteradorIni, iteradorFim, x): retorna um iterador para o primeiro elemento em [iteradorIni, iteradorFim) maior ou igual a x.
  • Retorna um iterador que aponta para uma posição depois do último elemento quando todos os elementos são menores que x.
• upper_bound(iteradorIni, iteradorFim, x): retorna um iterador para o primeiro elemento em [iteradorIni, iteradorFim) estritamente maior que x.
  • Retorna um iterador que aponta para uma posição depois do último elemento quando todos os elementos são menores ou iguais a x.

Atenção: iteradorIni e iteradorFim não são os índices da array! São o próprio endereço de memória do inicio e final do intervalo desejado para fazer a busca. A seguir temos um exemplo de como utilizar essas funções.

int n = 16, x = 21;
int arr[n] = {0,  4,  4,  6,  9, 13, 14, 17, 18, 18, 18, 18, 19, 21, 23, 25};
        
if (binary_search(arr, arr+n, x))
    cout << x << " encontrado!" << endl;
else
    cout << x << " nao encontrado :(" << endl;

x = 18;
auto low = lower_bound(arr, arr+n, x);

if (low-arr < n) { // Verifica se não retornou um apontador para arr[n]
    cout << "lower bound de " << *low; // 18
    cout << " encontrado na posicao " << low-arr << endl; // 8
}

auto upp = upper_bound(arr, arr+n, x);
if (upp-arr < n) { // Verifica se não retornou um apontador para arr[n]
    cout << "upper bound de " << *upp; // 18
    cout << " encontrado na posicao " << upp-arr << endl; // 12
}

Busca binária na resposta

Usaremos a lógica da busca binária para descobrir a resposta do nosso problema. Aqui a ideia é "chutar" uma resposta e então verificar se ela é válida.

O "chute" é feito a partir de uma busca binária entre o valor mínimo e máximo do problema. Perceba que não precisamos necessariamente construir a array para buscar o chute.

É comum que essas soluções sejam O(n log n)

• n para a verificação de cada chute.
• log n para a busca binária dos chutes.

Problema: Dado x quadrado perfeito, encontrar a raíz quadrada de x (sem usar a função sqrt()) Exemplo: x = 25

Sabemos que a raíz será um inteiro entre 1 e 25, então começamos com ini = 1 e fim = 25

• Chute = (1+25) / 2 = 13
• 13*13 = 169 que é maior que 25. Então podemos descartar todos os valores maiores que 13. Procuramos agora um valor entre 1 e 13.
• Chute = (1+13) / 2 = 7
• 7*7 = 49 que é maior que 25. Procuramos agora um valor entre 1 e 7.
• Chute = (1+7) / 2 = 4
• 4*4 = 16 que é menor que 25. Procuramos agora um valor entre 4 e 7.
• Chute = (4+7) / 2 = 5 (divisão inteira)
• 5*5 = 25 o valor que queríamos. Encontramos nossa resposta, 5.

Também é possível fazer isso para encontrar raízes não inteiras como veremos a seguir.

Busca binária em intervalo real

Se estamos trabalhando com um intervalo real, iremos usar double e a imprecisão do computador pode nos trazer problemas depois de muitas divisões.

Definimos eps um número bem pequeno para ser nossa margem de erro nas comparações de igualdade.

Problema: Dado um real x >= 1, encontrar a raíz quadrada de x (sem usar a função sqrt())

double encontra_raiz(double x) {
    double eps = 1e-9; // Esse valor pode ser alterado de acordo com a precisao desejada.
    double ini = 0, fim = x;
    
    while (ini < fim+eps) { // ini <= fim
        double mid = (ini+fim) / 2;
        double quad = mid*mid;
        
        if (x-eps < quad and quad < x+eps) // x == quad
            return mid;
        else if (x < quad)
            fim = mid;
        else // quad < x
            ini = mid;
    }
}

Ordenação

Agora que sabemos a importância da ordenação a pergunta é: como ordenar? Existem alguns algoritmos de ordenação, aqui veremos 3 deles:

• Insertion sort
• Mergesort
• Quicksort

Insertion sort

Para cada elemento x de uma array não-ordenada de tamanho n posicionamos ele corretamente em uma subarray ordenada.

Consideremos que a array está ordenada até a posição j-1. Começamos com j=1, ou seja, a array está ordenada no intervalo [0, 0].

O passo a passo é:

• Atribuir x = arr[j];
• Copiar os elementos de arr[j-1] ''para frente'' até encontrar um elemento menor ou igual a x.
• Posicionar x no lugar certo.
• Incrementar j.
• Repetir até que j = n.

Animação de um exemplo do Insertion sort

Implementação do Insertion sort

void insertion_sort(int arr[], int n) {
    for (int j = 1; j < n; j++) {
        int x = arr[j];
        int i = j-1;
        
        while (arr[i] > x and i >= 0) {
            arr[i+1] = arr[i];
            i--;
        }
        
        arr[i+1] = x;
    }
}

Complexidade: O(n^2)

Mergesort

Usa o princípio da Divisão e Conquista. Reduzimos nosso problema em vários subproblemas que quando combinados formam a solução final. A solução é recursiva.

• Ordena recursivamente a primeira metade.
• Ordena recursivamente a segunda metade.
• Com as duas sub-arrays ordenadas, combinamos elas na array original. (função merge)

Caso base:

• A array possui apenas 1 elemento, ou seja, já está ordenada.

A função merge

Dadas duas arrays ordenadas A e B, a função merge constrói uma única array arr ordenada com os todos os elementos.

Guardaremos três índices: i com a posição atual de A, j com a posição atual de B, k com a posição atual de arr.

• Copia em arr[k] o menor valor entre A[i] e B[j].
• Incrementa o índice que continha o menor valor.
• Incrementa k.
• Repete até chegar ao fim de A ou B.
• Copia os elementos restantes em arr.

Animação de um exemplo do Mergesort

Implementação da função Merge

void merge(int arr[], int p, int q, int r) { // arr[p..q] e arr[q+1..r] estao ordenadas.
    int n1 = q - p + 1;
    int n2 = r - q;
    int A[n1], B[n2];
    for (int i = 0; i < n1; i++) A[i] = arr[p+i];
    for (int i = 0; i < n2; i++) B[i] = arr[q+1+i];
    int i = 0, j = 0, k = p;
    while (i < n1 and j < n2) {  // Copia em arr[k] o menor valor entre A[i] e  B[j] e incrementa o indice que continha o menor valor.
        if (A[i] < B[j]) {
            arr[k] = A[i]; i++; }
        else {
            arr[k] = B[j]; j++; }
        k++;
    }
    while (i < n1) { // Copia os elementos restantes em arr.
        arr[k] = A[i];
        i++; k++;
    }
    while (j < n2) {
        arr[k] = B[j];
        j++; k++;
    }
}

Implementação do Mergesort

void mergesort(int arr[], int ini, int fim) {
    if (ini == fim) return;

    int mid = (ini+fim) / 2;

    mergesort(arr,   ini, mid);
    mergesort(arr, mid+1, fim);

    merge(arr, ini, mid, fim);
}

Complexidade:

• Função merge: O(n)
• Mergesort: O(n log n)

Quicksort

Também usa o princípio da divisão e conquista.

• Escolha um elemento p qualquer de arr para ser o pivô.
• Posicione todos os elementos x < p à esquerda do pivô e todos os elementos y > p à direita do pivô. (função particione)
  • Isso significa que p está na posição correta em relação à array ordenada final.
• Chama recursivamente para os elementos antes de p.
• Chama recursivamente para os elementos depois de p.

Caso base:

• A array tem menos de dois elementos, ou seja, já está ordenada.

A função Particione Consideramos [ini, fim] como o intervalo que estamos trabalhando. p é o elemento pivô.

Existem várias formas de escolher o pivô. Aqui escolhemos o elemento mais a direita, ou seja p = arr[fim].

Guardamos índices i, j tais que:

• Todo elemento em [ini, i] é menor ou igual a p.
• Todo elemento em [i+1, j-1] é maior que p.

Iniciamos com i = ini-1 e j = ini.

• Se arr[j] > p, incrementa j.
• Se arr[j] <= p, troca arr[j] com arr[i+1]. Incrementa i e j.
• Repete até que j == fim;
• Troca p com arr[i+1].

Implementação do Particione A função retorna um inteiro p tal que todo elemento em arr[ini..p-1] é menor ou igual a arr[p] e todo elemento em arr[p+1..fim] é maior que arr[p].

int particione(int arr[], int ini, int fim) {
    int i = ini-1;
    int pivo = arr[fim];

    for (int j = ini; j < fim; j++) {
        if (arr[j] <= pivo) {
            swap(arr[j], arr[i+1]); // Troca
            i++;
        }
    }
    swap(arr[fim], arr[i+1]);       // Troca
    int p = i+1;
    return p;
}

Complexidade: O(n)

Implementação do Quicksort

void quicksort(int arr[], int ini, int fim) {
    if (fim <= ini) return;

    int p = particione(arr, ini, fim); // O(n)

    quicksort(arr, ini, p-1);
    quicksort(arr, p+1, fim);
}

Complexidade: O(n log n) no geral.

• Pior caso: quando a array já está ordenada, fica O(n^2)
• É resolvido com uma melhor escolha de pivô, por exemplo escolhendo um pivô aleatório.

Mergesort vs. Quicksort

Qual usar, sabendo que eles têm a mesma complexidade? Depende.

• O Mergesort consome mais memória e tem consumo de tempo estável.
• O Quicksort não consome memória adicional e o consumo de tempo pode variar.

Contudo, na programação competitiva usamos a função sort(itInicio, itFim) do C++, que é implementada com Quicksort.

Exemplo:

int n = 10;
arr[n] = {11, 9, 2, 7, 11, 1, 13, 7, 7, 5};

sort(arr, arr+n);
print_array(arr, n); // 1 2 5 7 7 7 9 11 11 13

Você precisa de pelo menos 0 problems problemas.

Aula 06 - Noções Básicas de Problem Solving

Até agora, vimos majoritariamente um curso básico de C++ com ferramentas focadas em programação competitiva. No entanto, as competições vão muito além de saber apenas codar em uma linguagem específica. Precisamos também ter as ideias corretas para o problema, de forma rápida e eficiente. Muitas vezes, a implementação é a parte mais fácil da resolução. Mas ter a ideia correta é um processo muito confuso e, por vezes, místico, quando estamos começando. Então, como podemos fazer para esse processo ser mais consistente e menos assustador?

De fato, há técnicas e práticas que podemos treinar para abordar um problema que parece muito difícil. Às vezes nos assustamos quando vemos um veterano resolvendo um problema que passamos horas pensando instantaneamente, mas ele apenas estava acostumado com o processo e com as ideias necessárias para chegar na solução. Nessa aula, veremos algumas noções básicas que podem nos ajudar a resolver problemas que, à primeira vista, parecem impossíveis.

Técnica 1: Apenas tentem!

Primeiro, vamos olhar para um problema do simulado do bixecamp de 2023: Coffee Break.

Resumidamente, recebemos uma matriz de 0s e 1s e queremos saber a maior submatriz que contém apenas entradas de valor 1. À primeira vista, é um problema que pode assustar pois não parece haver uma maneira eficiente e trivial de contar esses valores. Pelo menos é o que acreditamos, já que boa parte dos competidores não resolveu o problema durante o tempo da prova, mesmo sendo um dos problemas que os setters consideraram como fácil. Não estamos dizendo isso para desestimular vocês, mas em algum lugar ocorreu um desencontro na percepção da questão entre os setters e os competidores. Por isso, consideramos um tópico importante para mencionar.

Aos olhares mais atentos, vão perceber um detalhe extremamente importante no problema que deixa ele muito mais simples: é garantido que o número de entradas da matriz é menor ou igual a 400. Por que isso nos ajuda? Pelo fato de 400 ser um número muito pequeno! Não precisamos achar uma solução extremamente otimizada e absurda. Podemos apenas testar todas as submatrizes e contar se nela há apenas 1's. Caso tenha, verificamos se é a maior encontrada até então. Podemos calcular a complexidade (o número de operações feitas pelo código) para ter certeza que essa solução não irá estourar o tempo.

Primeiro, veja que cada submatriz pode ser definida unicamente por dois valores: o índice (a, b) do seu canto superior esquerdo, e o índice (c, d) do seu canto inferior direito (adotamos aqui a origem como sendo o canto superior esquerdo!). Portanto, iremos iterar sobre todos os valores possíveis de a, b, c e d, seguindo a restrição de que c ≥ a e d ≥ b, para termos certeza que as submatrizes estão bem definidas. Note que, para o primeiro par (a, b), temos (n * m) escolhas. Para o par (b, c), temos na ordem de (n * m) escolhas também. O valor efetivo será menor, já que desconsideramos os pontos anteriores ao par (a, b), mas a complexidade ainda será a mesma. Em todo caso, estamos apenas superestimando nossas contas. Além disso, para cada submatriz, precisamos passar por ela inteira para calcular se existem apenas 1’s dentro dela. Logo, é uma operação em média O(nm). Como para cada operação O((nm)²) realizamos uma operação O(nm), a complexidade total da solução fica O((nm)³). Como sabemos que nm é no máximo 400, no total faremos no máximo 400³ = 64,000,000 = 6.4*10⁷ < 10⁸. Lembre-se que o C++ realiza cerca de 10⁸ operações em um segundo, por isso não queremos passar desse limite. Ou seja, a solução é perfeitamente viável!

Portanto, podemos aprender uma ótima lição com esse exercício. Sempre, sempre verifique se a abordagem mais óbvia para o problema funciona. Se você sabe estimar a complexidade, então não precisa perder tempo codando uma solução que você já sabe que irá exceder o tempo. Ainda que a abordagem não funciona, isso é um ótimo começo, pois saímos de “como resolvo o problema” para “como posso otimizar minha abordagem”, o que, às vezes, é mais fácil. Mesmo se você não tem muita prática em estimar complexidades, é importante tentar! Implemente o que você pensou. No pior dos casos, você irá tomar um Time Limit Exceeded (TLE), mas ainda assim terá feito algum avanço no problema. Claro, devemos ter cuidado, pois às vezes a otimização é a parte mais desafiadora do problema. No entanto, não devemos deixar de passar problemas simples apenas porque presumimos que o problema é muito difícil, sem nem mesmo tentar.

Falando em complexidade, adote as seguintes regras como dicas para resolver um problema:

• Se n é no máximo 20, um brute force básico O(2^n) pode funcionar. Teste todas as possibilidades! 2^20 é aproximadamente 10⁶.
• Se n é no máximo 100, um código O(n ⁴) pode funcionar, mas será apertado.
• Se n é no máximo 500, um código O(n ³) irá funcionar.
• Se n é no máximo 10⁴, então um código O(n ²) pode funcionar. Preste muita atenção nesses casos! Códigos O(n ²) são por vezes mais simples de se codar, então um limite desses pode deixar um problema muito mais fácil.
• Se n é 10⁵ ou 10⁶, então você irá precisar de um algoritmo O(n) ou O(n log n). Não tente fazer um O(n ²), pois certamente não irá funcionar.
• Se n é 10⁹ ou maior, então seu código terá que ser O(1) ou O(log n). Também não tente abrir arrays com esse tamanho, pois certamente irá exceder o limite de memória. Nunca tente iterar sobre cada valor até n nesse caso, pois não irá funcionar.

Note que, apenas ao ler as restrições para a entrada, já temos uma excelente dica de qual abordagem devemos ter para resolver o problema. Percebendo que o tamanho de uma lista vai até 10⁴, já podemos sentir um grande alívio pois poderemos iterar por todo par dessa lista, por exemplo, ao invés de encontrar uma fórmula ou algoritmo absurdo.

Segue abaixo o código de solução do problema:

#include <bits/stdc++.h>
using namespace std;


int n, m;
int matriz[400][400];


// retorna verdadeiro se matriz[a..c][b..d] é composta por apenas uns
bool apenas_uns(int a, int b, int c, int d)
{
   for (int i = a; i <= c; i++)
       for (int j = b; j <= d; j++)
           if (matriz[i][j] != 1)
               return false;


   return true;
}


int main()
{
   // Leitura do input
   cin >> n >> m;
   for (int i = 0; i < n; i++)
       for (int j = 0; j < m; j++)
           cin >> matriz[i][j];


   // A quantidade máxima de uns que podemos ter
   int ans = 0;


   // Itera sobre todas submatrizes da forma matriz[a..c][b..d]
   for (int a = 0; a < n; a++)
       for (int b = 0; b < m; b++)
           for (int c = a; c < n; c++)
               for (int d = b; d < m; d++)
                   if (apenas_uns(a, b, c, d))
                   {
                       // Quantidade de uns da submatriz é igual à área da submatriz
                       int area = (c - a + 1) * (d - b + 1);
                       ans = max(ans, area);
                   }


   cout << ans << endl;
}

Técnica 2: Mude a perspectiva

Em computação, há operações que não importa o quanto você queira, é simplesmente impossível de se fazer de forma eficiente. Por exemplo, remover ou inserir um item em uma lista, preservando sua ordem. Apesar de haver estruturas que possam cuidar disso em O(1) ou O(log n), podemos cair em armadilhas. Remover elemento por elemento ainda pode ser custoso. Vejamos esse problema da Seletiva USP de 2022: Indiana Jiang and the sphinx riddle.

Nele, há duas múmias que se revezam retirando elementos de uma lista. A primeira múmia, de cor branca, passa retirando uma bola sim e uma não, começando pela segunda, da esquerda para a direita, e a outra múmia, de cor preta, remove da direita pra esquerda, começando pela antepenúltima, uma sim e uma não. Elas então continuam nesse processo até sobrar apenas uma bola. Queremos saber qual é o valor da bola restante.

Note que, como foi dito antes, apenas simular o jogo não irá funcionar. Mesmo que apenas marquemos as bolas já removidas com um valor qualquer, passar pela lista várias vezes irá, inevitavelmente, estourar a complexidade. Na verdade, passar apenas uma vez já irá estourar a complexidade, pois N pode ser igual a 10⁹.

Precisamos então encontrar uma solução que não percorra a lista nenhuma vez, mas que de alguma forma, nos diga exatamente qual a bola que ficará no final. Parece muito complexo, então vamos treinar mais uma ideia importante: testar os casos menores.

Podemos acompanhar o caso do enunciado como exemplo, com N = 7.

• No começo, temos as seguintes bolas: 1 2 3 4 5 6 7
• Após a primeira múmia passar, teremos: 1 3 5 7
• Em seguida, temos: 3 7
• E por fim: 3

Podemos tentar outros casos, e procurar alguma fórmula fechada que nos diga qual é o número restante em função de N em O(1). No entanto, isso não é necessário! Vamos procurar quais informações temos em cada etapa. Ao passar da lista 3 7 para 3, note que o valor de cada número não importa. Sabemos que, como é a vez da múmia branca de passar, ela sempre irá remover a segunda bola, ficando a primeira. Portanto, toda vez que tivermos dois números, e for a vez da múmia branca de remover as bolas, ela sempre deixará a primeira. Caso seja a múmia preta, ela irá remover a primeira, e deixar a segunda. Ou seja, não precisamos saber qual o valor das bolas, precisamos saber apenas qual delas iremos escolher. Sabendo disso, vamos olhar agora para o caso anterior, 1 3 5 7. Sabemos que no próximo passo, a primeira bola será escolhida. Mas quando a múmia preta passar, a bola que será a primeira do próximo caso, é a segunda de agora. Podemos ver isso facilmente pois ela ainda é a de número 3, mas fica óbvio ao vermos que todos os índices pares serão divididos por 2, e os ímpares sumirão. Portanto, sabendo que no próximo caso será escolhido a i-ésima bola, independente do seu valor, ela será a (2 * i)-ésima bola nesse caso, quando é a vez da múmia preta remover. Note que isso é válido apenas por que o tamanho da lista é par, então a múmia preta irá remover os índices ímpares. Podemos seguir com essa mesma ideia. Sabendo que na lista 1 3 5 7 escolhemos a segunda bola, podemos ver qual é sua posição correspondente na lista anterior, sabendo que foi a múmia branca que removeu as bolas dessa posição. Como a múmia branca remove os valores de índice par, todo índice ímpar 2 * k - 1 irá parar na posição k. Se preciso, tome um tempo para se convencer disso. Assim, se sabemos que em uma etapa escolhemos a i-ésima bola, então na etapa anterior essa bola era a de valor 2 * i - 1. Logo, na lista 1 3 5 7, a segunda bola possui valor 2 * 2 - 1 = 3 na lista anterior 1 2 3 4 5 6 7. Como voltamos à lista inicial, agora já sabemos exatamente qual valor a bola deve ter! Encontramos exatamente o que queríamos: a terceira bola.

O que nós fizemos agora, foi simplesmente mudar nossa perspectiva. Ao invés de ir removendo as bolas, assumimos que já tínhamos a bola no final, e vimos de onde ela deveria ter vindo a cada etapa. Note que, a cada iteração, a depender do tamanho da lista e da múmia que está removendo, conseguimos descobrir qual bola devemos retornar baseado no próximo caso: um problema clássico de recursão!

A exploração pode ter ficado confusa, então vamos explorar com mais calma a ideia, de forma indutiva: Receberemos uma lista com N bolas. Não nos importamos qual valor cada bola possui, apenas queremos retornar qual a posição da bola é a escolhida no final. Iremos discutir porque isso nos garante a bola correta mais adiante. Por enquanto, vamos descobrir como fazer essa transição. Primeiro, o caso base. Esse é muito simples. Se N = 1, há apenas uma bola, que é a escolhida por definição. Então retornaremos o valor 1, pois essa é a posição da bola escolhida. Agora, suponha por indução que estamos em um caso anterior qualquer, e recebemos a informação de que a k-ésima bola do próximo caso é a escolhida. Como recebemos essa informação? Não importa, essa é a beleza da indução. Apenas assumimos que a informação é correta e passamos adiante. Como sabemos que a primeira informação é correta, todas as próximas também estarão. Sabemos então que o índice k da próxima lista é a escolhida. Como podemos descobrir qual o índice correspondente em nossa lista? Bom, se a lista tiver tamanho ímpar, é fácil. Independente da múmia que passar, qualquer uma removerá os índices pares. Logo, todo índice par vai sumir, e os índices ímpares da forma 2 * k - 1 irão para a posição k. Assim, se sabemos que o próximo caso retorna o valor k, iremos retornar então o valor 2 * k - 1. Se a lista tiver tamanho par, então irá depender de qual múmia é a vez. Se for a múmia branca, essa irá remover os índices pares. Logo, pelo mesmo motivo anterior, retornamos 2 * k - 1. Agora, se for a múmia preta, essa irá remover os índices ímpares. Então todo índice ímpar some, e os pares da forma 2 * k vão para a posição k. Logo, retornamos 2 * k. Então, ao chegarmos na última (ou primeira) camada, retornaremos um índice i. No entanto, sabemos que as bolas estão numeradas tal que a bola na posição i possui valor i, ao menos nessa etapa. Portanto, esse é exatamente o valor que estamos buscando.

Mas então, como codamos isso? Como foi dito, usaremos recursão. Para cada etapa, estaremos fazendo uma pergunta para a próxima: com uma lista de tamanho x, e uma múmia y que jogará na sua vez, qual é o índice da bola escolhida? Então, com a resposta obtida, calculamos o valor que devemos retornar. Note que, se recebemos uma lista de tamanho x, então devemos considerar alguns casos. Se x for ímpar, então após a remoção das bolas na nossa etapa, sobrarão ⌊ x / 2 ⌋ + 1 bolas para o próximo caso. Se for par, então serão removidas metade das bolas, sobrando x / 2. E a múmia y, podemos simplesmente passar um booleano, onde 0 é a múmia branca, e 1 a múmia preta. Se chegarmos no caso base, retornamos 1. Note que a cada iteração, dividimos o espaço de procura em 2. Portanto, a complexidade da solução é de O(log n). Segue o código para compreensão:

#include <bits/stdc++.h>
using namespace std;


// Recebe o tamanho da lista e o tipo da múmia
int solve(int n, bool m)
{
   // Caso base
   if (n == 1)
       return 1;


   // Se n é ímpar, o tipo da múmia não importa
   if (n % 2 == 1)
       return 2 * solve((n + 1) / 2, !m) - 1;


   if (m)
       return 2 * solve(n / 2, !m);
   else
       return 2 * solve(n / 2, !m) - 1;
}


int main()
{


   int n;
   cin >> n;
   cout << solve(n, 0) << endl;
}

O que podemos aprender com esse problema? Por vezes, é mais fácil mudar a perspectiva em que estamos trabalhando. Ao invés de remover valores, e se os adicionarmos ao contrário? Ao invés de responder perguntas em ordem, e se as recebêssemos e encontrarmos a resposta numa ordem que for mais conveniente, e organizar as respostas ao final para responder as perguntas na ordem correta? Ou, nesse caso, realizar as operações de baixo para cima ao invés de cima para baixo? Nem sempre isso nos trará uma solução imediata, mas por vezes isso nos permite enxergar outras propriedades do problema, que nos deixará um passo mais próximo da resposta.

Técnica 3: reduza a problemas mais simples.

Ao estudarmos programação competitiva, é impossível nos prepararmos para todas as ideias mirabolantes que passam na cabeça das pessoas que propõem os problemas. Mas de um jeito ou de outro, essas ideias são combinações de outras ideias mais comuns que você pode ter estudado por aí. Por isso, costumamos praticar e aprender com problemas clássicos. Um problema muito complexo pode ser decomposto em ideias cada vez mais simples, até que uma delas será algo que já sabemos fazer, ou por termos estudado aquele conteúdo específico, ou simplesmente esclarecer qual o caminho a seguir. De toda forma, é essencial que saibamos como interpretar e reduzir problemas complexos, tomando um passo de cada vez, e assim acabar com problemas mais simples.

Vejamos então um problema de um contest recente (em relação à data que esse guia foi escrito) do Codeforces: Long Inversions.

Nele, recebemos uma string de tamanho n contendo apenas 0 e 1. Podemos escolher um valor k e aplicar a seguinte operação: escolher vários segmentos de tamanho k, e para cada segmento inverter todos os valores nele. Ou seja, todo 0 vira 1, e todo 1 vira 0 nesse segmento. “Vencemos” o jogo se pudermos deixar todos os elementos iguais a 1. Queremos então saber qual o valor máximo de k que podemos escolher para vencer o jogo, independente do número de jogadas.

Primeiro, vamos lembrar das dicas anteriores. Temos que n vai até 5 * 10³. Ou seja, um código O(n ²) será suficiente para esse problema. Mesmo assim, ainda não fica imediatamente claro como podemos sequer começar. Afinal, há efetivamente maneiras infinitas de se jogar o jogo, pois podemos escolher uma quantidade arbitrária de intervalos. Então, vamos tentar mudar nossa perspectiva, e explorar casos mais básicos.

Vamos fixar um valor de k e tentar encontrar uma maneira mais concisa de visualizar o problema, para ver se encontramos alguma solução. Mas como podemos representar esses intervalos? Vamos imaginar que cada intervalo é representado por uma barra cobrindo um segmento. Por exemplo, temos que a escolha de intervalos de tamanho 6, [8,13], [12,17], [1,6], [4,9], [7,12] e [4,9] (de forma 1-indexada) podem ser representada dessa forma:

Note que, o que estamos fazendo efetivamente é, para cada índice, queremos invertê-lo na mesma quantidade de segmentos que existem sobre ele. Mas veja que isso é uma operação muito simples. Não importa nem a ordem nem a quantidade. Precisamos saber apenas a paridade dos segmentos que aparecem acima de cada índice. Podemos então escrever os segmentos dessa forma:

E apagando os segmentos que se sobrepõe, mantendo apenas a paridade, temos:

Dessa forma, fica muito mais fácil de perceber, por exemplo, que o segmento [4,9] foi completamente anulado pelo fato de aparecer duas vezes. Ou seja, nunca faz sentido selecionarmos o mesmo segmento duas vezes, pois estaríamos apenas desfazendo um trabalho que já fizemos, e como a ordem que selecionamos os segmentos não importam, não há nenhuma situação em que precisemos selecionar um segmento e depois revertê-lo, pois apenas não precisávamos selecioná-lo para começar.

Então precisamos saber apenas quais intervalos precisam, necessariamente, ser invertidos. Para simplificar, vamos imaginar que cada índice entre 1 e n - k + 1 é um botão, que irá inverter os próximos k valores, incluindo ele mesmo. Vamos então tentar jogar o jogo com a string acima (0110110001100111), e com k = 6.

Primeiro, veja que há apenas um botão que pode mudar o primeiro valor. Portanto, como ele é um 0, ele necessariamente deve ser apertado, pois ninguém mais o fará. Apertando ele, temos então a string 1001000001100111. Seguimos então para o próximo índice, já que estamos feitos com o primeiro. Note que os únicos botões que podem alterar o segundo índice são os botões 1 e 2. No entanto, já apertamos o botão 1 uma vez, então não faz sentido apertá-lo de novo, e desfazer nosso progresso. Logo, nossa única opção é apertar o segundo botão se quisermos corrigir a segunda posição. Ficamos então com a string 1110111001100111. Dessa vez, no terceiro índice, temos o valor 1. Note que se apertarmos esse botão agora, teremos que desfazer essa ação em algum momento. Mas os únicos botões que podem alterá-lo são o 1, 2 e 3. Já vimos que não faz sentido apertar os botões 1 e 2 novamente, e se apertarmos o 3 teríamos que apertá-lo de novo. Portanto, o melhor que podemos fazer é seguir em frente e não apertar nada. O quarto botão é um 0, portanto, pela mesma lógica, ele deve ser apertado. Você pode continuar jogando o jogo, e eventualmente chegará nessa string: 1111111111100000. Note que todos os últimos valores precisam ser apertados, mas não queremos mexer em nenhum botão anterior. No entanto, não há mais botões a serem apertados, já que os botões sempre alteram os próximos 6 valores nesse caso. Ou seja, para essa string, com k = 6, não temos solução. Agora, se ao realizarmos o mesmo procedimento, verificarmos que os últimos 5 valores da string já eram, por conveniência, iguais a 1, então sabemos que encontramos uma solução. E como a ordem dos movimentos não importa, sabemos que esse é o único caso em que há solução.

Ótimo, resolvemos um problema mais simples. Para um dado k e uma dada string, já conseguimos descobrir se é possível vencer o jogo. Mas a pergunta original era qual o maior valor possível de k que nos permitia vencer. Então como podemos fazer isso? Muito simples, ora! Lembre-se que pelas restrições do problema, nos foi permitido fazer uma solução O(n ²). Como os valores de k podem ser qualquer número entre 1 e n, basta testarmos todos, do maior para o menor, até encontrarmos uma solução! Note que k = 1 sempre nos dará uma solução, então se nosso código estiver correto ele certamente retornará alguma coisa.

Veja como, quebrando em casos simples, para os quais conseguimos encontrar as soluções mais facilmente mudando nossa perspectiva, podemos encontrar a solução geral.

No entanto, na hora de implementar, podemos encontrar mais um problema. Para cada valor de k, iremos iterar entre todos os valores de 1 a n, e então iremos invertendo os próximos k valores se necessário. Note que isso requer uma complexidade de O(n ³), pois ao invertermos cada um dos próximos valores estamos realizando muitas operações. Pode parecer um saco, depois de tudo isso, ainda não resolvemos o problema. Mas veja que agora estamos a um passo de resolver completamente. Basta apenas encontrar uma ideia inteligente para resolvê-lo. Perceba que, não há a menor necessidade de ir invertendo cada valor após cada operação. Podemos simplesmente “anotar” quantos intervalos estamos contando neste momento, e anotar em um vetor auxiliar onde eles param de contar. Cada vez que encontrarmos um 0 numa posição i (após as inversões necessárias), sabemos que devemos somar mais um intervalo. No vetor auxiliar, iremos dizer que na posição i + k - 1 devemos parar de incluir esse intervalo, portanto ao chegar lá, iremos subtrair 1 na contagem dos intervalos. Se a quantidade de intervalos for ímpar, devemos inverter. Se for par, devemos deixar como está. Note que agora não precisamos passar várias vezes nos mesmos índices desnecessariamente. Quando passarmos por ele, já sabemos qual situação ele deve estar baseado nos casos anteriores. Segue o código para melhor compreensão:

#include <bits/stdc++.h>
using namespace std;


char inverse(char c)
{
   return c == '0' ? '1' : '0';
}


void solve()
{
   int n;
   cin >> n;
   string s;
   cin >> s;


   // ans é o máximo k que encontraremos
   int ans = -1;
   // Como n <= 5000, podemos fazer uma solução quadrática que itera por cada k
   for (int k = 1; k <= n; k++)
   {
       int intervalos = 0;
       // Vetor auxiliar para indicar a saida de um intervalo
       int acaba[n + 10];
       for(int i = 0; i < n + 10; i++) acaba[i] = 0;


       string copy_s = s;
       for (int i = 0; i < n; i++)
       {
           intervalos -= acaba[i];
           if (intervalos % 2 == 1)
               copy_s[i] = inverse(copy_s[i]);


           if (copy_s[i] == '0' && i + k - 1 < n)
           {
               // Adiciona um segmento de i até i + k - 1
               intervalos++;
               // Intervalo acaba em i + k
               acaba[i + k]++;
               copy_s[i] = inverse(copy_s[i]);
           }
       }


       // count conta quantas ocorrências de ‘1’ existem em copy_s
       if (count(copy_s.begin(), copy_s.end(), '1') == n)
           ans = k;
   }
   cout << ans << '\n';
}


int main()
{
   int t;
   cin >> t;
   for (int i = 0; i < t; i++)
       solve();
}

Você precisa de pelo menos 0 problems problemas.

Aula 07 - Introdução à STL

Nessa aula, vamos aprender o que é a STL e como podemos utilizá-la para resolver de forma prática vários problemas anteriores e muitos novos.

Mas o que é a STL?

A Standard Template Library (STL) é uma biblioteca do C++ que possui vários recursos, como funções e estruturas de dados que podem ser usados associados a qualquer tipo de dado, inclusive estruturas definidas pela própria STL.

Em C++, essa característica de um tipo de dado ser capaz de se comportar de forma semelhante independente do tipo de dado que guarda é chamado de template, e permite abstrair as ideias em diversos problemas.

Iremos estudar 4 das principais estruturas (chamadas containers) da STL, que abstraem conceitos matemáticos importantes:

• vector: array dinâmico
• pair: par ordenado
• set: conjunto
• map: um "dicionário" que mapeia "chaves" a "valores"

Para cada uma delas, veremos as principais operações que podemos fazer sobre a estrutura e a complexidade dessas operações.

Vector

Já vimos anteriormente que uma lista de números pode ser representada em um array: uma lista que guarda 10 valores booleanos pode ser declarada como bool lista[10], e para acessar algum valor usamos colchetes (para acessar o terceiro valor da lista, usamos lista[2]).

Podemos usar um vector para fazer a mesma coisa, mas a forma de declarar muda. Assim como no caso do array estático, precisamos declarar o tipo de dado que queremos guardar (nesse caso, bool) e podemos dizer o seu tamanho inicial: vector<int> lista(10). Para acessar o terceiro elemento, fazemos também lista[2].

Diferenças com relação ao array estático

A primeira diferença é que o vector é um array dinâmico, ou seja, não precisamos definir o seu tamanho na hora de declarar. Quando o vector estiver "cheio" e quisermos adicionar um novo elemento a ele: a própria estrutura irá alocar mais espaço para a operação.

Para inserir um elemento no final de um vector, usamos a operação push_back. Veja um programa que lê uma lista de n números inteiros dados pelo usuário usando push_back:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> vetor;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        vetor.push_back(x);
    }
}

Assim como no caso de arrays, podemos querer ordenar nosso vector. Para isso, usamos a função sort com uma sintaxe diferente:

    vector<int> lista = {3,4,-5,-6};
    sort(lista.begin(), lista.end());
    for(int i = 0; i < 4; i++)
        cout << lista[i] << ' ';
    // saída: -6 -5 3 4 

Falaremos mais sobre o que são begin e end na seção de iteradores.

Em C++, uma string da STL se comporta como um vector<char> (com algumas simplificações para a manipulação do texto, como permitir comparações e concatenação). Ou seja, podemos usar as operações de arrays dinâmicos com strings.

Se queremos determinar se duas strings são anagramas uma da outra, podemos fazer um vetor de frequência para as letras e comparar essas contagens. Uma forma mais curta de determinar se duas strings dadas são anagramas uma da outra, e que não depende do tamanho do alfabeto, é a seguinte, usando sort:

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());

    if(s == t) cout <<"SIM\n";
    else cout << "NAO\n";
}

Principais operações em vector

• push_back: adiciona um elemento ao final do vetor. O(1) amortizado.
• pop_back: remove o elemento ao final do vetor. O(1).
• clear: limpa o vetor. O(n).
• size: retorna o tamanho do vetor. O(1).
• empty: diz se o vetor está vazio (v.empty() é o mesmo que v.size()==0). O(1).

Para fazer buscas binárias em vetores ordenados, podemos usar lower_bound e upper_bound. Essas funções retornam iteradores, que veremos mais adiante.

• Se v é um vector<int> ordenado, o primeiro elemento de v que é maior ou igual a 10 está na posição lower_bound(v.begin(),v.end(),10)-v.begin().
• Se v é um vector<int> ordenado, o primeiro elemento de v que é estritamente maior que 10 está na posição upper_bound(v.begin(),v.end(),10)-v.begin().

Pair

Um pair é um par ordenado, uma estrutura que guarda dois valores ao mesmo tempo. Esses valores são chamados de first (o primeiro elemento) e second (o segundo elemento). Os dois valores não precisam ser do mesmo tipo, mas precisam ter seus tipos dados informados na declaração do pair.

Um par meu_par que guarda um char e um vector<int>, pode ser declarado como pair<char,vector<int>> meu_par.

Além da vantagem de se poder guardar qualquer tipo de dado em um pair (como um vector de inteiros no exemplo acima), existe a vantagem que dois pares podem ser comparados: primeiro se compara o primeiro elemento de ambos e, em caso de empate, se compara o segundo deles.

• {0,10} < {5,0}
• {0,'b'} > {0,'a'}
• {5,"batata"} < {5,"mais batata"}

Note que só é possível comparar esses pares quando os dois tipos envolvidos são comparáveis. vector não é um tipo comparável, então teríamos um erro de compilação ao tentar comparar meu_par com outro pair do mesmo tipo.

Uma aplicação importante dessa ideia de ordenar pares é quando temos dois tipos e informação (nome e idade) e queremos usar uma dessas informação para ordená-las (idade). Usar pair é uma forma de vincular essas informações durante a ordenação, permitindo recuperar a informação que não foi usada na ordenação.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<pair<int,string>> idade_nome(n);
    
    for(int i = 0; i < n; i++)
        cin >> idade_nome[i].second >> idade_nome[i].first;

    sort(idade_nome.begin(),idade_nome.end());
    
    for(int i = 0; i < n; i++)
        cout << idade_nome[i].second << '\n';
        // imprime o nome das pessoas, da mais nova para a mais velha
}

/*
Input:

3
Enzo 80
Aristeu 10
Maria 30

Output:

Aristeu
Maria
Enzo
*/

Principais operações em pair

• first: acessa o primeiro elemento.
• second: acessa o segundo elemento.
• make_pair: cria um par. Na prática, pair<int,int> p = {0,3} é o mesmo que pair<int,int> p = make_pair(0,3).

Set

Um set é um conjunto de elementos de um mesmo tipo. Esse tipo deve ser um tipo comparável.

Como em um conjunto matemático, podemos adicionar ou remover valores, e nunca há dois elementos iguais no conjunto.

Principais operações em set

• insert: adiciona um elemento ao conjunto. O(log n).
• erase: remove um elemento do conjunto. O(log n). É possível remover um elemento tanto pelo seu valor como usando um iterador para ele. Dessa forma, se um conjunto s possui um elemento igual a 5 e queremos removê-lo, são equivalentes s.erase(5) e s.erase(s.find(5)). De forma semelhantes, para remover o menor elemento de s podemos fazer tanto s.erase(s.begin()) como s.erase(*s.begin()) (na prática, a primeira forma é mais rápida)
• size: retorna o tamanho do conjunto. O(1).
• find: se o elemento está no conjunto, retorna um iterador para ele. Senão, retorna um iterador para "final" do conjunto. Assim, um valor x está em s se, e somente se, s.find(x)!=s.end(). O(log n).

Map

Um map é um dicionário que mapeia valores de um primeiro tipo (chamados de "chaves") valores de um segundo tipo. Esses tipos não precisam ser diferentes. A única restrição é que as chaves precisam ser de um tipo comparável.

Para associar nomes a idades, podemos fazer um map<string,int> quantos_anos. Para acessar a idade de Roberto (e guardar que sua idade é 50 anos), usamos colchetes: quantos_anos["Roberto"]=50.

Map de frequência

Maps podem ser usados para generalizar vetores de frequência com maps de frequência. Se queremos dizer quantas vezes cada nome aparece em uma determinada sequência, não dá para usar um vetor de frequência, porque arrays e vector's são indexados por inteiros não negativos.

Além disso, quando as chaves são muito esparsas (inteiros até 10⁹), muitas delas não terão valores atribuídos, e portanto um map pode ser usado para que apenas as chaves "úteis" tenham valores associados. Veja o exemplo abaixo, que lê uma sequência de strings e responde várias queries do tipo "quantas vezes essa string aparece na sequência?":

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    
    map<string,int> freq;
    
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        freq[s]++;
    }
    
    int q; cin >> q;
    
    for(int i = 0; i < q; i++){
        string s; cin >> s;
        cout << freq[s] << '\n';
    }
}
    
/*
Input:

5
Maria
Maria
Cleber
Clodoaldo
Maria
3
Clodoaldo
Maria
Beto

Output:
1
3
0

*/

Tanto nas queries como na hora de incrementar a frequência do nome (em freq[s]++), não é necessário "conferir" se a chave já está sendo usada no dicionário. Se ela não está sendo usada, como na primeira vez que acessamos freq["Maria"], o próprio dicionário toma conta de criar uma entrada para ela antes de usar esse valor para operações, usando o valor default do tipo em questão. No caso de inteiros, esse valor é 0.

Contudo, note que quando acessamos uma chave ainda não cadastrada, o map de fato cria uma entrada para ela, aumentando o seu tamanho e portanto aumentando o tempo de execução das operações sobre ele. Uma forma de evitar essa criação de entradas para chaves inúteis é usando o find para determinar se a chave já está sendo usada no map:

if(m.find(s) != m.end()) cout << freq[s] << endl;

Principais operações em map

• size: retorna o tamanho do dicionário. O(1).
• []: acessa elemento do map. O(log n).

Iteradores

No caso de estruturas que não se comportam como arrays tradicionais, em que os valores são guardados de forma "crua" na memória e podem ser acessados diretamente, é necessário um artifício para acessar e iterar sobre tais estruturas.

Para isso, a STL define o iterator. Um iterador é uma generalização de ponteiro que aponta para uma posição em uma estrutura. Assim, ela diz onde uma variável está guardada, e não o seu valor.

Se queremos obter o valor da variável apontada pelo iterador it, fazemos *it.

Iteradores em vector

Um vector possui dois iteradores especiais: begin e end.

begin é um iterador que aponta para o primeiro elemento do vector. *v.begin() é o mesmo que v[0].

end é um iterador que aponta para o final do vetor, ou seja, a "posição" logo depois do último elemento. Tentar acessar o valor dessa posição com *v.end() causará uma falha de segmentação.

As funções de busca binária da STL (lower_bound e upper_bound) retornam o iterador end quando não há um elemento na estrutura que satisfaz a condição da busca.

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v = {1,3,2,8};
    
    auto it1 = v.begin();
    cout << *it1 << '\n';
        // saída: 1
    
    auto it2 = lower_bound(v.begin(),v.end(),6);
    cout << it2-it1 << '\n';
        // saída: 3
    cout << *it2 << '\n';
        // saída: 8
        
    auto it3 = upper_bound(v.begin(),v.end(),8);
    cout << it3-it1 << '\n';
        // saída: 4
    if (it3 == v.end())
        cout << "Nenhum elemento do vetor é maior que 8\n";
        // saída: Nenhum elemento do vetor é maior que 8\n
}

Iteradores em set

O problema aqui é mais sério: não há como acessar uma "posição" de um conjunto usando colchetes. Então como podemos iterar pelos elementos do conjunto? Usando iteradores, é claro!

#include <bits/stdc++.h>
using namespace std;

int main(){
    set<int> s;
    int n; cin >> n;
    
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        s.insert(x);
    }
    
    cout << "O conjunto tem " << s.size() << " elementos, que são:\n";
    for (auto it = s.begin(); it != s.end(); ++it){
        cout << *it << ' ';
    }
}

/*
Input:

5
1
0
-2
-2
1

Output:

O conjunto tem 3 elementos, que são:
-2 0 1
*/

• O nosso laço inicializa um iterador it=s.begin() que aponta para o "começo" do conjunto, que é o seu menor elemento.
• No início de cada iteração, precisamos verificar se já chegamos ao fim do vetor, que é apontado pelo iterador s.end().
• A cada laço, fazemos um incremento no iterador com ++it. O operador ++ transforma o iterador it no "próximo" iterador do conjunto (ou seja, o iterador que aponta para o menor elemento maior que o apontado por it antes do incremento). Veja que o resultado é impresso em ordem crescente.

Outra forma de fazer a iteração seria com o seguinte laço:

for (auto x : s)
    cout << x << ' ';

Matematicamente, podemos ler o laço como "para cada x pertencente a S, imprima x". Note que, neste caso, x não é um iterador, mas realmente uma variável que recebe os valores dos elementos de s.

Iteradores em map

Os iteradores em map vão funcionar de forma similar aos iteradores em set.

Em teoria dos conjuntos, uma função é um conjunto de pares ordenados com algumas condições particulares, e pensar nelas assim permite entender as semlehanças entre map<K,V> (K e V são os tipos das chaves e dos valores, respectivamente) e set<pair<K,V>>, principalmente com respeito à iteração. Se queremos imprimir todas as chaves de um map<K,V> m:

for (auto [key,val] : m)
    cout << key << '\n';

Vale ressaltar que no laço acima estamos copiando os valores de k e v dentro do laço. Então, se quisermos alterar os valores mapeados de um map<int,int> para decrementar ou incrementar as frequências de cada chave num map de frequência, por exemplo, o código a seguir não funciona:

#include <bits/stdc++.h>
using namespace std;

int main(){
    map<int,int> m;
    m[0]=1;
    m[1]=3;
    m[2]=5;
    
    for(auto [k,l] : m)
        l++;
    
    for(auto [k,l] : m)
        cout << k << " -> " << l << '\n';
}
/*
Saída:
0 -> 1
1 -> 3
2 -> 5
*/

Para fazer isso funcionar, precisamos não só dos valores de k e l, mas de uma referência para suas posições na memória. Em C++, copiamos essa referência usando o operador & da seguinte forma:

#include <bits/stdc++.h>
using namespace std;

int main(){
    map<int,int> m;
    m[0]=1;
    m[1]=3;
    m[2]=5;
    
    for(auto &[k,l] : m)
        l++;
    
    for(auto [k,l] : m)
        cout << k << " -> " << l << endl;
}
/*
Saída:
0 -> 2
1 -> 4
2 -> 6
*/

Buscando referências

A STL é um recurso da linguagem C++, e portanto é permitido (e recomendado!) consultar referências sobre ela durante provas e estudos quando surgir alguma dúvida.

Uma forma de fazer isso é usando o cppreference.

A STL vai muito além dessa aula, e mesmo para as estruturas que apresentamos há muito a ser explorado. Dê uma navegada! Se você esqueceu como acessar o último elemento (o último mesmo, não o end) de um set, basta ir na documentação de set e procurar o que você quer. No caso, se trata do iterador rbegin.

Você precisa de pelo menos 0 problems problemas.

Aula 08 - Grafos e DFS

Nessa aula, vamos introduzir o conceito de grafo, uma estrutura matemática extremamente útil e frequente na computação. Além disso, estudaremos um primeiro algoritmo para percorrê-lo, inicialmente simples, mas muito versátil.

Definições básicas

• Um grafo é constituidos por nós (chamados também de vértices) e arestas, em que em que uma aresta conecta dois nós e representa alguma relação entre eles.

• As arestas de um grafo podem ser:

  • Bidirecionadas: Se existe uma aresta bidirecionada entre vértices A e B então a relação que aquela aresta estabelece vale no sentido A→B e no sentido B→A). Um exemplo é se consideramos dois irmãos e a relação parental entre eles (Carlos é irmão de George e George é irmão de Carlos).
  • Unidirecionadas: Se existe uma aresta unidirecionada do vértice A para o vértice B, entao a relação dessa aresta vale somente no sentido A→B. Um exemplo disso é se consideramos como vértices uma mãe Maria, seu filho Fábio e a aresta representa a relação parental entre eles. Nesse caso, Maria é mãe de Fábio, mas Fábio nao é mãe de Maria.

• Um grafo direcionado é um grafo que possui arestas unidirecionadas.

• Um grafo com pesos é um grafo em que cada aresta está associada a um valor, por exemplo, o "custo" de ir do vértice A para o vértice B ou a "recompensa" de ir do vértice C para o Vértice D.

• Um grafo é simples se ele nao possui arestas que começam e terminam no mesmo nó e também nao existem múltiplas arestas entre dois nós. Na maiorias dos problemas, assuminos que os grafos dados são simples.

• Um caminho em um grafo é uma sequência de vértices e arestas em um grafo tal que todo vértice e aresta aparece apenas uma unica vez e para cada vértices na sequência ele está conectado por uma aresta ao vértice seguinte.

• No caso de uma sequência de vértices e arestas em que ela atende as condições do caminho, execto pelo fato de o último vértice da sequência ser igual ao primeiro, temos um ciclo.

Conectividade

• Um grafo é considerado conexo se existe um caminho entre quaisquer pares de nós.
• Uma componente conexa em um grafo é um conjunto de vértices tal que existe um caminho entre quaiquer pares de vértices desse conjunto.
• Uma árvore é um grafo conexo em que o número de arestas é igual ao numero de vértices menos um. Existem outras definições equivalente de árvore:
  • Um grafo é uma árvore se há exatamente um caminho entre quaisquer dois nós.
  • Um grafo é uma árvore se é conexo e não tem ciclos.

Adjacência e grau de vértices

• Dois nós são adjacentes se existe uma aresta entre eles.
• O grau de um nó é definido como o número de vértíces adjacentes que ele possui.
• Em casos de grafos direcionados, podemos falar de grau de entrada que é o número vértices adjacentes que tenham arestas apontadas para o vértice em questão e o grau de saída é o número de arestas que saem do vértice em questão.
• Um grafo regular é um grafo em que todos os nós possuem o mesmo grau.
• Um grafo completo é um grafo em que todos os vértices possui grau igual ao número de nós do grafo menos um. De forma equivalente, é um grafo em que há uma aresta entre quaisquer dois vértices.
• Um grafo é considerado bipartido se é possível colorir os vértices desse grafo com duas cores, de maneira que dois vértices adjacentes não tenham a mesma cor. Ou seja, podemos dividir o grafo em dois grupos tal que toda aresta do grafo seja entre vértices de grupos diferentes.

Codando grafos

Possíveis representações de grafos

• Lista de adjacência: nesse caso, temos uma lista de vector's em que cada elemento representa um vértice e cada vizinho dele será adicionado na sua respectiva lista. Em um grafo com N vértices:

vector<int> adj[N];

Em um grafo de 5 vértices e com as arestas bidirecionadas 2—5, 1—4, 2—3, pode ser feito da seguinte forma:

vector<int> adj[6];
adj[2].push_back(5);
adj[5].push_back(2);
adj[1].push_back(4);
adj[4].push_back(1);
adj[2].push_back(3);
adj[3].push_back(2);

Complexidades:

Criar lista de adjacência: O(N)

Adição de aresta: O(1)

Remoção de aresta: O(grau dos vértices) (percorrer a lista toda)

Saber se existe aresta A-B: O(grau do vértice) (percorrer a lista toda)

No caso de grafos com pesos podemos usar pair<int,int> em vez de int, em que um elemento do par representa o outro vértice da aresta e o outro elementa representa o seu peso.

• Matriz de adjacência: temos uma matriz matrix em que matrix[i][j]==0 quando não temos aresta entre i e j e matrix[i][j]==1 quando temos aresta entre i e j.
• No caso de grafos com pesos, poderíamos ter matrix[i][j]==c[i][j] onde c[i][j] é o peso da aresta entre i e j, caso ela exista. Se essa aresta não existir, podemos usar um valor "inválido" de peso para isso, como -1 se os pesos são inteiros não negativos.

Em um grafo de de 5 vértices e com as arestas bidirecionadas 2—5, 1—4, 2—3, pode ser feito da seguinte forma:

int adj[6][6];
for(int i=1;i<=5;i++)
    for(intj=1;j<=5;j++)
        adj[i][j] = 0;

adj[2][5]=1;
adj[5][2]=1;
adj[1][4]=1;
adj[4][1]=1;
adj[2][3]=1;
adj[3][2]=1;

Complexidades:

Memória: O(N²)

Adição de aresta: O(1)

Remoção de aresta: O(1)

Saber se existe aresta A-B: O(1)

• Vetor de arestas: nesse caso, temos um vector em que cada elemento é a representação de uma aresta (podendo ser um pair ou um tuple no caso de grafo com pesos). Essa representação nao é muito usada, porém vale ser citada. A complexidade fica com vocês :).

Busca em profundidade (Depth-First-Search ou DFS)

A DFS é uma maneira de percorremos o grafo em que seguimos passos bem simples, mas que tem bastante utilidade:

• Se estou em um vértice, marco ele como visitado.

• Se um vértice vizinho ao que eu estou não foi visitado, vou para ele.

• Se não há mais vértices vizinhos, volto para o vértice em que eu estava antes.

Podemos implementar essa ideia de forma da seguinte maneira:

int n = numéros de vértices;
vector<int> visitados(n+1); // vetor para marcar os vértices que já foram visitados

vector<int>adj[n]; // representação do grafo


void dfs(int vertice){
    visitado[vertice] = 1;
    for(auto vizinho: adj[vertice]){
        if(visitado[vizinho]==0){
            dfs(vizinho);
        }
    }
}

A partir dessa função, podemos fazer diversas coisas e conseguir informações a respeito do grafo, como por exemplo:

• Número de componentes conexas de um grafo

int conta_componentes(){
    int componentes = 0;
    for(int i=1;i<=n;i++){
        if(visitado[i]==0){
            componentes++;
            dfs(i);
        }
    }
    return componentes;
}

Se você chamou a dfs para um vértice v mas nem todos os vértices do grafo foram visitados, então isso significa que há um vértice u sem caminho para o vértice v. Ou seja, temos mais componentes conexas, e para visitar todo o grafo é necessário chamar a dfs na função conta_componentes() para vértices de componentes nao visitadas.

• Dado um grid NxN em que voce esta na célula x,y e quer ir para a célula n-1,n-1 e pode se mover para cima, baixo, direita e esquerda. Além disso os lugares com '.' no grid sao os lugares que voce pode ir e os 'X' nao paredes que nao da pra atravessar. A partir disso, determine se é possível chegar no ponto n-1,n-1 (o ponto que voce começa é possível estar).

int dx[4] = {0,0,1,-1};  // lista para representar os possíveis movimentos no eixo x
int dy[4] = {-1,1,0,0};  // lista para representar os possíveis movimentos no eixo y

int n;
char grid[n][n];
int vis[n][n];

void dfs(int x, int y){
    vis[x][y] =1;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;i++){
            int new_x = x + dx[i];
            int new_y = y + dy[j];
            if(new_x >=0 and new_x <n and new_y>=0 and new_y<n and vis[new_x][new_y]==0 and grid[new_x][new_y]=='.'){
                dfs(new_x,new_y);
            }
            
            
        }
    }
    
}

int main(){
    int sx,sy; // posições que começamos;
    dfs(sx,sy);
    if(vis[n-1][n-1]==0){
        cout<<"Nao é possivel";
    }
    else cout<<"É possivel";
}

Nesse caso, percorremos o grid da mesma maneira em que fazemos a dfs. os vetores dx e dy são utilizados para iterar pelas possíveis posições em que podemos ir a partir de uma certa posição. Se chamamos a dfs no ponto sx,sy e é possível visitar o ponto n-1,n-1, entao concluimos que chegamos onde queriamos. Se não, significa que existe alguma "barreira" de X's impedindo disso acontecer ou até mesmo o próprio ponto n-1,n-1 tem o valor 'X'.

Você precisa de pelo menos 0 problems problemas.

Aula 09 - Programação Dinâmica

Até agora, vimos diversas técnicas que nos ajudaram a resolver problemas. Algoritmos gulosos, recursões e buscas.
No entanto, muitas vezes essas soluções são extremamente ineficientes, pois há muitos casos que devemos considerar, e passar por todos certamente nos dará um belo TLE.

Por exemplo, vamos considerar um problema simples resolvido com recursão: encontrar o enésimo número de Fibonacci.

Caso você não se lembre, a sequência de Fibonacci é definida da seguinte forma:
F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2), para n > 1

Como já aprendemos, podemos escrever uma simples função recursiva para descrever essa sequência e encontrar seus primeiros valores:

#include <bits/stdc++.h>
using namespace std;

int Fibonacci(int n){
    if(n < 2) return n;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

int main(){
    int n; cin >> n;
    cout << Fibonacci(n) << endl;
    return 0;
}

Ao rodarmos o programa com n = 10, recebemos como output 55. De fato, você pode calcular manualmente e observar que esse é o valor correto. Bom, então ótimo. Vamos aumentar o passo. Que tal calcular para n = 20? O programa retorna 6765. Tudo certo.

Para n = 30, recebemos 832040. Como esperado, o valor de fibonacci cresce exponencialmente. Rodaremos então para n = 40, e logo obtemos também o valor de 102334155.

Mais uma vez. Colocaremos n = 50 no programa e...
Bom, faça o teste em casa. O programa não retorna nada. Mas o que aconteceu? Havia algo errado com o código? Como pode ser se ele retornou tudo corretamente até agora? Enquanto fazíamos essas perguntas, o programa finalmente respondeu! Ele só demorou bastante mesmo... Nossa recursão era tão ineficiente, que mudar o n de 40 para 50 já foi o suficiente para o programa demorar um minuto para encontrar a resposta.

Mas por que isso ocorreu? Bom, vamos analisar o que o programa faz com cada chamada observando um caso pequeno.
Com n = 5, o programa verificará que n não é menor que 2, então continuará para a próxima linha de código. Então, ele irá chamar a função para n = 4. Lembre-se da ordem de chamada: o programa só irá fazer a próxima chamada recursiva assim que a primeira se encerrar.
Para n = 4, o programa também verifica que não é menor que 2, e fará primeiro a chamada para n = 3.
Então, para n = 3, o programa chamará para n = 2, que por fim chamará para n = 1. Como finalmente atingimos um caso base, a função irá retornar 1. Então a chamada de n = 2 juntará essa resposta com a chamada para n = 0, que também é um caso base e retornará 0. Então voltamos à chamada de n = 3, que irá novamente chamar para n = 1. Mas espere um pouco, nós já não passamos por aqui? De fato, ao concluir essa chamada e retornar para n = 4, iremos fazer a chamada para n = 2 também, e ao voltar para a chamada original, faremos o mesmo ao chamar para n = 3 após concluir esse processo.

Essa explicação certamente ficou confusa, mas ajuda a perceber a redundância que ocorre quando fazemos uma chamada recursiva dessa maneira. Utilizando nosso conhecimento de grafos, podemos tentar modelar uma árvore de chamadas, que nos mostra como a recursão prossegue:

Note que esse código é extremamente ineficiente, pois recalculamos o mesmo número de Fibonacci várias vezes. Para estimar a complexidade do código, podemos ver que para cada chamada da função, realizamos 2 novas chamadas. Logo, é natural pensar que a complexidade é O(2^n). Na verdade, como alguns caminhos atingem o final da recursão mais cedo que outros, a complexidade é um pouco menor, e a chamamos de O(fib(n)), que é assintótica a O(φ^n), onde φ = (1+\sqrt(5))÷2 é a proporção áurea. De toda forma, como φ > 1, a complexidade ainda é exponencial, e por isso, aumentando um pouco o parâmetro de entrada, obtemos um aumento significativo no tempo de execução.

Talvez você esteja se debatendo agora, dizendo que podemos facilmente calcular o valor de F(n) com um simples for loop em F(n) salvando F(n-2) e F(n-1) em duas variáveis auxiliares para calcular F(n). Mas iremos explorar outra estratégia agora.

Note como o problema de complexidade está relacionado à redundância. Estamos calculando os mesmos valores várias vezes. E se houvesse uma forma de guardar os estados já processados globalmente, de modo que, ao encontrá-los novamente, apenas retornássemos o valor salvo?

Bom, esse é exatamente o princípio da programação dinâmica! Fazemos uma troca entre tempo e memória ao salvar valores que já calculamos para não precisar recalcular o mesmo valor várias vezes. É preciso ter alguns cuidados na hora de saber quais valores podemos/devemos salvar, e quando devemos utilizar essa técnica, mas entraremos em mais detalhes posteriormente.

Bom, mas então como podemos utilizar essa técnica para otimizar nossa função recursiva?

Naturalmente, a primeira coisa que precisamos fazer é criar uma lista global, a qual chamaremos de memo. Ela será responsável por salvar os valores que já passamos.
Após isso, precisaremos de algo que nos diga que aquele valor ainda não foi calculado. Esse valor dependerá do problema que estivermos resolvendo. Nesse caso, como todo valor de fibonacci deve ser sempre positivo*, podemos utilizar um valor padrão como -1. Ou seja, toda vez que encontrarmos um valor que seja -1 na nossa lista global para aquele parâmetro, sabemos que precisamos calcular aquele valor. Do contrário, retornaremos o que está salvo ali.

* Talvez você tenha percebido que o valor de F(50) que encontramos antes era negativo... De fato, houve um problema de overflow. Daqui em diante, considere que estamos calculando a resposta módulo 1e9+7, uma vez que os valores de Fibonacci crescem muito rápido.

Se o valor for -1, continuaremos a chamada. Ao terminarmos todos os cálculos, antes de retornar a função, devemos armazenar o valor guardado. Aqui vai uma dica para simplificar seu código: você pode fazer essas duas coisas ao mesmo tempo, retornando o valor da lista e assinalando o que foi calculado ao mesmo tempo.

O código então ficará assim:

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 200005;

// memo é um array para memorizar os valores de Fibonacci já calculados
int memo[maxn];

int Fibonacci(int n){
    if(memo[n] != -1) return memo[n];
    if(n < 2) return memo[n] = n;
    return memo[n] = (Fibonacci(n-1) + Fibonacci(n-2))%mod;
}

int main(){
    int n; cin >> n;
    // setamos -1 se não calculamos o valor ainda
    for(int i = 0; i <= n; i++) memo[i] = -1;
    cout << Fibonacci(n) << endl;
    return 0;
}

Testando agora para n = 50, obtemos nossa resposta quase instantaneamente! Podemos até colocar valores muito maiores, como 10^5, e o programa ainda retornará em instantes. Note que se quisermos um valor muito alto, iremos precisar alocar mais memória em memo, e devemos ter cuidado para não estourar a memória também.

Ao calcularmos a complexidade, podemos ver que cada vez que a função tenta fazer uma operação que já foi calculada, iremos cortar as chamadas ali mesmo. No pior caso, iremos continuar a chamada para cada valor de memo que ainda não foi preenchido. Portanto nossa complexidade não é pior que O(n)!

Aprimorando a intuição

Vimos qual o conceito geral da programação dinâmica, carinhosamente apelidada de DP (do inglês Dynamic Programming). No entanto, ainda há um longo caminho para criar a intuição necessária de como devemos usar essa ferramenta poderosa.

Vamos considerar mais uma aplicação básica de programação dinâmica: o problema das moedas. Suponha que você é um caixa de supermercado, e precisa entregar uma quantidade x de troco para um cliente (1 <= x <= 10⁵). Na caixa registradora, há uma quantidade efetivamente infinita de moedas de 1, 2, 5, 10, 25, 50 e 100 centavos. Se quisermos saber qual é a menor quantidade de moedas que precisamos para pagar a quantia, um algoritmo guloso irá resolver: pagaremos com as moedas de mais valor que não excedem o que ainda devemos, e assim por diante até não sobrar mais nada. Mas você é curioso, e quer saber algo diferente: quantas maneiras distintas há de pagar esse valor x, módulo 1e9+7 (já que a resposta pode ser grande). Para simplificar, diremos que a ordem de escolha das moedas importa. Ou seja, escolher a moeda de 2 centavos e depois de 1, ou de 1 e depois a de 2, são duas maneiras distintas de pagar 3 centavos. Uma aproximação gulosa pode funcionar também. Você consegue pensar como?

Podemos fixar o tipo (dentre 7) da última moeda a ser usada, e então fixamos o tipo da penúltima moeda, e assim por diante. Efetivamente, estamos quebrando em subcasos menores. Por exemplo, se soubermos quantas escolhas temos para pagar um valor x-1, sabemos que podemos utilizar essa quantia para calcular as possibilidades para x quando escolhemos uma moeda de 1 centavo. Esse é o princípio da programação dinâmica: recursão (com memorização). Iremos quebrar em casos menores aos quais podemos encontrar soluções de forma recursiva também, até chegarmos a um caso base. Mas qual será o caso base nesse caso? Se quisermos pagar uma quantidade de 0 com nossas moedas, há exatamente uma maneira de fazer esse pagamento: não escolher nenhuma moeda. Se quisermos pagar um número negativo, é conveniente assumir que há 0 maneiras de pagar essa quantia.

Essa ideia intuitivamente pode funcionar, mas ainda precisa ser otimizada. Por exemplo, se escolhermos moedas de 1 centavo duas vezes, caíremos na mesma chamada recursiva caso tivéssemos escolhido uma de 2 centavos, e assim iriamos ter que recomputar a quantidade de vezes para pagar com x-2 moedas duas vezes. Pois então, por que não fazemos exatamente o que foi feito antes? Iremos salvar uma lista com os valores que já percorremos, e não precisaremos calculá-los de novo. O código então ficaria assim:

const int mod = 1e9+7;

vector<int> moedas = {1, 2, 5, 10, 25, 50, 100}

int dp(int x){
    if(x < 0) return 0;
    if(x == 0) return 1;
    //Casos base

    if(memo[x] != -1) return memo[x];
    //IMPORTANTE: preste atenção nos casos base e onde iremos tentar acessar o valor de memo.
    //Se colocarmos essa última linha antes de eliminarmos o caso base que x é negativo,
    //iremos acessar um index negativo. Sempre coloque os casos base antes desse check.
    //Isso normalmente não fará diferença na complexidade, já que os casos base geralmente devem ser retornados em O(1).
    //Note que todo o setup para colocar os valores de memo como -1 ainda deve ser feito.

    int ans = 0;
    for(int moeda : moedas) ans = (ans + dp(x - moeda))%mod;
    //Aqui estamos passando por cada valor de moeda no vetor de moedas, e somando todos os casos
    //em que escolhemos aquela moeda primeiro.

    return memo[x] = ans;
}

Pelos mesmos motivos de antes, a complexidade será O(n). Ou quase. Note que dentro da transição, estamos realizando um loop pelas moedas. Se tivermos k moedas, a complexidade final será de O(nk).

Mas como podemos formalizar esse pensamento? Devemos entender que a programação dinâmica, além de ser uma otimização, é também uma forma de pensar indutivamente. Iremos ver que há muitos problemas com uma solução com recursão, ou ao menos com essa noção de quebrar em casos menores e juntá-los, cuja solução sem otimizações tem uma complexidade muito alta.
Por hora, iremos criar uma nova notação universal, extremamente útil para descrever todo tipo de problemas de DP. Sempre que puder, tente reduzir o problema a essa notação, e será mais fácil de entender com o que estamos lidando. Nesse caso, temos a seguinte afirmação:

dp(i) = 0, se i < 0
dp(i) = 1, se i = 0
dp(i) = dp(i-c_1) + dp(i-c_1) + ... + dp(i-c_n), se i > 0

Denotamos o estado da dp como sendo o índice i.

As primeiras duas linhas são os casos base. Eles são extremamente importantes em determinar onde a recursão deve parar. No nosso caso, faz sentido ter dp(i) para i < 0 é igual a 0, pois não existe maneira de escolher moedas de modo que a soma de valor delas seja negativo, e ter dp(0) = 1, pois há uma maneira de escolher moedas cuja soma de valores é 0: escolher nenhuma moeda.

A última linha é o que chamamos de transição. Ela nos indicará quais subproblemas iremos utilizar para compor a solução maior. Devemos tomar alguns cuidados ao escrever a transição. Caso dp(i) dependesse de dp(i) ou dp(i+1), como calcularíamos dp(i)? Seguindo as transições, devemos sempre cair em um caso base para conseguirmos calcular um valor da dp. Além disso, é importante notar que a transição também pode interferir na complexidade, como vimos acima. No geral, a complexidade de uma dp é dada por O(n*t), onde n é o número de estados, e t a complexidade da transição. Isso ocorre pois a cada valor que preenchemos da lista, precisamos correr uma e apenas uma vez pela transição, e nas próximas teremos esse valor salvo disponível em O(1).

Tente escrever a recursão de Fibonacci dessa forma também para praticar.

Aumentando as dimensões

O poder da programação dinâmica se encontra no fato de que podemos definir o estado. O estado pode ser uma posição em uma matriz, por exemplo.

Vamos ver mais um problema clássico. Suponha que temos uma grid nxm (1 <= n, m <= 2000) de caracteres dessa forma:

.........*
..**...***
..........
.*.....*.*
..........
.*.......*
..***.....
....*..*..

Nela, queremos chegar do canto superior esquerdo até o canto inferior direito, sendo que não podemos passar pelos arbustos, representados por '*'. Como vimos na aula de grafos, podemos facilmente achar um caminho com uma DFS/BFS. Mas assuma que podemos andar apenas para a direita e para baixo, e queremos calcular de quantas maneiras podemos realizar esse caminho, nunca saindo do grid, nunca passando por um arbusto e andando apenas para a direita ou para baixo.

Como estamos numa aula sobre DP, devemos pensar em como podemos reduzir isso em subproblemas, e para isso devemos definir o estado da DP. Um estado que faz sentido é ser a posição onde estamos na matriz. Por tanto, definimos dp(i, j) como sendo a quantidade de maneiras de chegar no canto inferior direito sabendo que estamos na posição (i, j). Note que, a todo momento, temos duas escolhas: ir para a direita ou para baixo. Essas escolhas serão a transição da DP. Note que nunca podemos voltar na posição onde começamos na DP, logo sempre estamos "reduzindo" nosso problema a cada transição.

Agora iremos pensar nos casos base. Primeiro, se atingirmos o final da grid, ou seja, a posição (n-1, m-1), então há apenas uma maneira de alcançar o objetivo, que é simplesmente ficar parado. E caso sairmos da grid, ou adentrarmos um arbusto, estamos em um lugar que não deveríamos estar. Portanto, podemos definir que há 0 maneiras de chegar até o canto inferior direito.

Escrevendo na linguagem recursiva, temos:

dp(i, j) = 0, se i < 0 ou j < 0 ou i >= n ou j >= n
dp(i, j) = 0, se grid[i][j] = '*',
dp(i, j) = 1, se i = n-1 e j = n-1
dp(i, j) = dp(i+1, j) + dp(i, j+1), caso contrário.

Em forma de código, temos a seguinte função:

const int mod = 1e9+7;

int n, m;
char grid[maxn][maxm];
//precisamos declarar as variáveis n e m, assim como a grid, globalmente, já que iremos utilizá-las na função.

int memo[maxn][maxm];
//devemos inicializar uma matriz de memória com duas dimensões dessa vez, já que precisamos de duas variáveis.

int dp(int i, int j){
    if(i < 0 or j < 0 or i >= n or j >= m) return 0;
    if(grid[i][j] == '*') return 0;
    if(i == n-1 and j == m-1) return 1;
    //Checamos os casos base, antes de checar a memória.

    if(memo[i][j] != -1) return memo[i][j];
    //Se já passamos por essa posição da grid, retornamos o valor já calculado

    return memo[i][j] = (dp(i+1, j) + dp(i, j+1))%mod;
    //retornamos a soma dos próximos casos.
}

Note que calculamos a resposta pelo resto módulo mod, pois a resposta pode ser muito grande. No final, a resposta será o valor de dp(0,0).

Passamos por n*m estados e cada estado faz O(1) transições. Logo, a complexidade desse código é O(n*m)

O problema da mochila

Vamos então para o último problema da aula, e o mais clássico, realmente demonstra o poder da programação dinâmica.
Como vimos, os algoritmos de programação dinâmica são algoritmos recursivos com memoização. Até agora, era intuitivo ver que repetiríamos inúmeros casos e poderíamos reduzir a eles de forma simples. Mas às vezes, a transição não nos deixa tão claro que reduzimos a um caso menor que evita repetições, e nem que estamos realizando cálculos supérfluos.

Considere o seguinte problema: você é um ladrão invadindo um museu. Você possui uma mochila que pode carregar um peso máximo de C, e existem O obras no museu, cada um com um peso P_i e um valor V_i. Você deseja maximizar o valor que irá roubar, sem exceder o peso máximo que sua mochila pode carregar. Assuma que 1 <= O <= 100, 1 <= C <= 10⁵, 1 <= P_i <= C e 1 <= V_i <= 10⁹.

A primeira observação importante é que não importa a ordem em que pegamos as obras. Podemos fazer um processo de escolha obra por obra, onde geramos uma configuração nova de obras de 1 a O a partir de uma configuração de obras de 1 a O - 1, por exemplo.

Como faríamos isso? Precisamos saber quais informações são realmente necessárias (e com isso, saber qual seria o estado). Podemos observar que dada uma coleção de obras que queremos pegar, as únicas informações relevantes são o peso total das obras e o valor total das obras. Outra observação é que o peso total das obras que pegaremos é menor ou igual a C, que vai até 10⁵. Esse fato é essencial para resolver o problema.

Como C vai até 10⁵, podemos definir o estado da dp como sendo o peso total das obras que queremos escolher. Assim, podemos tomar dp(i, p) como a maior soma de valores de obras que podemos roubar cuja soma de pesos é igual a p, escolhendo apenas obras de 1 até O.

Mas como calculariamos isso? Efetivamente, uma chamada de dp(i, p) fará o seguinte: ao estar na obra i, com um peso p, qual o melhor valor que eu posso obter escolhendo obras até i? Se p for maior que C, podemos retornar -infinito, pois não podemos carregar mais que C de peso. Do contrário, a função então fará a chamada para i - 1, perguntando qual o melhor valor que ele pode retornar em cada uma das escolhas até a obra i - 1. Então, temos duas escolhas: ou não pegamos a obra i, e dp(i, p) poderia ter o valor de dp(i - 1, p), ou pegamos a obra i, e dp(i, p) poderia ter o valor de dp(i - 1, p - W_i) + V_i.

Na linguagem recursiva, temos a seguinte estrutura:

dp(i, p) = -infinito, se p < 0 ou p > C.
dp(i, p) = 0, se i = 0 e p == 0
dp(i, p) = -infinito, se i = 0 e p != 0
dp(i, p) = max(dp(i-1, p), V_i + dp(i-1, p+W_i)), caso contrário

Em código, temos:

const int infinito = 0x3f3f3f3f;
//Como não podemos representar um infinito literal, usaremos um número que é garantidamente mais alto que qualquer valor
//que possamos encontrar durante o problema
//Esse valor em hexadecimal é aproximadamente 1.6*10^9. Você pode usar outros valores de infinito, mas
//tome cuidado para não escolher um valor muito grande que pode gerar overflows, ou um muito pequeno que não será maior que
//algum valor no seu código.

int O, C;
int V[105], P[105];
int memo[105][20005];

int dp(int i, int p){
    if(p < 0 || p > C) return -infinito;
    if(i == 0) {
    	if(p == 0) return 0;
    	else return -infinito;
    }
    if(memo[i][p] != -1) return memo[i][p];
    return memo[i][p] = max(dp(i-1, p), V[i] + dp(i-1, p+P[i]));
}

No fim, a resposta que queremos é o máximo dentre dp(O, p), para todo peso p. A complexidade desse código é O(O*C), pois passamos por O*C estados.

Esse conceito é difícil de se acostumar no começo, mas ao resolver problemas semelhantes, você terá que pensar nessas ideias e eventualmente irá entender. Portanto não deixe de praticar. Ainda há inúmeras técnicas de programação dinâmica com otimizações ainda mais fortes, mas agora você já tem uma base para começar a estudar.

Se você quiser implementar sua solução para os problemas, você pode encontrar versões semelhantes na lista. Recomendamos fortemente que você tente implementar sua própria versão para fixar bem os conceitos apresentados.

Você precisa de pelo menos 0 problems problemas.