Problema A - Frota Imperial

Tipo de problema: Matemática/Pesquisa
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

O Problema
Dada um conjunto de N intervalos de números, a tua tarefa é descobrir, para cada intervalo, qual o(s) dígito(s) que aparece mais vezes, bem como quantas vezes ele aparece.

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

Solução Base:
A solução mais simples para este problema passava por passar por todos os números entre A e B e contar os dígitos de cada um. Para isto era apenas necessário um ciclo que fosse de A a B. Depois, para contar os dígitos de cada número nesse intervalo era apenas necessário considerar o último dígito (que se pode obter fazendo o módulo de um número por 10: num % 10) e ir dividindo por 10 (contando sempre o último dígito) até chegar a 0. Por exemplo, para contar os dígitos do número 234, primeiro contamos o dígito 4 (234 % 10 = 4), depois dividimos por 10 (234 / 10 = 23) obtendo o número 23, contamos o dígito 3 (23 % 10 = 3), dividimos novamente por 10 (23 / 10 = 2) obtendo o número 2, contamos o dígito 2 (2 % 10 = 2) e finalmente dividimos por 10 obtendo 0 e terminamos a contagem.

Esta seria uma solução O(N * B) que daria aproximadamente 40 pontos.

Somas Acumuladas:
Uma solução melhor seria recorrer à técnica de somas acumuladas. A ideia é pré-calcular o número de ocorrências de um determinado dígito até cada número entre 1 e o número máximo. Consideramos uma matriz sum[num][dig] que representa todas as ocorrências do dígito dig em todos os números de 1 a num. Para calcular o valor para cada entrada desta matriz, basta fixar um número num e considerar que para cada dígito dig o valor de sum[num][dig] é igual a sum[num - 1][dig] mais o número de ocorrências do dígito dig no número num. Notem que temos de considerar um caso base, por exemplo que sum[0][dig] é igual a 0 para todos os dígitos menos o próprio 0.

Com esta matriz pré-calculada, o número de ocorrências do dígito dig num intervalo de A a B é simplesmente: sum[B][dig] - sum[A - 1][dig].

A única limitação deste método é que requer muita memória se os números do intervalo forem grandes (é impossível manter uma matriz de 1,000,000,000 por 10), por isso, ainda que a sua complexidade temporal seja reduzida, a solução não funciona para a pontuação total por falta de espaço na memória.

Esta seria uma solução O(N + B) que daria aproximadamente 60 pontos.

Solução Ótima:
A melhor solução seria considerar o aspeto matemático do problema e aproveitar a estrutura dos números para resolver o problema. A ideia é de em vez de considerar cada número individualmente, considerar intervalos de números. Para explicar a ideia vamos recorrer a um exemplo:

Consideremos o intervalo [102, 533]. Primeiramente fazemos uma contagem no dígito das unidades até que este seja 0, ou seja, consideramos o intervalo de [102, 110] e contamos o número de dígitos de cada número dentro deste intervalo. A razão pela qual queremos intervalos assim é porque agora contar de 110 até 120 não requer que contemos individualmente todos os números entre eles, pois como há exatamente 10 números entre os dois, contamos mais 1 vez cada dígito e adicionalmente contamos o resto dos algarismos do número (neste caso dois 1s: 11x) mais dez vezes. Agora podemos repetir este processo de 10 em 10 considerando apenas os intervalos de 120 a 130, 130 a 140, ..., 190 a 200. Porém agora podemos aplicar um raciocínio semelhante visto que do número 200 ao número 300 existem 100 números, ou seja, para este intervalo contamos mais 20 vezes cada dígito (20 porque cada dígito aparece 10 vezes por posição, como há duas posições, resulta em 20, se o intervalo fosse de 1000 para 2000, exemplo, já existeriam 3 posições e cada número aparece 100 vezes por posição, por isso daria 300 ocorrências e o mesmo para números maiores) mais resto dos algarismos 100 vezes (neste caso é apenas um 1: 1xx), pois há 100 números neste intervalo que começam pelo primeiro dígito. Agora aplicamos o mesmo raciocínio de 200 a 300, 300 a 400 e de 400 a 500. O 500 é um caso novo, porque agora queremos um intervalo menor, de 500 a 533, mas na verdade podemos aplicar os mesmo raciocínios que já aplicámos. Assim consideramos o intervalo de 500 a 510 e contamos mais 1 vez cada dígito mais 10 vezes o resto dos algarismos do número (neste caso um 5 e um 0: 50x). A mesma coisa para os intervalos 510 a 520 e de 520 a 530. Aqui voltamos à regra do início e contamos o número de dígitos no intervalo 530 a 531 ao contarmos mais 0 vezes cada dígito (pois, segundo o nosso raciocínio anterior, não há nenhum dígito a variar) mais o resto dos algarismos 1 vez (que neste caso são todos os algarismos, ou seja, um 5, um 3 e um 0: 530), pois o intervalo de valores é de 1. Aplicamos a mesma coisa de 531 a 532 e de 532 a 533 e voilá, contámos todos as ocorrências de dígitos no intervalo pedido.

Analisar a complexidade desta solução não é muito fácil, mas se ignorarmos as constantes (que serão todas múltiplos de 10, pois estamos sempre a contar 10 dígitos) temos que cada intervalo depende dos valores de A e B, mas para cada ordem de grandeza a diferença máxima é de 10 (pois cada a diferença entre dois algarismos é no máximo 10). Logo a complexidade apenas depende do número de algarismos dos números no intervalo, que é equivalente ao logarítmo de base 10 do número. Notem também que em termos de espaço esta solução apenas precisa de uma matriz para cada dígito (para guardar a contagem de cada dígito), logo consegue abranger intervalos maiores do que a solução anterior.

Esta seria uma solução O(N * log (B)) que daria aproximadamente 100 pontos.

Ligações interessantes:

• Somas Acumuladas na Wikipedia.