Treino de 17 de julho 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 Pasha and Tea
2 Case of Matryoshkas
3 Preparing Olympiad
4 Awari 2
5 Design Labyrinths
6 Spider's Web

Soluções

Pasha and Tea

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

Uma possível solução para esse problema é, primeiramente, ordenar as $2N$ xícaras. Como vamos servir exatamente $x$ para $N$ meninas, minimizamos o desperdício (maximizamos a utilização) da água, se usarmos as $N$ menores xícaras para as meninas. A xícara $N+1$, que será a menor atribuída aos meninos, tem de ser capaz de suportar $2x$ de água. Ou seja, o volume $x$ será o mínimo entre o volume da menor xícara e a metade do volume da xícara ($N+1$)-ésima xícara, ou $x = \text{min}(V_1, V_{N+1} / 2)$. Por fim, temos de retornar $\text{min}(w, 3nx)$. A complexidade da solução é $O(n \log n)$, justamente o custo de ordenarmos o vetor.

Case of Matryoshkas

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

A solução do problema depende de duas observações: 1) a única cadeia que podemos manter é aquela da forma $C(1, L) = 1 \rightarrow 2 \rightarrow \cdots \rightarrow L-1 \rightarrow L$ e 2) para todas as outras, temos de desfaze-las completamente. Tendo isso em mente, temos que, para cada uma das $K$ cadeias, iremos separar todas as matryoshkas, exceto aquelas em $C(1,L)$, com custo total $D = \sum_{i=1}^K (|i| - 1) - L + 1 = N - K - L + 1$. O custo de reconstrução é simplesmente $R = N - L$, pois temos de colocar cada uma das $N-L$ cadeias uma dentro da outra, e esse custo é de $1$ para cada matryoshka. Logo, o resultado desejado é $D + R = 2(N-L) - K + 1$. A complexidade da solução é $O(L)$, que é o tempo necessário para descobrirmos $L$, que no pior caso é $N$, logo $O(N)$.

Preparing Olympiad

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

Os limites desse problema dão uma ótima ideia de como resolve-lo. O número de problemas é muito pequeno, apenas 15, o que nos permite usar força bruta para chegarmos à solução. Da análise combinatória, temos que o número de subconjuntos não vazios de problemas é $P = 2^{15} - 1 = 32767$. Primeiro, geramos todos os $P$ subconjuntos e, para cada um desses, testamos se sua soma $S_i$ atende aos limites ($l \leq S_i \leq r$), e se $max(S_i) - min(S_i) \geq x$. A resposta do problema é, então, o número de subconjuntos que atendem às restrições. A complexidade de nossa solução é $O(N^22^N)$, mas como $N$ é pequeno, isto é suficiente.

Awari 2

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

Podemos resolver esse problema de forma gulosa após fazermos a seguinte observação: uma caixa só pode ser completamente esvaziada se todas aquelas com índice maior que ela atribuírem um número de bolas a ela que seja divisível por seu índice. Isto é, só podemos esvaziar a caixa $i$ se $|C_i| \leq i$ (caso contrário o jogo já se inicia de forma insolúvel) e se $ (|C_i| + G_i) \bmod i \equiv 0$, onde $G_i$ é o número de esferas fornecidas a $i$ por seus sucessores.

Sabendo disso, podemos construir a seguinte solução gulosa: para cada caixa $i$ de $N$ até $1$, se a quantidade de esferas naturalmente presente nela mais o ganho fornecido pelos seus sucessores for congruente com $0 \bmod i$, fazemos $G_i = G_{i+1} + \frac{T_{i+1}}{i+1}$. Se em algum momento a congruência for quebrada, temos que o jogo é impossível de ser ganho. Caso contrário, ele pode ser vencido. A complexidade da solução é, por fim, $O(N)$, já que passamos uma quantidade constante de vezes por cada caixa da entrada.

A otimalidade dessa solução é mais facilmente entendida quando vemos a estratégia ótima geral do problema. Suponha que tivéssemos de preencher, para cada retirada que realizarmos, todas as caixas anteriores a ela. Obviamente, teríamos de caminhar, de $1$ até $i$, retirando dessas caixas quando fosse possível e, recursivamente, repetindo essa jogada. O que nossa solução gulosa faz é simular essa tomada de decisões de forma a não ser necessário redistribuir as esferas para toda operação realizada no jogo e recalcular a próxima jogada ótima.

Design Labyrinths

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

Vamos pensar como o custo de se desenhar o labirinto cresce à medida que o mesmo também cresce. Para cada aresta que tomarmos no grafo, invariavelmente teremos de tomar a mesma aresta (ou uma paralela, que pode simplesmente ser ignorada) para chegar a um de seus vértices e novamente para retornar à origem, já que o grafo é acíclico, garantido pela descrição do problema, e que não podemos realizar nenhum tipo de "teletransporte", simplesmente indo de um vértice a outro.

Para implementarmos a solução, podemos ignorar arestas paralelas e considerar que o "custo" de cada aresta tomada é 2 (1 para visitar um novo vértice, e mais 1 para retornar à origem). A maneira mais direta de fazer essa contagem é caminhar no grifo utilizando uma busca em profundidade e contando o número de arestas ("pushes" na pilha) que foram tomadas e multiplicar essa quantidade por 2. A complexidade de nossa solução se torna, então, $O(E + V) = O(V)$, pois temos uma árvore e $E = O(V)$ nesse caso.

Spider's Web

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

Esse é um excelente caso onde o problema quase que intencionalmente usa muitos nomes diferentes para assustar o leitor. Vamos por partes. O que está sendo feito é, essencialmente, uma divisão do plano em diversos semi-planos (setores) de mesmas dimensões. Essa divisão é feita por meio de retas (hastes) que, por sua vez, possuem uma série de pontos de conexão (attachment points). Cada ponto desses é relacionado a um outro ponto em uma haste adjacente à atual, formando uma ponte (bridge) entre elas. A combinação de 2 hastes e 2 pontos formam trapézios (células) na estrutura da rede da aranha.

Para simplificar nossa compreensão, vamos marcar cada attachment point da haste $i$ como o par $(d_{i,j}, z_{i,j})$ onde $d_{i,j}$ é a distância do ponto $j$ até o centro da teia (fornecido na entrada) e $z_{i,j}$ é a orientação do mesmo, também fornecido na entrada (mas implicitamente). A orientação $z$ pode assumir dois valores: $r$, se $p_{i,j}$ se conecta à haste $i+1$, ou $l$, se ele se conecta à haste $i-1$. De certa forma, essa modelagem nos permite saber se um determinado por pertence ou não ao setor atual.

Para representarmos uma haste, vamos simplesmente construir uma pilha (previamente ordenada por $d_{i,j}$), representada por um vetor para simplificar operação de ordenação. Os pontos são inserido na mesma em 2 momentos, uma vez que ela faz parte de 2 setores distintos. Em cada um dessas ela atuará hora como $i+1$ (inserimos pontos com $z_{i,j} = l$) e hora como $i$ ($z_{i,j} = r$). Após terminadas todas as inserções, ordenamos.

Por fim, podemos representar um setor como um par de hastes $(i, i+1)$. Agora a tarefa de contar quantos trapézios possuem números diferentes de attachment points em cada lado se torna simples: entre dois pontos com $z_{i,j} = r$ em $i$ temos o trapézio correspondente aos dois ponto com $z_{i+1,j} = l$. Note que, nesse caso, $d_{i,j} = d_{i+1,j}$. A contagem de attachment points que pertencem a outro setor se torna, simplesmente, o número de vezes que temos de remover o topo da pilha para chegarmos ao próximo elemento desejado. Se o número for diferente para cada haste (lado do trapézio), temos um célula instável e aumentamos nosso contador em 1 unidade.

A complexidade dessa idéia é $O(2P + \sum P_i \log P_i) = O(P \log P)$, o custo de contar os trapézios instáveis (já que cada ponto é visto duas vezes) e ordenar os pontos em cada haste. Como o número de pontos é, no máximo, $10^5$, temos que nossa solução é suficiente.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas