Treino de 03 de julho de 2015

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

Este é o sexto 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. Recomenda-se não olhar os problemas antes do dia do treino (embora ninguém vá te impedir). Até lá, você pode ir treinando com outros problemas do Codeforces e de regionais passadas.

Conteúdo

Problemas

Nível Problema
1 Friends
2 Concurso de Contos
3 Foco
4 Radares
5 Vanya and Scales

Soluções

Friends

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Como as restrições são bem pequenas (somente 5 amigos), você pode testar todas as possibilidades. Para cada tripla de alunos, verifique se ou os três são amigos, ou se os três são desconhecidos entre si. Se isto acontecer para alguma tripla, a resposta é "WIN", caso contrário é "FAIL". Você pode salvar as amizades em uma matriz, de forma que $m[i][j] = 1$ se $i$ e $j$ são amigos, e 0 caso contrário. Isto facilitará a implementação.

Concurso de Contos

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Este problema é direto, mas pede cuidados na implementação. A observação que deve ser feita é de que não faz sentido colocar uma palavra na linha $i+1$ se ela cabe na linha $i$, como também não faz sentido usar colocar uma linha na página $p+1$ se a página $p$ ainda não está cheia. Porém, deve-se considerar os espaços, que podem impedir com que a palavra caiba na linha anterior. Apenas tome cuidado com esses casos.

Foco

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Primeiramente, vamos entender o problema, já que o enunciado pode deixar dúvidas. O foco é um parâmetro numérico da câmera no momento da foto. Ou seja, podemos tirar uma foto com foco $3$, $5.5$ ou $9$. Cada objeto possui um intervalo de foco em que, se a foto tirada tiver o foco naquele intervalo, o objeto aparecerá focado. O problema pergunta quantas fotos é necessário tirar de forma que cada objeto esteja focado em pelo menos uma delas. Em outras palavras, sejam $[L_i, R_i]$ os intervalos de foco dos objetos, para $i$ entre $1$ e $N$: queremos saber o menor $k$ tal que exista um conjunto de focos $F = \{f_1, \cdots, f_k\}$ de forma que cada intervalo $[L_i, R_i]$ contenha pelo menos um elemento de $F$.

Algo que auxilia em vários problemas é observar casos extremos e ver se encontramos alguma propriedade especial neles. Depois de um tempo, podemos nos perguntar o que há de especial no objeto cujo intervalo de foco tem o menor final $R_{min}$. Sabemos que, na solução ótima, necessariamente existe pelo menos uma foto com foco $f$ com $f \leq R_{min}$. Mas pense um pouco: se esta foto for tirada exatamente com foco $R_{min}$, ela continuará cobrindo todos os objetos que cobria (afinal, aumentando o foco até $R_{min}$ não iremos sair do intervalo de foco de nenhum objeto, porque assumimos que $R_{min}$ é o menor final de intervalo de foco). Ou seja, sempre existe uma solução ótima em que uma foto com foco $R_{min}$. Tirada esta foto, todos os objetos cujo intervalo de foco contém o ponto $R_{min}$ podem ser descartados, já que eles já foram focados em uma foto e não vão alterar mais a solução. Resta saber de quantas fotos precisamos para focar os demais objetos. Esta é uma versão menor do mesmo problema: podemos aplicar nossa ideia novamente até que caiamos no caso trivial: para focalizar 0 objetos, precisamos de 0 fotos.

É possível implementar nossa solução em tempo $O(n \lg n)$. Primeiramente, ordenamos os intervalos pelo tempo de final (em C++, você pode ver aqui alguns exemplos de como fazer isto usando a biblioteca padrão. Leia as respostas que não usam boost). Depois, iteraremos do primeiro ao último intervalos, mantendo dois inteiros: um $f$ que guarda o número de fotos já tiradas e outro $l$ que indica o foco da última foto tirada. Inicialmente, $f = 0$ e $l = -1$ (indicando que ainda não tiramos qualquer foto). Repetimos o seguinte: primeiro, incrementamos $f$ e tiramos uma foto no final do intervalo de foco da próxima foto (fazendo $l = R_i$). Depois, pulamos todos os intervalos cujo intervalo de foco contenha $l$. No final, a resposta será $f$.

A corretude desta ideia depende de uma outra observação. Quando tiramos uma foto, não necessariamente estamos removendo todos os objetos que são focados naquela foto. Se tiramos uma foto com foco $f$, pode haver um objeto $O_1$ com intervalo $[L_1, R_1]$ com $L_1 > f$ que não será coberto, mas outro objeto $O_2$ com intervalo de foco $[L_2, R_2]$ que é coberto, porém $R_2 > R_1$ (e como $f \in [L_2, R_2]$ e $f < L_1$, concluímos que o intervalo de $O_2$ contém o intervalo de $O_1$) e assim este segundo intervalo não será pulado, porque no máximo pararemos de desconsiderar intervalos quando chegarmos em $O_1$. Porém, neste caso, teremos de tirar alguma outra foto para focalizar o objeto $O_1$. E como o intervalo de $O_2$ contém o de $O_1$, essa foto também focaliza $O_2$. Novamente, é possível que $O_2$ não seja alcançado nos 'pulos' feitos nessa outra foto. Mas isto só poderá acontecer um número finito de vezes, e na última foto tirada com foco $f \leq R_2$ iremos pular o objeto $O_2$. Este argumento garante a otimalidade desta solução, que é um algoritmo guloso.

Radares

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

O que acontece quando colocamos um radar na posição $p$? Ganhamos um certo lucro $l_i$ e Isto nos impede de colocar um radar no intervalo $[p-k, p+k]$. Novamente, como no problema anterior, vamos analisar um caso extremo: o que acontece com o primeiro radar que colocarmos? Como ele é o primeiro, não haverá outro radar no intervalo $[p-k, p]$: logo, nossa única restrição é a de que os demais radares devem ser colocados em posições posteriores a $p_k$. Fora isto, se desconsiderarmos todos os radares nessas posições proibidas, ficamos com uma versão menor do mesmo problema. Isto nos leva a pensar em Programação Dinâmica.

Basicamente, vamos considerar que $l_i$ é o lucro que obtemos se colocarmos um radar na posição $i$ (consideramos $l_i = 0$ se não existe um radar que possa ser colocado na posição $i$). Seja $f(i)$ o maior lucro que podemos obter se só podemos colocar radares a partir da posição $i$ (ou seja, a posição $i$ é permitida). Então, não é difícil ver que:

$$f(K+1) = 0$$ $$f(i) = \max \{f(i+1), l_i + f(i+k+1),\enspace se\ i \leq K$$

A resposta para nosso problema é $f(0)$. Podemos tabelar os valores de $f$, e computá-los do maior $i$ até $i = 0$, que será a resposta desejada ($f(0)$). Obtemos, assim, uma solução $O(K)$, e como $K \leq 10^6$ isto é perfeitamente suficiente.

É possível também resolver este problema em $O(n \lg n)$ usando busca binária. Esta solução seria preferível se $K$ pudesse ser muito grande, pois o desempenho dela não depende das posições dos radares, mas apenas no número de radares.

Vanya and Scales

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Às vezes, uma estratégia efetiva de solução de problemas é eliminar alguns casos que conseguimos resolver até que os casos que sobrem tenham alguma propriedade que facilite nosso trabalho. É possível que, no final, cheguemos em uma solução genérica que não depende da remoção dos casos especiais que encontramos; ou em uma solução realmente particular. Também é possível que não cheguemos a solução alguma, caso em que devemos mudar de estratégia. Mas se isto está sendo dito neste editorial, é porque provavelmente isto ajudará em nossa solução, certo?

Primeiramente, vamos desconsiderar o caso $w = 2$. Neste caso, o problema se reduz a: é possível representar $n$ em binário? E a resposta é sempre sim para qualquer inteiro $n$. Assumindo então que $w > 2$, vamos continuar.

Olhando para o problema como ele é, pode ser que não nos venham muitas ideias. Vamos tentar formulá-lo de outra forma. Pode ser que encontremos uma formulação favorável.

Pensar que o problema está relacionado a potências de $w$ pode nos fazer querer trabalhar em base $w$. Vejamos o que ganhamos com isto. Vamos representar $n$ em base $w$ (se tiver dúvida, pode consultar esta página da Wikipedia sobre como fazer isto). Queremos saber se existem dois inteiros $m$ e $k$ de forma que:


  1. $n + m = k$
  2. $m$ e $k$ só tenham dígitos $1$ e $0$ na suas representações em base $w$, e
  3. $m$ e $k$ em base $w$ não tenham um dígito $1$ na mesma posição.


Cada dígito $1$ em base $w$ representa um dos pesos que o enunciado menciona (um dígito $1$ na posição $i$ representa o peso $w^i$).

Primeiro, podemos notar que a terceira restrição é inútil. Se encontramos uma solução em que $m$ e $k$ tenham um dígito $1$ na mesma posição, podemos simplesmente tirar este dígito de ambos e as demais restrições continuam válidas. Na prática, isto significará tirar o mesmo peso dos dois lados da balança: é óbvio que ela continuará equilibrada. Ou seja, se a resposta for "sim" sem a terceira restrição, também será "sim" com ela.

Agora, vamos tentar construir os números $m$ e $k$ do dígito menos significativo para o mais significativo em base $w$. Se o $i$-ésimo dígito de $n$ em base $w$ for $0$, podemos deixar o dígito correspondente de $m$ e de $k$ com zero também. Se o dígito for $1$, podemos colocar o $i$-ésimo dígito de $k$ como $1$, de forma que a soma do $1$ de $n$ com o $0$ de $m$ resulte no $1$ de $k$. Se não for $1$, a única possibilidade para que ainda seja possível é ele ser exatamente $w-1$, porque assim conseguimos somar $1$ de forma que a adição gere um "carry" e o dígito resultante de $k$ seja $0$. Isto porque se houver um dígito que não seja $0$, $1$ ou $w-1$, é fácil ver que é impossível preencher $m$ e $k$ com uns e zeros de forma a satisfazer $n + m = k$ (já que esse dígito na soma de $n$ e $m$ não será nem $0$ nem $1$, e $k$ só pode ter zeros e uns). Neste último caso, em que o carry foi gerado, devemos considerar isto no dígito seguinte de $n$. Novamente, pode ser que este dígito gere um novo "carry" (ele pode ser $w-1$, por exemplo), caso em que, ainda que coloquemos um dígito $0$ em $m$, o dígito correspondente em $k$ também será $0$.

Se chegarmos até o final dos dígitos de $n$ e não tivermos encontrado um dígito impossível, mostramos como teríamos construído a resposta (os números $m$ e $k$), ou seja, a resposta é que sim, é possível pesar o objeto. Caso contrário, a resposta será não.

Para implementar esta solução, podemos manter uma flag que indica se há carry do último dígito ou não (neste caso especial, o carry só pode ser $1$ ou $0$, ao contrário do caso geral). Calculamos o $i$-ésimo dígito de $m$ aplicando as regras que listamos acima ao resto da divisão por $w$ da soma do $i$-ésimo dígito de $n$ ao carry e calculamos o próximo carry verificando se a soma anterior resultou em $w$. Se não caímos no caso em que não podemos encontrar o dígito correspondente de $m$ porque a soma do $i$-ésimo dígito de $n$ ao carry resultou em um número que não é nem $0$, nem $1$ e nem $w-1$ (módulo $w$), encontramos, ao final, uma solução.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas