TOPIC

PROBLEM 1482 - URI Fórum 1.0

URI Online Judge asked 7 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Junior Andrade replied 7 years ago

    Tentei fazer este exercício utilizando uma pd com bitmask para guardar quais museus eu já passei, e por quais eu ainda posso passar para conseguir visitar o maior número possível de museus, porém, estou tomando TL. Estou no caminho certo, ou há alguma outra abordagem mais eficiente para esse problema?

  • Heveraldo Rodrigues de Oliveira replied 5 years ago

    dois exemplos para testar tle: 15 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 20 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0

  • testoTLE replied 5 years ago

    Isso só é valido para uma viagem completa e que passe por todos os vértices, se existisse um caso com 20 vértices e o máximo possível fosse 19, você tomaria TLE.

  • Guilherme de Lima replied 6 years ago

    Os casos de teste deste problema parece que são bem fracos mesmo. Da primeira vez tentei uma pd bottom up pra verificar as 2^N N possibilidades, com complexidade 2^N N^2, algo parecido com o problema do caixeiro viajante. Como o N vai até 20 deu tle, os casos de teste da maratona rodavam em 7s na minha máquina.

    Depois tentei um backtracking simples que ignorava a pd e acabou passando. Acredito que se incluísse esse caso de teste muitas soluções, inclusive a minha, iriam falhar.

  • Marcus replied 6 years ago

    Esse caso de teste não teria que dar 3 como resposta? O meu algoritmo passou mas com resposta 2

    3 100 100 100 0 100 100 40 0 100 40 40 0 0

    Começar pelo museu 3 -> 2 -> 1 total de 380 minutos

  • Altamir Gomes Bispo Junior replied 7 years ago

    É possível diminuir o runtime registrando-se o melhor tempo de viagem até o momento (ou então a menor profundidade de recursão possível para uma viagem completa) e fazendo o cancelamento de viagens que estejam prestes a estourar.

  • Wyllian Brito replied 7 years ago

    Acredito que você esteja no caminho certo. Minha solução é recursiva, também utilizo bitmask e passou com 1.480s.

  • aajjbb replied 7 years ago

    Os casos de teste para este problema estão fracos. Soluções que recebem aceito aqui levam WA no Live Archive. Acho que os teste aqui não cobrem a possibilidade de ir a um Museum e não visita-lo, sendo que um caminho a-b-c pode ser mais rápido do que a-c.

    Códigos já aceitos também estão tomando compilation error.

    MOD