Wrong Answer no UVA

Wrong Answer no UVA

por Rafael Junqueira -
Número de respostas: 7
Alguém tem alguns casos de testes para eu testar meu programa? Eu testei todos os casos que minha limitada criatividade poderia imaginar e meu sistema acerta todas! Mas o UVA dá "Wrong Answer".
Explicando meu algoritmo, é parecido com o do Fabrício. Criei uma estrutura de parentesco, armazenando o pai de cada nó. Com o cuidado de acusar os seguintes casos - resultando "is not a tree":
  • Entrada de 2 pais para um mesmo nó;
  • Raízes múltiplas;
  • Grafos sem raízes (com exceção de árvores vazias - onde é permitido);
O número máximo de vértices foi limitado em 50000 e o número de grafos computados por vez em 100000.

Se alguém puder me ajudar agradeço imensamente.
Rafael

PS: alguém acha que poderia anexar meu código? Seria antiético?

Em resposta à Rafael Junqueira

Re: Wrong Answer no UVA

por Gabriel Pugliese -
Eu também não to conseguindo.

Pergunta: Quem conseguiu Accepted aí, colocou que:

  • O pai nunca é filho dele próprio ou;
  • 2 arestas repetidas dá erro. Exemplo: 1 2 1 2 0 0 ???
Já fiz uma porrada de coisa no meu código e só ganho WA triste
Em resposta à Gabriel Pugliese

Re: Wrong Answer no UVA

por Rafael Junqueira -
Ah, Gabriel, bem lembrado! Eu também não permito ninguém ser pai dele mesmo. E o segundo caso (" arestas repetidas dá erro"), é filtrado pela condição de não permitir filhos com mais de um pai.

Em resposta à Rafael Junqueira

Re: Wrong Answer no UVA

por Fernando Fernandes Chaves -
Testem a entrada:

1 2 3 4 4 3 0 0

Cuja resposta deve ser not a tree, obviamente.

Eu também havia deduzido (equivocadamente) que a terceira condição era consequencia das duas primeiras. Mas a entrada acima é um contra-exemplo de que não. Ainda vou corrigir meu algoritmo, mas tenho quase certeza de que esse é o problema.

Quanto a anexar o código, nos fóruns do online-judge isso é comum. Apenas se deve retirá-lo do ar quando o problema for resolvido (ou seja, o que não pode lá são códigos Accepted).

Eu confirmaria com o Rafael ou o Coelho mesmo assim.
Em resposta à Rafael Junqueira

Re: Wrong Answer no UVA

por Pedro P. de S. B. Silva -
pessoal, essa entrada bandida me tomou umas duas horas de debug:

1 2 2 3 3 1 4 5 0 0

(is not a tree)
espero q ajude vcs!

abçs!
Em resposta à Pedro P. de S. B. Silva

Re: Wrong Answer no UVA

por Fernando Fernandes Chaves -
É o mesmo caso da entrada que eu tinha colocado: um grafo circular desconexo de uma dupla pai-filho.

Notem que a entrada só tem uma raiz e o grau de entrada é 1 para todos os vértices, mas é a terceira condição que não satisfaz.

Eu implementei essa verificação e meu programa passou.
Em resposta à Fernando Fernandes Chaves

Re: Wrong Answer no UVA

por Rafael Junqueira -
Finalmente consegui passar também! E com um impressionante limite de vértices em apenas 50! surpreso
Acho que li em algum lugar que este número deveria ser bem grande, portanto não sei se é bem por aí..
Abraço a todos e boa Páscoa!