Treino de 05 de junho de 2015

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Este é o segundo treino no novo formato. Esperamos que gostem. Abaixo, seguem os links para os problemas desse treino e uma descrição de uma solução possível para cada um deles.

Conteúdo

Problemas

Nível Problema
1 Zero or one
2 Sticker Collector Robot
3 Mesa da sra Montagny!
4 Find Maximum
5 Counting Ones

Soluções

Zero or one

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este problema é bem direto: basta fazer o que se pede. Uma forma bem compacta de se implementar este problema em C ou C++ é a seguinte. Sejam $A$, $B$ e $C$ os três inteiros dados na entrada, cada um podendo ser ou $0$ ou $1$. A resposta então é '*' se $(A + B + C) \% 3 == 0$, e caso contrário será $'A' + (A == C) + 2*(A == B)$.

Consegue ver por que isso funciona? Se não, faça alguns casos manualmente, lembrando que expressões booleanas em C e C++ são equivalentes aos inteiros $0$ ou $1$ em expressões aritméticas e outros contextos.

Sticker Collector Robot

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este problema também é direto: basta seguir as instruções dadas no enunciado. Porém, a implementação será um pouco mais trabalhosa que a do último problema. Uma técnica que simplifica bastante a implementação deste problema foi explicada no editorial passado, no contexto do problema 2048.

Mesa da sra Montagny!

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
O problema se reduz ao seguinte: dado um grafo não direcionado sem pesos, verificar se ele é um grafo bipartido. Isto pode ser feito com uma busca em largura. Suponha que façamos uma busca em largura a partir de um vértice qualquer $v$, e para cada vértice $u$ salvamos a distância $d(u, v)$ (número de arestas no menor caminho entre $u$ e $v$. É fácil ver que, se o grafo for bipartido, todos os vértices a uma distância par de $v$ (0, que é o próprio $v$, 2, os vizinhos dos vizinhos de $v$, e assim por diante) necessariamente estão na mesma partição que $v$, e os vértices a uma distância ímpar deverão estar na partição oposta. Sabendo a única possibilidade de duas partições, basta então verificar se existem arestas entre vértices que deveriam estar na mesma partição. Ou seja, para cada aresta ($u$, $w$), verifique se a paridade de $d(v, u)$ e $d(v, w)$ é diferente. Se isto for verdade para toda aresta, o grafo é bipartido. Caso contrário, não é. A Wikipedia explica com mais detalhes um outro algoritmo baseado em busca em profundidade.

É bastante útil familiarizar-se com os conceitos básicos de Teoria dos Grafos, tais como grafos bipartidos, busca em largura e busca em profundidade. Eles são extremamente recorrentes na Maratona e em Ciência da Computação em geral. Como referência, recomenda-se o livro Introduction to Algorithms.

Find Maximum

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este problema requer uma observação que se aplica em várias situações. Ela é a seguinte: seja $x$ um inteiro positivo. Seja $y$ outro inteiro positivo tal que $0 \leq y \lt x$. Digamos que $x$ tem representação binária $a_na_{n-1}\cdots a_1a_0$, de forma que $x = \sum_i^n a_i \times 2^i$, com $a_i \in \{0, 1\}$. Digamos também que $y$ tem representação binária $b_nb_{n-1}\cdots b_1b_0$, onde $y = \sum_i^n a_i \times 2^i$ e com $b_i \in \{0, 1\}$. Então, existe um $k$ tal que a sequência $b_n b_{n-1} \cdots b_1b_0$ tem a seguinte forma: $a_na_{n-1}\cdots a_{k+1}0 \cdots$, onde $a_{k} = 1$. Ou seja, até antes de um determinado bit $k$, a representação binária de $y$ é idêntica à de $x$, até que, no k-ésimo bit, $x$ tem um $1$ em sua representação binária e $y$ tem um zero. A implicação corre das duas formas: se existe tal $k$, então $x \gt y$.

Vejamos um exemplo. Se $x = 1930$ e $y = 1699$, $x$ e $y$ têm as seguintes representações binárias:

$$x = 11110001010_2$$ $$y = 11010100011_2$$

Neste caso, eles diferem no terceiro bit mais significativo, onde $x$ tem um 1 e $y$ tem um zero.

A prova de que isto é válido é simples. Vamos mostrar um lado da prova, mas o outro é bastante semelhante. Assumimos que $x > y$. Logo, eles têm representações binárias diferentes. Seja $i$ o índice do bit mais significativo em que $x$ e $y$ diferem. Só temos duas possibilidades: ou $x_i = 1$ e $y_i = 0$, ou $x_i = 0$ e $y_i = 1$. Não é difícil ver que esta última possibilidade viola a hipótese de que $x > y$. Dissemos que $x$ e $y$ têm representações binárias que começam com $x_nx_{n-1}\cdots x_{i+1}$ e que, no bit $i$, $x$ tem um $0$ e $y$ tem um $1$. Agora, o maior valor que $x$ poderia ter é com todos os próximos bits menos significativos sendo $1$, certo? E o menor valor que $y$ poderia ter é com todos os bits menos significativos sendo $0$. Ainda nesse caso extremo, teríamos $y = x+1$, o que é absurdo. Logo, no bit mais significativo em que $x$ e $y$ diferem em suas representações binárias, $x$ tem um $1$ e $y$ tem um $0$, necessariamente.

Como isto nos ajuda a resolver o problema? Da seguinte forma: queremos um $x$ tal que $x \leq m$ e que maximize $f(x)$. Você pode calcular $f(m)$ facilmente, certo? Agora considere que $x \lt m$. Neste caso, sabemos que na posição mais significativa em que $x$ e $m$ diferem, $m$ possui um $1$ e $x$ possui um $0$. Podemos testar então todos os bits em que $x$ e $m$ podem diferir pela primeira vez (são $n$ bits). Isto só pode acontecer no $i$-ésimo bit se o $i$-ésimo bit de $m$ for $1$. Para todo bit $1$ de $m$, vamos considerar os $x$ que diferem pela primeira vez de $m$ neste bit. Sabemos que os bits mais significativos de $x$ e $m$ são iguais, que o $i$-ésimo bit de $x$ é zero, mas não sabemos os demais bits. Porém, dentre todos os $x$ que podemos escolher que têm esse formato, qual é o que maximiza $f(x)$? Como todos os valores de $a$ são não-negativos, o ideal seria pegarmos todos os que restaram, certo? E podemos fazer isto, porque a observação que demonstramos garante que, dado que não pegamos o $i$-ésimo elemento, $x$ será menos que $m$ independente do valor dos bits menos significativos que $i$. Logo, podemos colocar todos esses bits em $1$.

Para calcular $f(x)$ do melhor $x$ que difere de $m$ no $i$-ésimo bit eficientemente, precisamos apenas da soma de todos os elementos $a_j$ com $j < i$. Isto pode ser pré-computado em $O(n)$: são as somas dos prefixos de $a$. Além disso, para cada $i$, precisamos saber a soma dos valores de $a_j$ tal que $j > i$ e o bit $j$ de $m$ é $1$ para todo $i$. Isto também pode ser pré-computado em $O(n)$ de forma bem similar. Tendo isso, para cada bit $i$, conseguimos calcular o valor de $f(x)$ do melhor $x$ que difere de $m$ pela primeira vez no bit $i$ em $O(1)$. Assim, a complexidade do nosso algoritmo é $O(n)$.

Counting Ones

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
G. Polya dizia: "Se você não consegue resolver um problema, existe um problema relacionado mais fácil que você consegue resolver. Resolva-o". É claro que nem sempre é fácil achar esse outro problema mais fácil e relacionado. Nesse caso, vejamos o que podemos simplificar. Ao invés de contar o número de uns na representação binária de todos os números entre $A$ e $B$, vamos tentar contar o número de uns na representação binária de todos os números entre $0$ e $X$, dado um $X$, que chamaremos de $f(X)$. Se soubermos fazer isto eficientemente, sabemos resolver o problema original, certo? A resposta será $f(B) - f(A-1)$.

Ainda não parece um problema muito simples. Simplifiquemos novamente, então. Ao invés de darmos apenas um inteiro $X$, vamos considerar também apenas um bit específico $i$ e perguntar quantos inteiros entre $0$ e $X$ têm esse bit $i$ com o valor $1$. Provavelmente ainda não é óbvio, mas vamos olhar alguns casos pequenos (outra técnica comum para resolver problemas). Vejamos a representação binária dos números entre 0 e 15:

$$ 00 = 0000_2 $$ $$ 01 = 0001_2 $$ $$ 02 = 0010_2 $$ $$ 03 = 0011_2 $$ $$ 04 = 0100_2 $$ $$ 05 = 0101_2 $$ $$ 06 = 0110_2 $$ $$ 07 = 0111_2 $$ $$ 08 = 1000_2 $$ $$ 09 = 1001_2 $$ $$ 10 = 1010_2 $$ $$ 11 = 1011_2 $$ $$ 12 = 1100_2 $$ $$ 13 = 1101_2 $$ $$ 14 = 1110_2 $$

Podemos perceber que o bit menos significativo alterna sempre que passamos de um número para o próximo. Ou seja, ele está ativo em metade dos números até $X$, arredondando para cima. Para este bit, a resposta é fácil, certo? E para o segundo? Este alterna de dois em dois números. O terceiro alterna de 4 em 4. Em geral, o $i$-ésimo bit alterna a cada $2^i$ números, e mantém seu valor por exatamente $2^i$ números.

A resposta sai facilmente se considerarmos os ciclos de cada bit. Como vimos, este ciclo tem tamanho $2^{i+1}$ para o i-ésimo bit: ele fica $2^i$ números em $0$, depois outros $2^i$ números em $1$, depois isto se repete. Agora, para um determinado $X$, podemos contar quantos ciclos completos do bit $i$ acontecem até $X$ facilmente: $C_i(X) = X / (2^{i+1})$ (divisão inteira, ou seja, arredondada para baixo). A quantidade de números com o $i$-ésimo bit com valor $1$ nesses ciclos completos será $2^i \times C_i(X)$. Fora os ciclos completos, possivelmente $X$ está no meio de um ciclo que fica incompleto. Quantos números estão neste ciclo incompleto? Não será difícil ver que são exatamente $X \mod 2^{i+1}$ (o resto da divisão entre $X$ e $2^{i+1}$). Neste ciclo incompleto, os $2^i$ primeiros números contém um $0$ no bit $i$, e os $2^i$ últimos contém um $1$. Logo, a quantidade de números com o $i$-ésimo bit com valor $1$ neste ciclo incompleto, $I_i(X)$, será $0$ se $(X \mod 2^{i+1}) \lt 2^i$, e $(X \mod 2^{i+1}) - 2^i + 1$ caso contrário. Ou seja, $I(X) = \max \{0, (X \mod 2^{i+1}) - 2^i + 1\}$.

Sabemos calcular $C_i(X)$ e $I_i(x)$ em $O(1)$. Com isto, sabemos calcular $f(x)$ em $O(\lg x)$, pois precisamos apenas de realizar $O(1)$ operações para cada bit de $X$. Sabendo computar $f(x)$ eficientemente, sabemos resolver o problema: basta imprimir $f(B) - f(A-1)$.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas