Contest Delta – Editorial

Olá, hoje ocorreu o segundo contest aberto do URI, o Contest Delta, onde eu escrevi 5 dos 13 problemas disponíveis na competição. Agradeço ao Ricardo Oliveira por revisar meus problemas. Os outros problemas foram escritos pelo Neilor Tonin, Lucas Negri, Márcio Oshiro e Gabriel Dalalio.

Parabéns aos ganhadores da competição:
1⁰ lugar: Fernando Fonseca
2⁰ lugar: Igor Wolff
3⁰ lugar: Márcio Barbosa

Os ganhadores levaram pra casa esta camiseta:
http://34.210.26.18/wp-content/uploads/2014/03/camiseta.png
Bacana, não?

Este editorial conta com 9 dos 13 exercícios do contest. Os outros 4 exercícios serão adicionados em breve em um post separado.

Clique no link abaixo para ver o editorial.

O Culpado[link]
Este exercício é bem simples: um aluno sempre entrega outro, ou entrega a si mesmo. Para descobrir quem acabará se entregando, basta seguir as dicas dadas começando do aluno K, até que um determinado aluno entregue a si mesmo.

Pseudocódigo:

enquanto n[k] != k
      k = n[k];
imprima k;

Estacionamento Linear[link]
O funcionamento deste estacionamento não vos lembram alguma estrutura de dado em particular? Que tal pilha? Só é possível estacionar o carro no final da pilha, e só é possível remover o carro que está no final da pilha.

Para resolver o exercício, basta então simular a ordem em que os carros entram e saem do estacionamento, verificando se as limitações da pilha sempre são respeitadas.

Uma solução seria preencher um vetor chegada com o indice i do carro que chega no tempo t , ou seja, chegada[t] = i. De forma semelhante, preencher um vetor saida. Se nenhum carro chega e/ou sai no tempo t, chegada[t] = saida[t] = 0.
O pseudocódigo ficaria então assim:

para i de 1 até maior_t
      se saida[i] != 0
            se !pilha.vazia E pilha.topo = saida[i]
                  pilha.pop;
            senao
                  imprima "Nao";
                  encerra laço;
      se chegada[i] != 0
            se pilha.tamanho < k
                  pilha.push(chegada[i]);
            senao
                  imprima "Nao";
                  encerra laço;

Gruntz[link]
Há duas maneiras de se encarar este problema, e mais duas maneiras de implementar.

  • Uma delas é posicionar o personagem em todas as bordas existentes e verificar se ele consegue chegar até o centro.
  • A outra é posicionar o personagem no centro, e verificar se ele consegue chegar até alguma das bordas (ele andará no sentido contrário das setas).

Uma vez escolhida uma das duas maneiras, há duas formas de se implementar:
– Utilizando uma busca em profundidade com backtracking, ou seja, andando nas direções que as setas apontam, ou andando na direção contrária e gastando um valor de K. Se K já for igual a 0, só é possível andar nas direções pré-definidas. Se você alcançar o centro (ou a borda, dependendo da sua escolha anterior), então a resposta é “Sim”.
Trecho de código: https://github.com/crbonilha/codes/blob/master/contest_delta/gruntz.cpp

– É possível montar um grafo onde as arestas podem conter peso 0 (quando seguem o fluxo das setas) ou peso 1 (quando seguem o fluxo contrário da seta). Com este grafo, basta encontrar o caminho mínimo entre a borda e o centro (ou vice-versa), e verificar se este caminho mínimo tem custo <= K. Para tal, a implementação do algoritmo de Dijkstra é suficiente.
Trecho de código: [em breve]

Guildas[link]
Este exercício requer uma implementação eficiente para:

  • Descobrir a qual Set pertence um jogador A.
  • Unir dois Sets.
  • Descobrir o número de pontos de cada Set.

As duas primeiras operações são operações clássicas de uma estrutura chamada Disjoint-set (Conjuntos Disjuntos). A terceira operação é facilmente adicionada uma vez que haja as duas primeiras.
Um post mais detalhado pode ser encontrado aqui:
http://marathoncode.blogspot.com.br/2013/01/conjuntos-disjuntos.html

Para descobrir se Rafael estava na guilda que ganhou a batalha, antes verifique se ele pertencia a uma das guildas que estava batalhando, e então verifique se a guilda dele venceu. Eis um pseudocódigo:

guilda_a = find(A);
guilda_b = find(B);
se guilda_a = find(1) E guilda_a.pontos > guilda_b.pontos
      contador++;
senão se guilda_b = find(1) E guilda_b.pontos > guilda_a.pontos
      contador++;

Abreviações[link]
Para resolver este exercício basta ter alguma experiência com manipulação de strings, tal como a separação de palavras, e fazer uso de uma boa estrutura para guardar todas as palavras e o número de vezes em que ela aparece no texto.

Com a estrutura Map é possível manter controle sobre todas as palavras que aparecem no texto. Após coletar todas as palavras com mais de dois caracteres, é possível jogá-las dentro de um Vector, junto com o número de aparições e o número de caracteres economizados.

Com este Vector preenchido separadamente para cada letra inicial, é possível ordená-lo de acordo com o número de caracteres economizados, e aquele que tiver o maior número de economia será impresso ao final da execução do algoritmo.

O maior desafio está na implementação, que pode ser um pouco trabalhosa, custando um bom tempo da competição. Exercícios como este são melhores aproveitados se guardados para o final da competição, quando todos os outros exercícios já foram resolvidos OU quando não se sabe resolver os outros exercícios.

