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.