Eventos com inscrição prévia, do Fórum Internacional do Software Livre às plenárias do Congresso do PSOL nas grandes cidades, costumam ter mesas de credenciamento pelas quais os presentes precisam passar para pegar um crachá.

Quando há muitos participantes é comum que as letras do alfabeto sejam separadas entre essas mesas, de forma a dividir as pessoas pelas iniciais dos seus nomes e assim reduzir o tempo de espera nas filas que se formam.

Exemplo: Se há três mesas de credenciamento, pode-se atribuir a elas os intervalos letras A-I, J-R e S-Z. Nesse caso, alguém com um nome que comece com B (como Bruno) deve se credenciar na mesa A-I, enquanto alguém com um nome que comece com T (como Tiago) deve se credenciar na mesa S-Z.

Uma dificuldade conhecida por todos que já organizaram eventos desse tipo é que alguns particionamentos do alfabeto podem levar a formar umas filas grandes e outras pequenas. Em particular, deixar o mesmo número de letras em cada conjunto costuma ser uma estratégia muito ineficiente, porque em português muitos nomes começam com as letras A, J e M, mas poucos começam com as letras Q, U e X.

O problema que surge a partir dessa constatação é: Como dividir as letras do alfabeto de forma a garantir que o número de participantes por mesa esteja o mais equilibrado possível?

Há uma restrição: As letras precisam ser divididas de forma que formem partições contíguas na ordem alfabética. Isso é, não se pode definir que A e C ficam num conjunto 1, enquanto B fica num conjunto 2. Se A e C estão no conjunto 1, todas as letras entre A e C (B, no caso) também precisam estar no conjunto 1.

Trata-se claramente de um problema de otimização. Para desenvolver um algoritmo (que nada mais é do que um procedimento computacional) para resolvê-lo, convém definir o que esperamos como entrada e o que esperamos como saída.

Entrada:

• $n$: número de letras no alfabeto
• $a_i$: número de participantes que começam com a $i$-ésima letra do alfabeto ($1 \leq i \leq n$).
• $k$: número de mesas de credenciamento (partições que devem ser formadas)

Saída:

• $c_i$: primeira letra da $i$-ésima partição do alfabeto ($1 \leq c_i \leq n$, $1 \leq i \leq k$)

Um parênteses: Enquanto este texto era escrito, o governo do Distrito Federal começou uma campanha de vacinação contra a influenza dividindo idosos em 5 grupos a partir das suas iniciais. De acordo com a Agência Brasil,

• Na segunda-feira (23), devem ser vacinados os idosos cujo nome comece com as letras A, B, C, D e E.
• Na terça-feira (24), pessoas com 60 anos ou mais com nomes iniciados pelas letras F, G, H, I e J.
• Na quarta-feira (25), idosos que tenham nas letras iniciais do nome K, L, M, N e O.
• Na quinta-feira (26), pessoas com 60 ou mais com o primeiro nome iniciado em P, Q, R, S e T.
• Na sexta-feira (27), devem se vacinar os idosos com nomes que comecem com U, V, W, X, Y e Z.

É fácil ver que esse governo teve que resolver o problema proposto aqui para separar as pessoas em 5 dias (que seriam equivalentes a mesas de credenciamento, na nossa formulação). Terá ele feito uma escolha ótima? Infelizmente acho difícil que os idosos que tenham nomes começando com letras entre A e E não tenham que esperar muito mais tempo na fila do que os idosos que tenham nomes começando com letras entre U e Z.

Como definir equilíbrio?

Idealmente gostaríamos de dividir os conjuntos de nomes igualmente. Se $t = \sum a_i$ é o número total de participantes do evento (a soma dos números de participantes com cada letra do alfabeto) e $k$ é o número de mesas de credenciamento, então o número de participantes que gostaríamos de colocar em cada mesa é $\frac{t}{k}$.

Há diferentes formas de medir o quão longe um valor se encontra do seu valor esperado. Uma das medidas mais populares, que decidi usar aqui, é o desvio padrão.

Se $x_i$ é o número de participantes que devem se credenciar na $i$-ésima mesa (para $i$ variando de 1 a $k$), então o desvio padrão dessa solução é:

Exemplo: Suponha que temos 42 nomes que começam com A, 25 nomes que começam com B e 33 nomes que começam com C. Então temos $a_1 = 42$, $a_2 = 25$, $a_3 = 33$ e $t = a_1 + a_2 + a_3 = 42 + 25 + 33 = 100$. Suponha que precisamos dividir esses nomes em duas mesas de credenciamento, portanto $k = 2$. Podemos dividir as pessoas de duas formas diferentes:

1. A e B-C.
2. A-B e C.

Na primeira solução, temos uma mesa com 42 pessoas e outra mesa com 58 (25+33). Na segunda solução, termos uma mesa com 67 pessoas (42+25) e outra mesa com 33. Note que $\frac{t}{k} = \frac{100}{2} = 50$.

Então o desvio padrão da primeira solução é

$$\sigma_1 = \sqrt{\frac{1}{2} ((42-50)^2 + (58-50)^2)} = 8$$

e o desvio padrão da segunda solução é

$$\sigma_2 = \sqrt{\frac{1}{2} ((67-50)^2 + (33-50)^2)} = 17.$$

Como $\sigma_1 < \sigma_2$, dizemos que a primeira solução é mais equilibrada do que a segunda. Nosso objetivo, portanto, é encontrar uma solução que minimize o desvio padrão.

(Note que o desvio padrão nunca é negativo e a solução ideal para o nosso problema, que divide os participantes perfeitamente, tem desvio padrão 0.)

Se você quiser tentar resolver o problema antes de ler sobre a solução, pare de ler aqui. Caso contrário, pode continuar a leitura.

Abordagem gulosa

Uma solução que que alguém poderia sugerir é inicialmente dividir a lista de nomes em $k$ partes e aí tentar, para cada um dos cortes, decidir se é melhor deslocá-lo para frente ou para trás. Talvez uma forma razoável de tomar essa decisão seja ver qual delas minimiza o desvio padrão para o conjunto que estamos deixando para trás.

Exemplo: Suponha que $a_1 = 42, a_2 = 25, a_3 = 27, a_4 = 18, a_5 = 38$ e $k = 3$. Então $\frac{t}{k} = \frac{150}{3} = 50$.

A solução proposta inicialmente divide esses nomes em 3 partes iguais. Os cortes das divisões estariam (1) entre o oitavo e o nono nome da letra B e (2) entre o sexto e o sétimo nome da letra D.

Para diminuir o desvio padrão do primeiro conjunto é melhor mover o primeiro corte para entre as letras A e B, porque 42 é mais próximo de 50 (diferença 8) do que 67 (diferença 17). Já para diminuir o desvio padrão do segundo conjunto é melhor mover o segundo corte para entre as letras C e D, porque 52 é mais próximo de 50 (diferença 2) do que 70 (diferença 20).

A solução encontrada portanto separa as letras em A, B-C e D-E.

Esse tipo de solução é chamado, na Ciência da Computação, de “guloso” (greedy, em inglês). As técnicas gulosas são aquelas que procuram soluções locais ótimas na esperança de encontrarem uma solução global ótima. Note que na solução sugerida otimizamos corte por corte (localmente), sem pensar muito sobre o que nos espera no futuro (global).

Algoritmos gulosos, quando encontram a solução ótima, são uma beleza: normalmente são fáceis de escrever e super rápidos. Porém, nem sempre algoritmos gulosos que funcionam para alguns casos funcionam para todos. Para não nos enganarmos, é sempre bom provar a corretude de um algoritmo guloso, isso é, provar matematicamente que ele funciona para todas as entradas. Já para provar que um algoritmo guloso não funciona basta apresentar um contra-exemplo, isso é, uma entrada para o qual o algoritmo guloso não produz a saída esperada.

Uma tentativa de explicar melhor, em termos lógicos, o parágrafo acima: Suponha que representemos nosso algoritmo como uma função $f$. Uma entrada é representada por $x$ e a saída esperada para $x$ é representada por $y$. Então, se o algoritmo funciona, esperamos que $\forall x (f(x) = y)$ (isso é, para todo $x$, o algoritmo leve $x$ em $y$). A negação dessa proposição lógica é $\exists x (f(x) \neq y)$ (isso é, existe $x$ tal que o algoritmo não leva $x$ em $y$). É por isso que para provar que um algoritmo não funciona para todas as entradas basta apresentar um contra-exemplo.

Afirmo que o algoritmo guloso apresentado acima não é capaz de encontrar a solução ótima para todas as entradas. Você é capaz de construir um contra-exemplo para provar isso?

Se quiser tentar construir um contra-exemplo por sua conta, pare de ler aqui. Caso contrário, pode continuar a leitura para ver o meu contra-exemplo.

Contra-exemplo: Suponha que temos 120 nomes, sendo que 35 começam com A, 8 com B, 27 com C e 50 com D. Queremos dividí-los em três mesas de credenciamento. Então temos $a_1 = 35, a_2 = 8, a_3 = 27, a_4 = 50$ e $k = 3$.

A abordagem gulosa inicialmente divide esses nomes em três partes iguais, conforme ilustração a seguir.

Então, corte por corte, vamos tentar minimizar o desvio padrão do conjunto de nomes que estamos deixando para trás. Para minimizar o desvio padrão do primeiro conjunto é melhor mover o primeiro corte para entre as letras B e C, porque 43 (35+8) é mais próximo de 40 do que 35. Já para minimizar o desvio padrão do segundo conjunto é melhor mover o segundo corte para entre as letras C e D. A solução encontrada pelo algoritmo guloso é portanto separar as letras nos conjuntos A-B, C e D.

O desvio padrão dessa solução é:

$$\sigma_g = \sqrt{\frac{1}{3} (3^2 + 13^2 + 10^2)} \approx 16.67.$$

Essa solução não é ótima para essa entrada, porque se tivéssemos colocado o primeiro corte entre A e B conseguiríamos um desvio padrão menor:

$$\sigma_\star = \sqrt{\frac{1}{3} (5^2 + 5^2 + 10^2)} \approx 12.25.$$

Logo, o algoritmo guloso não funciona para todas as entradas.

O contra-exemplo mostra como ótimos locais não implicam num ótimo global. A gulodice aqui não funcionou, por isso talvez seja melhor construir um algoritmo usando outras técnicas.

Força bruta

Como o computador é uma máquina capaz de executar bilhões de instruções por segundo (é exatamente isso que é medido pelos Hz que usamos para medir os processadores), uma forma de resolver problemas de otimização sem pensar muito é enumerar todas as soluções possíveis e compará-las. Essa abordagem é chamada, na Ciência da Computação, de força bruta (não confundir com bater nas pessoas para elas não reclamarem da fila de credenciamento).

