11852  Knight's Trip
Moderator: Board moderators

 New poster
 Posts: 9
 Joined: Sat Jun 12, 2010 2:11 pm
 Location: Ulaanbaatar, Mongolia
 Contact:
11852  Knight's Trip
Hi,
Any Hints How to solve this problem?
http://uva.onlinejudge.org/contests/263 ... 11852.html
Thanks in Advance
Any Hints How to solve this problem?
http://uva.onlinejudge.org/contests/263 ... 11852.html
Thanks in Advance
Re: 11852  Knight's Trip
A Pure Greedy algorithm will solve it ...
generate the output for a Board n*n and by induction find the solution to (n+1)*(n+1)
the minimum number of moves are at least the (x+1)/2 , and also at least (y+1)/2 since you can more at most 2 row or column each time ... and the total of 3 cells each time .... so the number of moves is also at least (x+y+2) /3 ....
we suppose that cell 0,0 is colored white ...
so if the target cell is also white we need even number of moves ...
else if target cell is black we need odd number of moves ...
there are 4 cells in the Board that dont use the Principle mentioned above and you need to check this cases ...
now its easy to find the solution ...
you can find usefull hints for this kind of Problems in Algorithmic problem solving book .......
generate the output for a Board n*n and by induction find the solution to (n+1)*(n+1)
the minimum number of moves are at least the (x+1)/2 , and also at least (y+1)/2 since you can more at most 2 row or column each time ... and the total of 3 cells each time .... so the number of moves is also at least (x+y+2) /3 ....
we suppose that cell 0,0 is colored white ...
so if the target cell is also white we need even number of moves ...
else if target cell is black we need odd number of moves ...
there are 4 cells in the Board that dont use the Principle mentioned above and you need to check this cases ...
now its easy to find the solution ...
you can find usefull hints for this kind of Problems in Algorithmic problem solving book .......
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)

 New poster
 Posts: 9
 Joined: Sat Jun 12, 2010 2:11 pm
 Location: Ulaanbaatar, Mongolia
 Contact:
Re: 11852  Knight's Trip
Thank you very much.
Re: 11852  Knight's Trip
Thanks for your help.
But can you tell me where to download "Algorithmic problem solving book"?
I looked at google but cannot find.
Thank you again.
But can you tell me where to download "Algorithmic problem solving book"?
I looked at google but cannot find.
Thank you again.
Re: 11852  Knight's Trip
You could find it here: http://uvatoolkit.com/material.php
Re: 11852  Knight's Trip
Thanks Igor9669.
Following your link I found this course by the author but I cannot download the book (maybe this link is not avaiable).
If you have this book, can you sent to me via my email : doulce2000@yahoo.com.
Thanks you much!
Following your link I found this course by the author but I cannot download the book (maybe this link is not avaiable).
If you have this book, can you sent to me via my email : doulce2000@yahoo.com.
Thanks you much!
Re: 11852  Knight's Trip
sent
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)

 New poster
 Posts: 18
 Joined: Sat Nov 20, 2010 7:44 pm
Re: 11852  Knight's Trip
i search it in the internet but i can´t find it!!!, so please can you send it to my email????....kavic1@hotmail.com
Thanks
Thanks