sábado, 22 de fevereiro de 2014

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.

[For those who only speak English, come here:]
http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-english-version.html

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:
https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png
Bacana, não?

Agora vamos ao que interessa: eu escrevi menos da metade dos exercícios deste contest, portanto o meu editorial estará incompleto por um tempo indeterminado. Após o contest acabar, vou tentar fazer os exercícios, e então eu compartilho com vocês minha solução, mas não sei quanto tempo isso pode levar.
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!, Quantas Substrings?, e Cordas Emaranhadas, clique no link abaixo:
http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-continuacao.html


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 :)

21 comentários:

  1. Minha reclamação pública ao problema Guildas, pois apesar de ser interessante, simplesmente *não passa* se usar cin para leitura dos dados. Tomei 6 TLs por causa disso. Acho que esse tipo de coisa não deveria ser importante numa competição de algoritmos.

    Mas tirando isso, parabéns, o contest foi ótimo :)

    ResponderExcluir
    Respostas
    1. Juan, a diferença de tempo de execução entre cin e scanf pode parecer insignificante quando o volume de dados é baixo, mas com 10⁵ + 5*10⁵ inteiros a diferença se torna absurda. Alguns programadores tem isso em mente, mas não é obrigatório o conhecimento disso. Se eu aumentasse o tempo para acomodar soluções com cin, estaria dando uma folga muito grande para quem usasse scanf.

      Perdão pelo inconveniente.

      Excluir
    2. Eu passei usando cin/cout, basta usar ios_base::sync_with_stdio(false);
      Uma coisa estranha foi que eu só consegui passar a G quando mudei pro Dijkstra, levei 4 TLEs usando a primeira abordagem. Ainda não descobri o motivo.

      Excluir
    3. Estranho, nos meus testes minha DFS levou menos tempo que o Dijkstra. Se quiser me mandar seu código, posso dar uma olhada.

      Excluir
  2. Eu fiz com DFS e passou, mas sem folga: 0.224s

    https://gist.github.com/juanplopes/6131525dab1087688827

    De uma forma geral, achei os timelimits bem apertados. Quase todos os problemas tinham que estar bem azeitados, senão não passavam.

    ResponderExcluir
  3. Olá Cristhian,
    Gostei do Contest Delta de hoje. Entretanto ainda estou intrigado com o problema A - Abbreviations.
    Meu código segue a sua solução. Separar cada palavra, contar as repetidas, contar letras economizadas por palavra, depois pegar para cada letra, se existe alguma palavra iniciando com ela abreviar aquela com maior economia (desconsiderando palavras tamanho<=2 ).
    Um ponto de dúvida era como esse caso de teste:
    aaaa azzz
    Qual palavra abreviar ? Tentei pegando a menor, WA, maior, WA.
    Trato de colocar apenas espaços ENTRE as palavras (sem space no final).
    Poderia ceder casos de teste, ou verificar meu código ?
    http://pastebin.com/FykYf0ma

    Obrigado!

    ResponderExcluir
    Respostas
    1. Você editou seu código depois do contest? Pois eu testei com os casos de teste aqui e o teu algoritmo está correto.
      Não haverá casos tal como aaaa e azzz (fiz questão de remover, mas esqueci de deixar claro no enunciado).

      Excluir
    2. A única modificação que fiz foi no cálculo de letras economizadas, mas nada que deva mudar o comportamento em geral do programa.
      Estava considerando strlen(palavra)-1 como economia, mas na verdade é strlen(palavra)-2. Isso passou despercebido, mas creio que não muda nada, pois as palavras selecionadas ainda são as mesmas. Só a quantidade economizada muda, mas isto afeta todas as contas.
      Testarei quando estiver disponível como problem no URI.

      Excluir
    3. Huum então é isso. O certo seria strlen(palavra)-2. Isso faz diferença na hora de escolher as palavras se alguma delas aparecer mais de uma vez, por exemplo:
      abcd abcd abcdefg
      O certo seria escolher "abcdefg", pois economiza 5 caracteres, mas seu algoritmo talvez ficasse confuso entre escolher "abcdefg" economizando 6 caracteres ou "abcd" economizando 3*2 caracteres.

      Excluir
    4. Exato! Tava pensando se existiria um caso como esse... erros bobos... =/

      Excluir
    5. I don't speak so well portuguese, but i understand so so.... my question is what happen if i have this test case:
      han han hans
      I have 2 posibilities, because if i replace han with h. ... i save 2 characters and hans with h. i save 2 characters too. Is there any case like this in test cases?

      Excluir
    6. perhark, you can see the editorial here, if English is easier for you: http://crbonilha.blogspot.com.br/2014/02/contest-delta-editorial-english-version.html

      This kind of case never occurs at the test cases I made. You will never have to choose between two words that would give the same amount of saved characteres.

      Excluir
  4. No problema "Jogo das Pilhas" eu apenas fiz um somatório de todos os números dados e verifiquei se o resultado é múltiplo de 3. Essa solução acabou passando na competição, mas não sei demonstrar a corretude dessa solução.

    ResponderExcluir
  5. No problema Max, se você não quiser depender dos limites baixos, basta rodar um Dijkstra onde cada vértice é um par (cidade, posição). :)

    ResponderExcluir
  6. No problema Max, estou recebendo TLE com 1s, sendo que na descrição do problema diz que o timelimit é 5s. Inclusive, tentei uma solução com bitmask, tentei submeter sua solução, mas todas dão TLE, o que acho estranho, pois as restrições do problema são bem baixas...

    ResponderExcluir
    Respostas
    1. Estranho...
      Me envia seu código pra eu dar uma olhada, se quiser.
      O meu e-mail está ali na aba Contato.

      Excluir