Uma forma intuitiva de resolver este problema testando todas as soluções é construir um algoritmo recursivo que, a cada passo, faça um novo corte dividindo as letras que restam. Isso é, no primeiro passo tentamos colocar um corte entre todo par adjacente de letras, nos restantes tentamos colocar um corte entre todo par adjacente de letras a direita dos cortes já feitos.

Construiremos uma função recursiva $f$ que recebe dois parâmetros: $s$ é o índice da primeira letra do que resta no alfabeto e $m$ é o número restante de mesas que devem ser formadas. $f(s, m)$ vai retornar uma variância não normalizada (que para todos os efeitos é igual ao desvio padrão, porque minimiza ele) da solução ótima considerando as letras a partir de $s$ e dividindo-as em $m$ mesas de credenciamento.

Uma nota sobre desvio padrão e variância: A variância é o desvio padrão ao quadrado (isso é, sem tirar a raiz quadrada), ou seja, $\frac{1}{k} \sum_{i=1}^k \left(x_i - \frac{t}{k}\right)^2$. Como minimizar um número é a mesma coisa que minimizar ele ao quadrado, usamos a variância para não precisarmos nos preocupar em ficar tirando raízes no código. Esse valor $\frac{1}{k}$ é constante. Então o que chamei de variância não normalizada aí em cima é simplesmente $\sum_{i=1}^k \left(x_i - \frac{t}{k}\right)^2$. Minimizar esse valor é a mesma coisa que minimizar o desvio padrão. Nos parágrafos seguintes, chamarei simplesmente de variância o que aqui defini como variância não normalizada.

Vamos considerar que o vetor $a$ de números de nomes por letra é global, assim como o tamanho do alfabeto $n$ e o valor $\mu$ (mu, no código) que é a média $\frac{t}{k}$ que usaremos para computar a variância da solução. Estamos interessados na solução de $f(0, k)$, que é a solução do nosso problema porque é a variância da solução ótima considerando todas as letras e dividindo em $k$ mesas de credenciamento.

Essa recursão tem alguns casos-base para os quais podemos retornar imediatamente valores computados diretamente, a saber:

• $f(n, 0) = 0$ — isso é, se não há letras para serem divididas em conjuntos e não há cortes a serem feitos, então a variância da solução é 0 (não há nada a ser feito).
• $f(s, 0) = \infty$ para qualquer $s \neq 0$ — isso é, se há letras para serem divididas em conjuntos, mas não há mesas para colocá-las, então a variância da solução é infinita (o problema não tem solução).
• $f(n, m) = m \mu^2$ para qualquer $m \neq k$ — isso é, se não há letras para serem divididas e há $m$ mesas, então a variância da solução é $m\mu^2$ porque estamos somando $m$ mesas vazias (com 0 pessoas).

Para os demais $s, m$, temos:

Ou seja, fazemos todos os cortes possíveis (eles são representados por $i$) e minimizamos a variância correspondente a fazê-los: estamos somando a variância do conjunto $[s, i]$ (primeiro parâmetro da soma) com a variância da solução ótima para o conjunto $[i+1, n)$ com $m-1$ mesas (segundo parâmetro da soma).

Então o código da solução usando força bruta, em Python (linguagem escolhida porque está na moda), ficaria como segue:

a = [...]  # parâmetro de entrada (vetor com número de nomes por letra)
k = ...    # parâmetro de entrada (número de mesas)

n = len(a)       # tamanho do alfabeto
mu = sum(a) / k  # média usada para calcular as variâncias (t/k)

inf = float('inf')  # infinito

def f(s, m):
    if s == n and m == 0:
        return 0
    if m == 0:
        return inf
    if s == n:
        return m * mu * mu

    menor = inf
    soma = 0
    for i in range(s, n):
        soma += a[i]
        variancia = (mu - soma) ** 2
        resto = f(i+1, m-1)
        if variancia + resto < menor:
            menor = variancia + resto

    return menor

print("A variância da solução ótima é:", f(0, k))

Essa solução funciona (provar isso é um exercício de indução matemática: prova-se a solução dos casos-base e depois que subsoluções ótimas garantem soluções ótimas). Note que ela tem uma semelhança com o algoritmo guloso na medida em que a cada passo nos preocupamos com uma mesa (corte), porém ela testa todas as possibilidades possíveis de corte em vez de escolher gulosamente onde fazer cada corte.

O problema da força bruta é seu tempo de execução. Por mais rápido que sejam nossos computadores, custos exponenciais não são razoáveis para resolver problemas com entradas suficientemente grandes.

Uma observação sobre o universo: Segundo o consenso científico, o número de átomos no universo observável é por volta de $10^{80}$. Já a idade do universo é cerca de 14 bilhões de anos ($1.4 \times 10^{10}$), o que equivale a cerca de $4.4 \times 10^{26}$ nanossegundos. Suponha que todos os átomos do universo estejam, desde o surgimento do universo, realizando uma instrução computacional por nanossegundo, ou seja, cada átomo do universo seja um computador operando a 1GHz. Então até agora eles teriam realizado cerca de $4.4 \times 10^{106}$ operações. Se o tempo de execução de um algoritmo é exponencial no tamanho da entrada, o universo todo não é capaz de executá-lo para entradas suficientemente grandes — e “grande” nessa colocação são números que consideraríamos razoáveis, como 50 ou 100.

Testar todas as possibilidades costuma levar um tempo exponencial no tamanho da entrada, e no nosso problema não é diferente.

Um esboço relaxado para computar o tempo de execução da força bruta: Para medir o custo de um algoritmo recursivo, temos que construir e resolver uma recorrência. No nosso caso, temos:

$$T(n, k) = \sum_{i=1}^n T(n-i, k-1),$$

onde $T(n, k)$ denota o número de operações necessárias para resolver o problema com entrada $n, k$. Com alguma manipulação algébrica, podemos ver que, para $n > 1$, vale:

$$T(n, k) = T(n-1, k) + T(n-1, k-1),$$

que é exatamente a propriedade dos coeficientes binomiais conforme conferimos no Triângulo de Pascal. Os casos-base são um pouco diferentes dos coeficientes binomiais, por isso não se trata exatamente de dizer que o número de operações da solução seja ${n \choose k}$, mas dá para dizer que se aproxima disso por alguma constante. Portanto, o custo é exponencial no tamanho da entrada, na ordem de $2^n$.

Talvez seja razoável afirmar que a solução com força bruta é suficiente para o escopo do nosso problema quando estamos limitados ao alfabeto latino, que tem 26 letras. Porém, o que fazer caso o alfabeto seja maior — tenha, digamos, 1000 letras? Um algoritmo exponencial não é capaz de terminar na idade do universo neste caso nem com todos os átomos do universo trabalhando para isso. Isso nos motiva a usar programação dinâmica.

Programação dinâmica

Programação dinâmica, diferente do que o nome indica, não tem nada a ver (ao menos diretamente) com programação de computadores. Na verdade, há quem diga que um nome mais adequado para esse método de otimização de programas seria “recursão com uma tabela”.

Muitas vezes um subproblema é resolvido diversas vezes dentro de um procedimento recursivo; em particular, é fácil ver que isso acontece na força bruta proposta na seção acima. Note que $f(1, 3$) precisa do resultado de $f(2, 2), f(3, 2), f(4, 2), \cdots$ e também que $f(2, 3)$ precisa do resultado de $f(3, 2), f(4, 2), \cdots$. A tabela abaixo, mostrando a árvore de recursão para resolver o problema para $n = 6$ e $k = 4$, mostra que várias computações estão sendo repetidas.

A ideia da programação dinâmica é simplesmente tabelar os resultados da recursão para não precisar recalculá-los várias vezes. Usando programação dinâmica, tudo que está em vermelho na ilustração acima pode ser diretamente retornado pela função — não é preciso recomputar $f(s, m)$ mais de uma vez para nenhum par $s, m$.

A forma mais direta de implementar programação dinâmica em cima de um algoritmo recursivo é simplesmente guardar cada resultado da recursão numa tabela e usar os resultados já guardados previamente. Modificando o código da força bruta, temos:

# A linha abaixo inicializa com -1 uma matriz (n+1)x(k+1). Python é esquisito.
pd = [[-1 for i in range(k+1)] for j in range(n+1)]

def f(s, m):
    if s == n and m == 0:
        return 0
    if m == 0:
        return inf
    if s == n:
        return m * mu * mu
    if pd[s][m] != -1:
        # Já temos o resultado de f(s, m) e podemos retorná-lo diretamente.
        return pd[s][m]

    menor = inf
    soma = 0
    for i in range(s, n):
        soma += a[i]
        variancia = (mu - soma) ** 2
        resto = f(i+1, m-1)
        if variancia + resto < menor:
            menor = variancia + resto

    return pd[s][m] = menor

O número de operações agora é proporcional a $kn^2$, que é um valor polinomial no tamanho da entrada — ou seja, a programação dinâmica reduziu a complexidade exponencial do nosso problema e agora podemos resolvê-lo para alfabetos muito maiores. Para alfabetos de até mil letras e para até mil mesas de credenciamento um computador comum deve ser capaz de dar uma solução para o problema de forma eficiente em cerca de 1s. Mais importante, a medida que considerarmos alfabetos maiores o tempo de execução só aumenta por um fator polinomial — não mais exponencial.

A recursão, na solução com programação dinâmica, pode facilmente ser transformada em iterações. Para fazer isso, basta garantir que a tabela seja preenchida na ordem correta: não podemos tentar acessar alguma coisa que ainda não foi computada. O código abaixo mostra como poderia ficar uma implementação iterativa da programação dinâmica:

# Casos-base.
for m in range(k+1):
    pd[n][m] = m * mu * mu
for s in range(n+1):
    pd[s][0] = inf
pd[n][0] = 0

for s in range(n-1, -1, -1):
    for m in range(1, k+1):
        menor = inf
        soma = 0
        for i in range(s, n):
            soma += a[i]
            variancia = (mu - soma) ** 2
            resto = pd[i+1][m-1]
            if variancia + resto < menor:
                menor = variancia + resto
        pd[s][m] = menor

Por isso a programação dinâmica é muitas vezes apresentada como uma estratégia bottom-up e não top-down.

Programação dinâmica é uma técnica recorrente em problemas de olimpíadas de programação, como OBI, ACM ICPC, TopCoder, CodeForces, Google Code Jam e Facebook Hacker Cup, e possui muitas aplicações no mundo real. A Wikipedia tem uma lista de algoritmos clássicos que usam programação dinâmica.

Recuperando a solução

Nas seções anteriores apresentei alguns códigos que, embora encontrem o desvio padrão da solução ótima, não nos dizem qual é a solução — isso é, onde devem ser feitos os cortes. Há diversas formas de recuperar a solução a partir dos algoritmos mostrados. Uma que demandaria uma alteração simples nos códigos seria criar uma outra matriz $n \times k$ que guarda, para cada par $(s, m)$ o ponto em que fizemos o $m$-ésimo corte.

Para recuperar a solução, basta usar essa informação. O código completo ficaria como segue:

from typing import List

def final(a: List[int], k: int):
    """Exemplo de uso: final([35, 8, 27, 50], 3)"""
    n = len(a)       # tamanho do alfabeto
    mu = sum(a) / k  # média usada para calcular as variâncias (t/k)

    inf = float('inf')  # infinito

    pd = [[-1 for i in range(k+1)] for j in range(n+1)]
    sol = [[0 for i in range(k+1)] for j in range(n+1)]

    for m in range(k+1):
        pd[n][m] = m * mu * mu
    for s in range(n+1):
        pd[s][0] = inf
    pd[n][0] = 0

    for s in range(n-1, -1, -1):
        for m in range(1, k+1):
            menor = inf
            soma = 0
            for i in range(s, n):
                soma += a[i]
                variancia = (mu - soma) ** 2
                resto = pd[i+1][m-1]
                if variancia + resto < menor:
                    menor = variancia + resto
                    sol[s][m] = i
            pd[s][m] = menor

    print("A variância da solução ótima é:", pd[0][k])

    # soma[i] vale a soma dos numeros de a[0...i-1].
    soma = [0 for i in range(n+1)]
    soma[0] = 0
    for i in range(1, n+1):
        soma[i] = soma[i-1] + a[i-1]

    print("Partições:")
    s = 0
    for l in range(k):
        e = sol[s][k-l]
        print("%d. %d-%d (tamanho: %d)" % (l+1, s, e, soma[e+1] - soma[s]))
        s = e + 1

A saída desse programa para final([35, 8, 27, 50], 3) (entrada usada como contra-exemplo para o algoritmo guloso) é, como esperado:

A variância da solução ótima é: 150.0
Partições:
1. 0-0 (tamanho: 35)
2. 1-2 (tamanho: 35)
3. 3-3 (tamanho: 50)

(No alfabeto latino, A=0, B=1, C=2, D=3, etc.)

Finalmente

A ideia desse artigo foi mostrar como um problema real pode ser solucionado por meio de diferentes técnicas de projeto de algoritmos. Conhecer essas técnicas é útil para se abordar diversos problemas; não à toa elas são tão valorizadas em competições de programação. Espero que o artigo tenha utilidade para os que se interessarem em estudar Ciência da Computação durante esse estranho período em que muitos estamos fisicamente isolados.

Agradecimentos ao Pedro, que me apresentou o problema; ao Ulysses, que comentou que o problema apareceu na distribuição das vacinas do governo do Distrito Federal; e a todo mundo que chegou até aqui, pela leitura. Comentários são muito bem-vindos.

Tabelas de preços de impressão são interessantes. É muito comum que quanto mais você imprima mais baratas as impressões fiquem, fazendo com que o gráfico de preço por impressões não seja monótono (isso é, você não necessariamente pague mais por um número maior de impressões).

Isso torna as gráficas boas candidatas de lugares para pensar em gráficos de funções de primeiro grau, assim como a busca binária é uma boa candidata de aplicação para pensar sobre logaritmos.

Hoje fui imprimir uma partitura e me deparei com a seguinte tabela:

(registrada em uma foto de um bilhão de dólares)

Se desenharmos um gráfico de preço (eixo y — vertical) por número de impressões (eixo x — horizontal), temos:

Observando esse gráfico (feio), percebemos que há alguns números de impressões que economicamente não faz sentido fazer. Por exemplo, 3 impressões custam R$ 2,10 enquanto 4 impressões custam R$ 2,00. 20 impressões custam R$ 8,00 enquanto 21 impressões custam R$ 6,30. 100 impressões custam R$ 25,00 enquanto 101 impressões custam R$ 20,20.

Mas não só esses. Os valores que não faz sentido imprimir no gráfico são todos aqueles cujo existe algum ponto a direita na mesma altura ou mais baixo, ou seja, todos os que pintei de amarelo:

Um problema econômico interessante para quando se está numa gráfica imprimindo é, portanto, descobrir quando estamos nos pontos amarelos. É interessante porque, se estivermos nos pontos amarelos, podemos aproveitar para imprimir mais cópias ou pedir ao dono da gráfica um desconto. Afinal, é razoável esperar que o preço que a gente pague seja limitado por este gráfico:

Descobrir se estamos numa região amarela é simples. Basta calcular o preço que pagaríamos a princípio (multiplicar o número de cópias pelo preço por cópias da região em que estamos) e comparar com o preço que pagaríamos se pedíssemos o menor número de cópias da região imediatamente mais barata. Por exemplo, faz sentido imprimir 15 cópias porque $15 \times 0.40=6.00$ é menor do que $21 \times 0.30 = 6.30$, mas não faz sentido imprimir 85 cópias porque $85 \times 0.25 = 21.25$ é maior do que $101 \times 0.20 = 20.20$.

Agora vamos inverter o problema. Vamos supôr que você é a gráfica e quer evitar esse tipo de cliente insuportável, fazendo o preço ir ficando mais barato proporcionalmente com o número de impressões, mas mantendo a função monótona (crescendo).

Poderíamos pensar em funções que crescem cada vez mais devagar…

… mas parece complicado achar uma função que não nos dê prejuízo quando o cliente quiser muitas cópias e parece especialmente complicado explicar para o cliente que o preço de x cópias é um monte de constantes multiplicadas pelo logaritmo de x.

Então talvez seja melhor pensar em funções de primeiro grau mesmo.

Se você separar todas as funções que encontramos na tabela de preços do problema anterior e colocá-las num gráfico, você vai ver que a interseção delas só acontece num ponto: o ponto x = 0.

(esse gráfico foi um oferecimento Wolfram Alpha)

Uma forma de resolver o problema é fazer com que as interseções sejam nos pontos onde o preço das impressões muda. Isso se faz movendo cada uma das funções um pouquinho pra cima, isso é, adicionando constantes às funções de primeiro grau.

Por exemplo: 3 cópias custam R$ 2,10. Se a partir de 4 cópias quisermos que as cópias custem R$ 0,50 em vez de R$ 0,70, podemos forçar que 4 cópias custem R$ 2,10 + R$ 0,50 = R$ 2,60. R$ 2,60 é R$ 2,00 + R$ 0,60. Logo, em vez de usarmos a função de preço $f(x) = 0.5x$ para $x$ entre 4 e 10, podemos usar a função $f(x) = 0.5x + 0.6$.

Se repetirmos o mesmo raciocínio para as outras interseções, a tabela de preços final fica assim:

(Isso aqui é só um exercício. Por favor, não façam isso, donos de gráficas!)

Agora note que as coisas passam a fazer mais sentido (embora muito mais caras):

• 3 cópias custam R$ 2,10 e 4 cópias custam R$ 2,60;
• 10 cópias custam R$ 5,60 e 11 cópias custam R$ 6,00;
• 20 cópias custam R$ 9,60 e 21 cópias custam R$ 9,90;
• 50 cópias custam R$ 18,60 e 51 cópias custam R$ 18,85;
• 100 cópias custam R$ 31,10 e 101 cópias custam R$ 31,30.

O gráfico monótono (e bonito) comprova:

Imagine-se num prédio de 100 andares com várias bolas. A partir de um determinado andar (desconhecido), quando você joga uma bola pela janela, a bola quebra. Você quer determinar precisamente qual é esse andar e a única coisa que pode fazer é jogar bolas de andares diferentes.

Se você tem muitas bolas e não se importa em quebrar quantas forem necessárias, você pode realizar uma busca binária. Uma busca binária, para começar com um exemplo, é aquilo que você faz naquele diálogo clássico:

— Pense num número de 1 a 100 e eu vou tentar adivinhar. A cada palpite, você precisa me dizer se o número que você pensou é maior ou menor do que meu chute.
— Pensei.
— 50
— Maior.
— 75
— Menor.
— 63
— Menor.
— 57
— Menor.
— 54
— Menor.
— 52
— Menor.
— 51
— Acertou!

A cada passo numa busca binária você divide o intervalo de possibilidades por dois. Você descarta metade dos números que poderiam ser a solução. Por isso, mesmo que você pense num número de 1 a 1.000.000.000 (um bilhão) eu certamente não vou demorar mais de 30 (isso é, logaritmo de um bilhão na base dois) tentativas para acertar exatamente o número que você pensou.

Por que logaritmo de um bilhão na base dois? Como eu comentei anteriormente, a cada número que eu chuto e você diz se é maior ou menor do que o resultado eu corto meu intervalo por dois. Portanto, o número de chutes necessários (no pior caso) é precisamente a quantidade de vezes que preciso dividir um bilhão por dois até chegar a um (até sobrar um único número possível para eu chutar, que necessariamente vai ser o número que você pensou).

Nosso problema é encontrar quantos 2 tem aí. Dividir um número por 2 k vezes é o mesmo que dividir por $2^k$. Logo, nosso problema é encontrar quanto vale k:

Multiplicando os dois lados da igualdade por $2^k$, temos:

Tirando o logaritmo na base 2, concluímos:

Ou seja, o logaritmo de n na base 2 é o número de vezes que precisamos dividir n por 2 para chegar em 1. Voltando ao problema inicial, como $log_2 100 < 7$, precisaremos jogar no máximo 7 bolas para determinar a partir de qual andar a bola quebrar. Quando você jogar uma bola, se ela quebrar é a mesma coisa que o seu amigo que pensou num número dizendo “O número que eu pensei é menor.” Se ela não quebrar, é equivalente ao seu amigo dizendo “O número que eu pensei é maior.”

Realizando uma busca binária, o pior caso (aquele caso no qual quebraremos mais bolas – e que jogaremos a maior quantidade de vezes) é quando a bola quebra no primeiro andar. Você joga as bolas dos andares 50 (poft!), 25 (poft!), 13 (poft!), 7 (poft!), 4 (poft!), 2 (poft!), 1, jogando um total de 7 e quebrando um total de 6 bolas.

Nada muito novo para quem já conhecia busca binária. Por isso, vamos modificar o problema: Suponha que você não tenha quantas bolas desejar, mas apenas duas bolas. Quando uma bola cai sem quebrar, você pode descer, pegá-la e jogá-la de novo. Qual a menor quantidade de vezes que você vai ter que jogar a bola para com certeza determinar a partir de qual andar as bolas começam a quebrar?

Fazer uma busca binária não funciona mais. No caso de a bola quebrar a partir do primeiro andar, assim que você joga uma bola do andar 50 (uma bola quebra) e outra do 25 (outra bola quebra), você não tem mais bolas e não tem ideia de qual é o andar a partir do qual as bolas começam a quebrar (tudo o que você sabe é que é algum andar entre 1 e 25).

Como usar as duas bolas para determinar exatamente o andar a partir do qual as bolas começam a quebrar jogando as bolas a menor quantidade possível de vezes? Qual é essa quantidade mínima de vezes que será necessário jogar bolas pela janela?

Obrigado ao David por ter me apresentado o problema. A solução é bem legal!

Editado para ficar mais claro: A quantidade mínima que queremos é a do pior caso, isso é, a menor quantidade de vezes que será necessário jogar a bola independente de qual for o andar. Por exemplo, suponha que eu jogue uma bola do andar 5 e não quebre. Aí eu jogue do andar 10 e não quebre. Do 15 e não quebre. E assim sucessivamente (de 5 em 5) enquanto ela não quebrar. Quando ela quebrar, eu pego a outra bola e jogo no último valor que eu joguei menos 4, menos 3, menos 2 e menos 1. O pior caso para esse algoritmo é quando a bola quebrar a partir do andar 99. Jogarei nos andares 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (poft!), 96, 97, 98, 99 (poft!), ou seja, 24 vezes. (Mas é possível usar um algoritmo mais esperto que isso: a resposta do problema é menor que 24.)

Editado para programadores: A generalização deste problema (para n andares em vez de 100 e k bolas em vez de 2) caiu na OBI 2010 (o problema se chama Altas Aventuras) e está no SPOJ para quem quiser resolver: ALTAS2. Quem me contou foi o André.

Esses dias, tomando banho de mar, me vi pensando na forma das potências de dois em base dez.

É fácil ver que não existe potência de 2 que termine em 0, já que qualquer número que termina em 0 é múltiplo de 5.

Na verdade, é fácil ver (com um raciocínio indutivo com módulo 10) que o último algarismo das potências de 2 vai seguindo a sequência (2, 4, 8, 6) infinitamente, de tal forma que o último algarismo de $2^k$ (k > 0) é:

• 6, se o resto da divisão de k por 4 for 0
• 2, se o resto da divisão de k por 4 for 1
• 4, se o resto da divisão de k por 4 for 2
• 8, se o resto da divisão de k por 4 for 3

Mas aí fiquei pensando em potências de 2 que acabassem com uma porção de doises. Algo como 3103912840123891294805398108310312222 (esse número aí não tem nada de especial, foi só eu batendo no teclado loucamente e terminando com 2222). Como eu faria pra encontrá-las? Será que existem?

Comecei pensando em coisas do tipo 222…222, isto é $2 \times 10^n + 2 \times 10^{n-1} + 2 \times 10^{n-2} + \cdots + 2 \times 10^0$.

Podemos colocar 20 em evidência, ficando com $20 \times (10^{n-1} + 10^{n-2} + \cdots + 10^0) + 2$.

A princípio isso não parece ajudar muito, mas vejam que interessante:

$20 \times x + 2 = 2(10x+1)$ (x é qualquer número inteiro > 0)

Bem… $10x+1$ certamente não é uma potência de 2 (porque termina em 1).

Logo, $2(10x+1)$ também não é uma potência de 2, independente da maluquice que a gente coloque no lugar de $x$.

Portanto, não existem potências de 2 que terminem em 22! Mais que isso: não existem potências da forma 20x+2, ou seja, não existem potências de 2 que terminem em 02, 22, 42, 62 ou 82! Não é incrível? Não é nada muito revolucionário ou complexo, mas nunca tinha parado pra pensar nisso.

Lá no início tínhamos visto que o último algarismo de $2^k$ é 2 se e somente se o resto da divisão de k por 4 for 1. Logo, concluímos (e dá pra imaginar várias outras provas simples pra esse fato, pensando bem, por exemplo notando que $12 \times 16 \equiv 12 \mod 20$) que para todo k > 0 tal que o resto da divisão de k por 4 seja 1 vale que o resto da divisão de 2^k por 20 é 12.

As primeiras potências de 2 que terminam em 2 são:

• $2^1 = 2$ (que ignorei aí em cima quando falei que x > 0 no 20x+2)
• $2^5 = 32$
• $2^9 = 512$
• $2^{13} = 8192$
• $2^{17} = 131072$
• $2^{21} = 2097152$
• $2^{25} = 33554432$

O que parece nos indicar que, da mesma forma que o último algarismo das potências de 2 seguem a sequência (2, 4, 8, 6), o penúltimo algarismo das potências de 2 que acabam em 2 seguem a sequência (9, 7, 5, 3, 1). Isso é fácil de ver: basta fazer umas multiplicações por 16 dentro do módulo 100.

Este post possui intencionalmente apenas imagens e códigos.

Código-fonte (com alguns bugs inofensivos — procure XXX)

/* pascal -- generate colored Pascal's triangles in XPM format

   Copyright (C) 2011 Tiago Madeira <madeira@ime.usp.br>

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You can read a copy of the GNU General Public License at
   http://www.gnu.org/licenses/gpl-3.0.txt */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <getopt.h>