EDIT: Nunca haverá casos onde a abreviação de duas palavras de mesma letra inicial resulte no mesmo total de caracteres economizados. Eu me assegurei que isso não acontecesse, mas esqueci de deixar claro no enunciado.

Parafusos e Porcas[link]
Há mais de uma maneira de se aproximar a este problema, e eu vou descrever duas.

1- Para cada intervalo dado, adicione todos os valores pertencentes a tal intervalo dentro de um vetor de inteiros. Após isso, ordene o vetor, e faça um laço encontrar a primeira e a última aparição do valor Num (uma alternativa também é usar uma busca binária aqui).
Uma sugestão de melhoria também seria implementar o Insertion Sort quando os valores estão sendo inseridos no vetor. Que tal praticar?

2- Como os valores de cada intervalo estão sempre entre 1 e 100, é possível manter um vetor count que descreva quantas vezes cada valor i aparece. Após isso, podemos saber quantos valores estão antes de Num apenas somando as posições de 1 até Num-1 em count em tempo linear, e saber se Num apareceu ou não em tempo constante, verificando se count[Num] == 0.

Jogo das Pilhas[link]
Este exercício pode ser resolvido testando todas as possibilidades permitidas de remoção de cartas, até que em uma delas a mesa esteja vazia.

Implemente uma função recursiva que tenha como caso base as três pilhas estarem vazias, e que chame a si mesma recursivamente caso contrário, indicando quais cartas foram removidas.
É possível remover cartas de 7 formas diferentes: A,  B,  C,  A e B,  A e C,  B e C,  A e B e C.

Seja 0 a posição do topo da pilha inicialmente, e N-1 a posição da última carta, a função recursiva ficaria assim:
https://github.com/crbonilha/codes/blob/master/contest_delta/jogo_das_pilhas.cpp

Una isso a uma maneira de prevenir que o mesmo estado seja consultado milhões de vezes.

Max, o Louco[link]
Trata-se de uma busca um pouco diferente do que pode-se estar acostumado. Não só é preciso encontrar um caminho entre um vértice A até um vértice B, mas você precisa comprar gasolina de modo estratégico.

Deixar para comprar gasolina apenas quando se precisa pode sair mais caro do que comprar com antecedência, ou vice-versa. Mas esse tipo de coisa é difícil de prever.

Note agora que os limites estão bem baixos. Há no máximo 10 cidades e 20 estradas. Se está difícil pensar numa estratégia de previsão, talvez testar todas as possibilidades seja a saída.

Solução: para cada cidade, experimente ir até as cidades adjacentes, comprando todas as quantias de gasolina que for possível (entre 0 e limite-tanque_atual, inclusive), e veja qual das alternativas lhe leva até o destino gastando menos dinheiro.

Eis um trecho do código para exemplo:
https://github.com/crbonilha/codes/blob/master/contest_delta/max_o_louco.cpp

Transportando Lanches[link]
O desafio aqui depende da forma como você interpreta o problema. Vou explicar um pouco a forma que eu interpretei, que seria calcular o número de viagens entre cada posição adjacente, e tentar generalizar esse valor para mais de uma posição adjacente.

Digamos que ele tem 15 lanches para serem transportados, e possa carregar 10 lanches por vez. A distância final por enquanto não importa. Seja A o ponto inicial, e B um ponto adjacente ao ponto A.
Há inicialmente 15 lanches no ponto A, e 0 no ponto B. Digamos que sejam levados 10 lanches até o ponto B. Como o transportador come um lanche a cada posição adjacente, só 9 lanches chegarão até o ponto B.
Temos agora 5 lanches no ponto A, e 9 no ponto B. Digamos que ele queira voltar ao ponto A para pegar os lanches restantes. Para isso deve levar no bolso um lanche para que possa comer, pegar os 5 lanches lá, e voltar para o ponto B, comendo mais um lanche.
Temos agora 12 lanches no ponto B, e 0 no ponto A.

Notem agora que a quantidade de lanches comidos para levar toda a encomenda entre dois pontos adjacentes não é tão difícil de prever. Para levar L lanches, será preciso quantas viagens? E a cada viagem, quantos lanches são comidos?
Dica: viagens = teto(L/C);
lanches_comidos = ?

Tudo estaria bem se pudéssemos aplicar esse cálculo D vezes, porém D pode ser um número muito alto.
O segundo passo é contar qual a distância pela qual o número de viagens é a mesma, diminuindo o número de iterações D.

EDIT:
Para ver a segunda parte do editorial, com os exercícios Fibonacci de Novo!, Contagem de Substrings, e Cordas Emaranhadas, clique no link abaixo:
http://crbonilha.com/pt/contest-delta-editorial-pt2/

Mais exercícios podem ser adicionados aqui em breve.

Alguma dúvida, sugestão, ou correção?
Me envie um e-mail, ou deixe um comentário abaixo.

Até mais 🙂

2 ideias sobre “Contest Delta – Editorial”

  1. Cristhian no problema Max, o louco a solução que você mostrou passaria no no tempo limite ? Eu implementei algo muito parecido com o que você mostrou e estou tomando TLE.
    Será que existe algum pruning que não estou vendo?

    O único detalhe que eu reparei e pode ter diminuído o meu campo de busca foi que ao montar o grafo eu só adiciono nele arestas que o peso é menor que o meu tanque. Pensei que essa seria a sacada, só que mesmo assim TLE.

    1. Consegui passar dessa maneira mesmo, a única otimização que fiz, foi salvar os subproblemas para poder reutilizar as respostas.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *