10422 - Knights in FEN
Moderator: Board moderators
10422 - Knights in FEN
What is the best algorithm for this problem? I tried a backtracking and it ran for 2 seconds, but there are more rapid solutions, say instant...
@+!
DitriX
DitriX
Hello.
I've just solved the problem by DFS. However, my program runs pretty slowly (>> 7 sec)!!!! >_<
I know that there are some much faster methods. Could anyone plz explain them to me??? Many thanks!![:roll:](./images/smilies/icon_rolleyes.gif)
Note: after some simple modification, my program gets ACC in <<1 sec !
However, I'm still looking for faster algorithm...![:lol:](./images/smilies/icon_lol.gif)
I've just solved the problem by DFS. However, my program runs pretty slowly (>> 7 sec)!!!! >_<
I know that there are some much faster methods. Could anyone plz explain them to me??? Many thanks!
![:roll:](./images/smilies/icon_rolleyes.gif)
Note: after some simple modification, my program gets ACC in <<1 sec !
However, I'm still looking for faster algorithm...
![:lol:](./images/smilies/icon_lol.gif)
Last edited by Observer on Mon Aug 04, 2003 12:31 pm, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Say, how should I solve this problem within reasonable time if n <= 20??? ![:confused:](//cdn.jsdelivr.net/gh/twitter/twemoji@latest/assets/svg/1f615.svg)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Could you explain more clearly pls??
By the way, it would be great if the path can be obtained as well!![:P](./images/smilies/icon_razz.gif)
By the way, it would be great if the path can be obtained as well!
![:P](./images/smilies/icon_razz.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
bidirectional bfs
i used IDA* and solved in 0.000sec.
if n<=20 try bfs from both the start and goal
the bfs tree grown from the start will meet the one grown from the goal at some node x
then start ~> x ~> goal is the path
if n<=20 try bfs from both the start and goal
the bfs tree grown from the start will meet the one grown from the goal at some node x
then start ~> x ~> goal is the path
Re: bidirectional bfs
Wow!!!!!!! Really great!!!!!!!!!CelebiX wrote:i used IDA* and solved in 0.000sec.
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
This method sounds feasible! But I'm still not so familiar with BFS......CelebiX wrote:if n<=20 try bfs from both the start and goal
the bfs tree grown from the start will meet the one grown from the goal at some node x
then start ~> x ~> goal is the path
But why would this method be efficient? Could you explain plz?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Hello! It's me again.
While doing BFS we need to keep a boolean array to see whether a "node" is visited, is that correct?
But in this question, possible configurations = 25!/(12! 12!) = 67603900
So keeping such a huge array is definitely impossible!! (MLE for sure!!!)
So what should I do? Plz help!!!!![:cry:](./images/smilies/icon_cry.gif)
While doing BFS we need to keep a boolean array to see whether a "node" is visited, is that correct?
But in this question, possible configurations = 25!/(12! 12!) = 67603900
So keeping such a huge array is definitely impossible!! (MLE for sure!!!)
So what should I do? Plz help!!!!
![:cry:](./images/smilies/icon_cry.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
I came to see this post eventually and did not solve this problem.
Anyway.. as I understand the post, the size of the state space is pretty large, but by using the method posted above, the number of nodes that you actually have to traverse can become VERY small.
So you can apply some hashing or clever data structures to check if you have visited a node already or not.
It's a late night in Korea and I'm going to bed now, but when I get an AC I'll come back![:)](./images/smilies/icon_smile.gif)
Anyway.. as I understand the post, the size of the state space is pretty large, but by using the method posted above, the number of nodes that you actually have to traverse can become VERY small.
![:)](./images/smilies/icon_smile.gif)
It's a late night in Korea and I'm going to bed now, but when I get an AC I'll come back
![:)](./images/smilies/icon_smile.gif)
JongMan @ Yonsei
I see that the number of "nodes" visited will never exceed 60000......
But how to implement??
But how to implement??
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org