Problema A - Códigos preguiçosos

O Problema

Dados três inteiros $A$, $B$ e $K$, calcular a quantidade $Q$ de números entre $A$ e $B$ que usam no máximo $K$ dígitos diferentes.

Restrições

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

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

Solução Base

Visto que o problema nos pede para calcular a mesma operação um máximo de 20 vezes, vamos focar-nos em calcular uma operação, ou seja, consideremos que temos três inteiros $A$, $B$ e $K$ e queremos calcular a quantidade de números entre $A$ e $B$ que usam no máximo $K$ dígitos diferentes.

A solução mais simples para este problema passa por simplesmente iterar por todos os números entre $A$ e $B$ e para cada um contar quantos dígitos tem. Para todos os que tenham menos de $K$ dígitos incrementamos um contador e devolvemos o valor final desse contador. O código seguinte faz o pretendido:

int contar_digitos(int numero) {
  int diferentes = 0;
  int vistos[10];
  
  for (int i = 0; i < 10; i++) {
    vistos[i] = 0;
  }

  while (numero > 0) {
    int digito = numero % 10;
    numero /= 10;

    if (!vistos[digito]) {
      diferentes++;
      vistos[digito] = 1;
    }
  }

  return diferentes;
}

int resposta = 0;

for (int i = A; i <= B; i++) {
  if (contar_digitos(i) <= K)
    resposta++;
}

Esta solução tem complexidade $O(N(B - A))$, ou seja, daria para aproximadamente 30 pontos.

Melhorar a abordagem

Claramente a solução base é a solução mais simples possível pois temos de iterar por todos os números entre $A$ e $B$. Como é que podemos evitar ter que considerar todos esses números?

Vamos pensar no caso em que $K = 1$. Claramente a maior parte dos números têm mais que 1 dígito diferente. Os números com apenas um único dígito único são da forma 1, 11, 111, 1111, ..., 2, 22, ..., 9, 99, ... Assim, podemos gerar todos os números que contêm apenas um único dígito e depois verificar se quantos há estão entre $A$ e $B$. Consideremos que temos uma array $lista$ que queremos preencher com todos os números com apenas um dígito de 1 a $10^{15}$. O seguinte código faz esta tarefa:

int num_numeros = 0;

for (int digito = 1; digito <= 9; digito++) {
  int numero = 0;
  for (int i = 0; i < 15; i++) {
    numero *= 10;
    numero += digito;

    lista[num_numeros++] = numero;
  }
}

Visto que conseguimos fazer isto quando $K = 1$, e se $K = 2$? Também parece que não há muito números com exatamente dois dígitos diferentes (conseguem fazer as contas?), por isso podemos usar a mesma estratégia e gerar todos os números com até 2 dígitos diferentes.

Gerar números com no máximo 2 dígitos diferentes é um pouco mais difícil. Há várias formas de o fazer, mas a forma mais simples é através de uma função recursiva que vai preenchendo o número com dígitos, guardando os dígitos que já foram usados. O código seguinte mostra exatamente isto:

void gerar(int digito1, int digito2, int numero) {
  if (numero > 1000000000000000)
    return;

  if (numero != 0)
    lista[num_numeros++] = numero;
     
  if (digito1 == -1) {
    for (int i = 1; i < 10; i++) {
      gerar(i, -1, i);
    }
  }
  else if (digito2 == -1) {
    for (int i = 0; i < 10; i++) {
      if (i == digito1)
        gen(digito1, -1, numero * 10 + i);
      else
        gen(digito1, i, numero * 10 + i);
    }
  }
  else {
    gen(digito1, digito2, num * 10 + digito1);
    gen(digito1, digito2, num * 10 + digito2);
  }
}

// para preencher chamar gerar(-1, -1, 0)

A complexidade desta solução é dependente da quantidade de números diferentes com no máximo 2 dígitos, mas como já referimos esse valor é relativamente pequeno. Assim, se combinarmos esta solução com a anterior conseguiriamos aproximadamente 55 pontos.

Nota sobre representação de inteiros

Visto que os números podem ir até $10^{15}$, é imporante usar um tipo de inteiro que possa representar números tão grandes. Usar um simples int não é suficiente, em C++ é necessário usar um long long int e em Java um long.

Solução ótima

Claramente a estratégia anterior não é generalizável para valores de $K$ maiores. Por exemplo, para $K = 3$ há 2305947664 números entre $1$ e $10^{15}$ com no máximo 3 dígitos diferentes. Ainda assim há muita informação que podemos reaproveitar quando estamos a fazer as contas. Vamos considerar que estamos a contar a quantidade de números entre 10 e 23000 com 3 dígitos diferentes. Vamos supor que estamos de alguma forma a gerar números e que gerámos os números 121 e 112. De quantas formas podemos continuar a adicionar dígitos ao final do número 121 de forma a que os números resultantes sejam menores que 23000? E para 112? A resposta não parece óbvia, mas podemos fazer uma observação importante: é a mesma para 121 e 112! Visto que ambos usaram os mesmos dígitos até agora e podem ter ambos 5 dígitos, qualquer combinação que funcione para 121 funciona para 112.

Este tipo de propriedades costuma indicar que podemos fazer algum tipo de programação dinâmica. A ideia base de programação dinâmica é explorar a estrutura de um problema de forma a não calcular valores que já tenham sido calculados, exatamente como neste caso do 121 e 112. Se nunca ouviram falar programação dinâmica consultem o artigo relevante:

Artigo: Introdução a programação dinâmica

Este artigo contém uma introdução a programação dinâmica.

Vamos aplicar um tipo de programação dinâmica que é normalmente conhecida como digit dynamic programming (infelizmente ainda não há nenhum artigo do loop sobre este tema, em breve esperamos ter um). Neste estilo de programação dinâmica vamos aplicar o conceito de programação dinâmica aos próprios dígitos do número. Para simplificar a solução, vamos assumir que $A = 1$. Na verdade não estamos a simplificar nada, visto que o problema é o mesmo. Imaginemos que temos uma função $f(n, K)$ que calcula a quantidade de números entre $1$ e $n$ com no máximo $K$ dígitos. Se quisermos usar esta função para calcular o mesmo valor entre $A$ e $B$ basta calcular $f(B, K) - f(A - 1, K)$ e temos o pretendido. Por isso vamos assumir que só temos de calcular quantos números há entre 1 e um limite superior $B$.

Resumidamente, o que vamos fazer é o seguinte: vamos calcular o número de maneiras de preencher os dígitos de um número que obedece às restrições do problema (é menor que $B$ e usa no máximo $K$ dígitos) ao preenchê-lo do dígito mais significativo para o dígito menos significativo. Para simplificar a solução, vamos considerar números com zeros à esquerda, sendo que podemos ignorá-los alterando ligeiramente a solução posteriormente. Vamos usar o exemplo anterior, em que $B = 23000$ para ilustrar esta ideia. Se vamos preencher o primeiro dígito temos 3 hipóteses: 0, 1 ou 2. Se preenchermos o primeiro dígito com 0 ou 1, então os seguintes 4 dígitos podemos preencher com quaisquer dígitos, desde que não excedamos os $K$ diferentes. Se preenchermos com um 2 isso já não se verifica, por exemplo, para o segundo dígito não podemos preencher com um 4, caso contrário independentemente dos restantes dígitos já passámos o máximo de 23000 (o nosso número parcial seria 24???, onde os ? são dígitos por preencher). Assim, temos de distinguir o caso em que podemos preencher os próximo dígitos com qualquer valor ou se temos de ter atenção aos dígitos do número original.

Dito isto, vamos considerar o seguinte triplo como um estado da nossa programação dinâmica: (dígitos que já preenchemos; conjunto de dígitos que já usámos; podemos preencher qualquer valor ou não), isto é, para um dado triplo $(a, b, c)$ vamos calcular o número de possibilidades de preencher um número com no máximo $K$ dígitos sabendo que já preenchemos os primeiros $a$ dígitos, que usámos os dígitos no conjunto $b$ e que: se $c = 1$ podemos preencher os restantes com qualquer dígito; se $c = 0$ temos de ter atenção aos dígitos do número original. Se tivermos um algoritmo que calcule isto para qualquer triplo, então a resposta será o valor para o triplo $(0, {}, 0)$, onde ${}$ é um conjunto vazio.

Notem que o valor do triplo $(N, b, c)$, para qualquer $b$ ou $c$, é 1 se $b$ contiver no máximo $K$ dígitos e 0 se $b$ contiver mais de $K$ dígitos. Para os restantes triplos, podemos calcular o seu valor de forma recursiva. Vejamos um exemplo para o caso anterior, ou seja, $B = 23000$, em que queremos calcular o valor para o triplo $(0, {}, 0)$. Ora, como já tinhamos visto podemos preencher usando os dígitos 0, 1 e 2. Se preenchermos o primeiro dígito com 0 o número de maneiras de preencher os restantes é exatamente $(1, {0}, 1)$. Se preenchermos o primeiro dígito com 1 o número de maneiras de preencher os restantes é exatamente $(1, {1}, 1)$. Finalmente, se preenchermos o primeiro dígito com 2 o número de maneiras de preencher os restantes é exatamente $(1, {2}, 0)$. Se somarmos os valores para estes três triplos, temos o valor do triplo inicial. Podemos repetir o mesmo raciocínio para calcular o valor de qualquer triplo.

Assim torna-se evidente como aplicar programação dinâmica aqui: quando calcularmos o valor de um certo triplo $(a, b, c)$ guardamos esse valor e não o voltamos a calcular, quando voltarmos a precisar de o usar usamos o valor que temos guardado. Só nos falta acertar um último pormenor: como é que podemos guardar um conjunto numa array ou noutro objeto qualquer (visto que o segundo elemento de cada triplo é um conjunto)? A maneira mais óbvia é usar uma estrutura de dados, como um vector em C++ ou uma ArrayList em Java e guardar o triplo numa estrutura de dados de acesso logarítmico, como um set (árvore binária de pesquisa). Felizmente existe um truque mais simples para estes casos em que o número máximo de elementos do conjunto é pequeno (o conjunto tem no máximo 10 elementos, visto que só há 10 algarismos): bitmasking.

O conceito de bitmasking consiste em representar um conjunto num número. Para isso, vamos considerar a representação binária de um número (representação base 2), ou seja, em vez de 17 vamos usar 10001 ou em vez de 1243 vamos usar 10011011011. Vamos agora usar os dígitos binários do número para representar a presença ou ausência de elementos num conjunto, isto é, se o terceiro elemento estiver presente no conjunto então o terceiro dígito binário do número será um 1, se o quinto elemento estiver presente no conjunto então o quinto dígito binário do número será um 1, etc... sendo os restantes dígitos serão 0. Por exemplo, imaginemos que temos o conjunto ${1, 4, 7}$ e queremos representá-lo por um número, então o número em binário será 10010010 pois: o 0 não está no conjunto, logo o primeiro dígito (o mais à direita) é um 0; o 1 está no conjunto, logo o segundo dígito é um 1; o 2 não está no conjunto, logo o terceiro dígito é um 0; ... Em base 10 o número 10010010 é 146, logo o número 146 representa o nosso conjunto.

Para manipular os dígitos binários de um número podemos usar operações de adição e subtração usando potências de 2, mas existe uma forma mais simples e elegante. A maior parte das linguagens de programação modernas (incluindo, claro, C++ e Java) contêm um conjunto de operadores para manipular inteiros usando a sua representação binária. Estes operadores são conhecidos como bitwise operators. Há 3 relevantes para o nosso caso: o operador & "and", dados dois inteiros $a$ e $b$, $a$ & $b$ calcula a conjunção dos dígitos binários dos dois, por exemplo, em representação binária $11010$ & $10011 = 10010$ ou $26$ & $19 = 18$; o operador $|$ "or", dados dois inteiros $a$ e $b$, $a | b$ calcula a disjunção dos dígitos binários dos dois, por exemplo, em representação binária $11010 | 10011 = 11011$ ou $26 | 19 = 27$; o operador $<<$ "binary shift", dados dois inteiros $a$ e $b$, $a << b$ calcula a translação binária de $a$ por $b$ casas, ou seja, adiciona $b$ zeros à direita da representação binária de $a$, por exemplo, em representação binária $11010 << 3 = 11010000$ ou $26 << 3 = 208$. Para usarmos estes operadores, se $b$ for o número que representa o nosso conjunto, se quisermos adicionar o elemento 4 ao conjunto, basta fazermos $b | (1 << 4)$, pois $1 << 4$ representa a quarta potência de 2 e usando o operador "or" estamos a colocar o quinto dígito a 1 (o primeiro dígito é a potência 0, dai ser o quinto dígito). Se quisermos testar se o elemento 3 está no conjunto $b$ então basta fazermos $b$ & $(1 << 3)$, pois $1 << 3$ representa a terceira potência de 2 e usando o operador "and" estámos a ver o valor do quarto dígito binário de $b$, se este for 0 o elemento 3 não está em $b$, se for diferente de 0 está.

Finalmente, vamos à complexidade desta solução. Existem $N \cdot 2^K \cdot 2$ estados possíveis da nossa programação dinâmica: o primeiro elemento de cada triplo pode ter um de $N$ valores diferentes; o segundo elemento pode ter $2^K$, visto que há este número de conjuntos diferentes de $K$ elementos; o último elemento de cada triplo é ou 0 ou 1. Para cada estado, podemos fazer no máximo 10 operações, correspondentes a tentar colocar cada um dos 10 possíveis algarismos como próximo dígito. Ou seja a complexidade final é $O(N \cdot 2^K \cdot 20)$, visto que $K$ é no máximo 10, esta solução é bastante rápida e obtém os 100 pontos.

Nota final

Esta técnica de programação digit dynamic programming é muito útil em diferentes tipos de problemas onde nos pedem quantos números num intervalo obedecem a uma certa propriedade relativa aos seus dígitos. Por exemplo, se o problema for: quantos números há entre $A$ e $B$ tal que a soma dos seus dígitos é $K$? Por exemplo, há 4 números entre 20 e 100 cuja soma dos dígitos é 5: 23, 32, 41 e 50. Podemos usar a mesma técnica, mas modificando ligeiramente os triplos da nossa solução anterior. Já não nos interessa os dígitos que usámos, mas sim a soma dos dígitos até agora, isto é, o segundo elemento do triplo conteria a soma dos dígitos que já preenchemos.

Dito isto, conseguem agora resolver alguns dos problemas antigos das ONI com este estilo de pergunta? Um exemplo é o problema A da final das ONI 2016. Como é que podemos representar a existência de padrões como parte dos triplos da nossa programação dinâmica?