Treino de 25 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 Sudoku
2 Help Cupid
3 Biridian Forest
4 Desvio de rota
5 Help R2-D2!

Soluções

Sudoku

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Para esse problema, basta verificar se a tabela $9 \times 9$ dada na entrada é um jogo sudoku valido. Verifique se não há nenhum número repetido nas linhas, colunas e sub-tabelas.

Help cupid

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Perceba inicialmente que os fusos horários não se interceptam e que é sempre melhor agrupar números que estão no mesmo fuso. Ordene os números de forma crescente e aplique a função fornecida no problema para calcular a resposta. Vale notar que ela é o minimo entre agrupar todos dois a dois em sequencia ou unir o primeiro com o último e agrupar o resto em sequência.

Biridian Forest

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
A grande observação para resolver esse problema é que o seu personagem $p$ será atacado por algum breeder se e somente se a distancia dele ate a saída é menor ou igual que a de $p$.

Pegue qualquer caminho mínimo de ($s, d$), se um "breeder" consegue te interceptar, então ele consegue andar ate a saida e te esperar lá em um tempo menor ou igual ao de $p$. Suponha que ele não consiga chegar ate a saída antes mas que consiga batalhar com seu personagem em uma celula qualquer. Se a batalha acontece, então ele consegue andar ate $d$ em um tempo $\leq p$. Provamos por contradição que todos os "breeder" que entrarão em conflito com seu personagem chegam a saída em um tempo menor ou igual a $p$. A solução do problema se resume calcular o caminho mínimo de todos no grid e comparar.

A solução acima, apesar de estar certa pode dar TLE pela quantidade de caminhos minimos que deverão ser calculados. Para evitar isso, calcule o caminho minimo partindo da saída $d$ a todos os outros pontos do grid e ao final compare quais "breeder" tem distancia menor que $p$. O custo dessa solução é $O(r \times c)$

Desvio de rota

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Dado um grafo não direcionado $G(V, E)$, um vértice de origem $s$ e outro vértice de destino $t$, construa um grafo $G'(V, E')$ com a restrição que entre os vértices do conjunto $S = 0, 1, \ldots, C-1$ só podem existir arestas do vértice $i$ para o vértice $i+1$.

Seja o grafo $G$ dado na entrada, queremos construir um grafo $G'$ de maneira que se $A$ e $B$ pertencem a $V$, e existe um arco que liga $A$ a $B$ em $E$, existirá um arco que liga $A$ a $B$ em $E'$, se e somente se:

  • $A \notin S$.

OU,

  • $A$ e $B \in S$
  • e que $A+1 == B$ ou $A == B+1$

No grafo resultante, basta calcular o caminho mínimo do vértice de origem ao vértice de destino.

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