Treino de 18 de setembro de 2015

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

Seguimos com os treinos no novo formato. 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 Arrays
2 El Dorado
3 Puzzle
4 "OR" Game
5 Ecology
6 Help R2-D2!

Soluções

Arrays

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

Queremos saber se é possível escolher $a$ elementos de $A$ e $b$ elementos de $B$ de forma que todo elemento escolhido de $A$ seja menor que todo elemento escolhido de $B$. Isto equivale a: o maior elemento escolhido de $A$ deve ser menor que o menor elemento escolhido de $B$. É fácil ver que isso só é possível se o $a$-ésimo menor elemento de $A$ for menor que o $b$-ésimo maior elemento de $B$. Ou seja, $A[a] < B[|B| - b + 1]$, onde $|B|$ é o número de elementos em $B$.

El Dorado

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

É sempre útil verificar se conseguimos utilizar soluções para subproblemas menores para resolver o problema original. Neste caso, vamos dizer que sabemos o número de subsequências crescentes de tamanho $k-1$ que terminam em cada elemento até o penúltimo elemento. Como podemos então saber quantas subsequências crescentes de tamanho $k$ terminam no último elemento? É simples: basta contar, para cada elemento anterior que seja menor que o último elemento, o número de subsequências de tamanho $k-1$ que terminam nele. O caso base é para $k = 1$, em que só existe uma subsequência crescente que termina em cada elemento (a que só contém ele mesmo). Com isto, temos uma solução por Programação Dinâmica, $f(n, k)$, onde para cada $n$ precisamos verificar até $n$ soluções anteriores. Ou seja, a complexidade da solução é $O(n^2 k)$.

Puzzle

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

Há um detalhe crucial no enunciado do problema que nos permite uma solução simples: ele garante que sempre haverá pelo menos uma linha ou coluna com apenas uma variável desconhecida. Ou seja, o problema se resume agora à implementação, porque a solução fica clara a partir desta frase: basta resolver as linhas ou colunas que já podem ser resolvidas iterativamente, pois sabemos que sempre teremos uma próxima linha ou coluna resolvível até que os valores de todas as variáveis tenham sido encontrados.

Podemos implementar a solução como se sugere a seguir. Para cada linha e coluna, mantemos o conjunto de variáveis com desconhecidos que aparecem nela. Sempre haverá pelo menos uma linha ou coluna em que o tamanho deste conjunto é 1. Agora, mantemos uma estrutura (como uma fila ou pilha) que contém os números das linhas e colunas com apenas uma variável desconhecida. Iteramos até que esta estrutura esteja vazia, repetindo o seguinte: pegamos a próxima linha ou coluna, encontramos o valor da única variável que falta, e atualizamos todas as outras linhas ou colunas, removendo esta variável de seus conjuntos. Se neste processo alguma linha ou coluna que foi atualizada passa a ter um conjunto de tamanho $1$, adicionamos seu número na estrutura. Ao final, teremos resolvido o puzzle.

Se garantirmos que cada linha e coluna só é visitada uma vez, a complexidade desta solução passa então a ser $O((L + C)^2 \lg (L + C))$, pois para cada uma das $L + C$ linhas ou colunas, passamos por todas as outas $O(L + C)$ linhas e colunas atualizando-as em $O(\lg (L + C))$. Isto é suficiente.

"OR" Game

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

A observação crucial para este problema é que nunca é ótimo multiplicar dois números distintos por $x$. A prova é a seguinte: como $x \geq 2$, cada multiplicação corresponde a, no mínimo, um shift para a esquerda (multiplicação por 2) do número. Um shift para a esquerda ativa um bit mais significativo que todos os que já estavam ativados. Então, para qualquer escolha de números em que mais de um número é multiplicado, a opção de pegar o maior número do vetor de entrada e multiplicá-lo por $x$ todas as $k$ vezes será melhor, porque esta última opção sempre ativará um bit mais significativo que se diviidrmos as $k$ multiplicações entre mais de um número.

Ou seja, sabemos que temos que escolher um número, multiplicá-lo por $x$ todas as $k$ vezes e fazer o OR disso com todos os outros números. Será que este número será sempre o maior? Não necessariamente. Podemos montar um exemplo em que isto acontece. Vamos dizer que $k = 1$ e $x = 2$, e temos um vetor com os números $2$ e $3$. Neste caso, é melhor multiplicar o $2$ por $2$, resultando em $4 | 3 = 7$, do que multiplicar o $3$, o que nos daria um resultado de $6$.

Temos, então, que escolher o número. Mas podemos testar todos se fizermos as operações com cuidado. Basta pré-computarmos o OR de cada prefixo e sufixo do vetor. Agora, para cada número, podemos multiplicá-lo por $x^k$ e fazer o OR disso com o resto do vetor em termos do prefixo até o elemento anterior e do sufixo que começa no próximo elemento. Escolhemos, então, o melhor resultado.

A complexidade desta solução será, então, $O(k + n)$, pois fazemos a exponenciação $x^k$ em $O(k)$ uma vez e depois testamos cada um dos elementos em $O(1)$.

Ecology

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este é um problema que pode parecer mais complicado do que realmente é. O fato é que não existem tantas regiões contíguas assim. Há várias maneiras de ver que este número é, de fato, pequeno.

Assim, resta-nos encontrar uma forma eficiente de gerar todas as regiões, sem repetição. Depois disso, basta testarmos cada região colocada em cada lugar no grid e ver qual valor conseguimos.

Help R2-D2!

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Precisamos apenas de uma estrutura que nos permita fazer a consulta que R2-D2 fará: dado um inteiro $X$, qual é o primeiro elemento do vetor que é maior ou igual a $X$? Podemos utilizar uma árvore de segmentos para responder esta pergunta e atualizar o vetor eficientemente. Guardamos em cada nó o valor máximo do subvetor daquele nó. Para fazermos a consulta, então, fazemos o seguinte: se o máximo do filho da esquerda é maior ou igual a $X$, vamos para a esquerda. Senão, vamos para a direita. É fácil ver que isto é ótimo para este problema. Após utilizarmos um starship, atualizamos sua capacidade restante na árvore.

As garantias na entrada nos permitem processar cada container separadamente, mesmo quando eles chegam em blocos (já que o número total de containers é $10^6$ no máximo. Cada operação terá então custo $O(\lg n)$, resultando em uma solução $O(n \lg n)$.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas