10752 - Distant Jumping

sunny · Post by **sunny** » Tue Jul 24, 2007 3:14 pm

This problem seems to be finding the Hamiltonian Cycle of graph.
But 2000 vertices, so how to speed up?

mf · Post by mf » Tue Jul 24, 2007 3:21 pm

Find an efficient algorithm, of course!

Think about the following:

The jumper can jump from city A to city B if there is a way from A to B over the roads containing at most three roads.

Thanks to this restriction, a linear-time algorithm exists.

Monsoon · Post by **Monsoon** » Sun Sep 09, 2007 5:33 pm

Hi, could anyone help me?

http://online-judge.uva.es/board/viewtopic.php?t=21548

thanks in advance

rio · Post by **rio** » Tue Nov 20, 2007 3:07 pm

I'm having same problem as Monsoon.

This problem is easy to check if the solution is valid, so its strange getting WA..
Maybe the problem with the new server.
Could someone who got AC with the old server see if it could still get AC ?

Thanks in advance.
----
Rio

mf · Post by mf » Tue Nov 20, 2007 5:16 pm

My old AC solution gets WA on the new judge.

Edit: in case admins are going to investigate this, the old AC submission's number is 5187713.

rio · Post by **rio** » Tue Nov 20, 2007 6:15 pm

Thanks mf. I'll report this to "Bugs and suggestions".

----
Rio