#include <math.h>

#define DEFMOD 2
#define DEFSIZE 300
#define DEFPADDING 8

int mod = DEFMOD;
int size = DEFSIZE;
int padding = DEFPADDING;

char makecolors[6][4] = {
	"001", "010", "100", "110", "101", "001"
};

struct option longopts[] = {
	{"help", 0, 0, 'h'},
	{"padding", 1, 0, 'p'},
	{"size", 1, 0, 's'},
	{"mod", 1, 0, 'm'},
	{0, 0, 0, 0}
};

char *program_name;

void try_help() {
	fprintf(stderr, "Try `%s --help' for more information.\n", program_name);
}

void help() {
	printf("Usage: %s [OPTION]... [FILE]\n", program_name);
	printf("Generate colored Pascal's triangles (XPM format).\n\n");
	printf("Mandatory arguments to long options are mandatory for short options too.\n\n");
	printf("  -h, --help        print this help\n");
	printf("  -m, --mod=M       paint with different colors numbers mod M\n");
	printf("  -p, --padding=SZ  image padding (margin) in pixels\n\n");
	printf("  -s, --size=SZ     generate SZ lines of Pascal's triangle\n\n");
	printf("With no FILE, or when FILE is -, write to standard output.\n\n");
	printf("Report bugs to <madeira@ime.usp.br>.\n");
}

int baselog(int n, int base) {
	return ceil(log(n) / log(base));
}

void *xmalloc(size_t size) {
	void *x = malloc(size);
	if (x == NULL) {
		fprintf(stderr, "There is no enough memory to allocate.\n");
		exit(3);
	}
	return x;
}

int main(int argc, char **argv) {
	int optc, tofile;
	int i, j;
	int width, height, chars;
	char **color, rgb[7];
	int one, pos;
	int *pascal;
	char *line;

	program_name = argv[0];
	while ((optc = getopt_long(argc, argv, "hm:p:s:", longopts, (int *)0)) != -1) {
		switch (optc) {
		case 'h':
			help();
			return 0;
		case 'm':
			mod = atoi(optarg);
			if (mod > 48) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 48 (color generation limit).\n");
				return 4;
			}
			if (mod > 26) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 26 (bad implementation limit).\n");
				return 5;
			}
			break;
		case 'p':
			padding = atoi(optarg);
			break;
		case 's':
			size = atoi(optarg);
			break;
		default:
			try_help();
			return 1;
		}
	}
	if (optind < argc && strcmp("-", argv[optind])) {
		if (freopen(argv[optind], "w", stdout) == NULL) {
			fprintf(stderr, "Can't open `%s' for writing.\n", argv[optind]);
			return 2;
		}
		tofile = 1;
	} else {
		tofile = 0;
	}

	printf("static char *a_xpm[] = {\n");
	width = size * 2 + padding * 2;
	height = size * 2 + padding * 2;
	chars = baselog(mod, 26);
	printf(""%d %d %d %d",\n", width, height, mod + 1, chars);
	color = xmalloc(sizeof(color[0]) * (mod+1));
	rgb[6] = '�';

	printf("\"");
	color[mod] = xmalloc(sizeof(color[mod][0]) * (chars + 1));
	for (j = 0; j < chars; j++) {
		color[mod][j] = ' ';
	}
	color[mod][chars] = '�';
	printf("%s c #000000\",\n", color[mod]);

	for (i = 0; i < mod; i++) {
		color[i] = xmalloc(sizeof(color[i][0]) * (chars + 1));
		if (i == 0) {
			for (j = 0; j < chars; j++) {
				color[i][j] = 'a';
			}
			color[i][chars] = '�';
		} else {
			strcpy(color[i], color[i-1]);
			for (j = chars-1; j >= 0; j--) {
				if (color[i][j] == 'z') {
					color[i][j] = 'a';
				} else {
					color[i][j]++;
					break;
				}
			}
		}
		one = 255 / pow(2, i / 6);
		sprintf(rgb, "%02x%02x%02x", makecolors[i%6][0] == '1' ? one : 0,
				makecolors[i%6][1] == '1' ? one : 0, makecolors[i%6][2] == '1' ? one : 0);
		printf("\"%s c #%s\",\n", color[i], rgb);
	}

	line = xmalloc(sizeof(line[0]) * (width+1));
	pascal = xmalloc(sizeof(pascal[0]) * size);

	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\",\n", line);
	}

	memset(pascal, 0, sizeof(pascal[0]) * size);
	pascal[0] = 1;

	for (i = 0; i < size; i++) {
		for (j = i; j >= 0; j--) {
			if (j != 0) {
				pascal[j] = (pascal[j-1] + pascal[j]) % mod;
			}
			pos = padding + 2*j + (size - 1 - i);
			/* XXX a implementacao de line ficou toda errada e so estou pegando
			 * o primeiro caractere de color aqui. precisa ser reescrito. */
			line[pos] = line[pos+1] = *color[pascal[j]];
		}
		printf("\"%s\",\n\"%s\"%s\n", line, line, i == size-1 && !padding ? "" : ",");
	}

	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\"%s\n", line, i == padding-1 ? "" : ",");
	}
	printf("};\n");

	if (tofile) {
		fclose(stdout);
	}
	return 0;
}

(Download – 5kb)