Official editorial coming soon
Video link: ADASHOP2 Solution - CodeChef March Long Challenge 2020 - YouTube
2 Likes
BASH 
This was the easiest of all.
Here’s my code which proves why-
https://www.codechef.com/viewsolution/30316527
1 Like
Cmon they should’ve made the chessboard something like 69x69.
7 Likes
A recursive solution. Every time I am checking if the node is not visited then move forward. If the node is already visited then backtrack to the previous node whose all neighbour is not visited.
1 Like
this is also known as backtracking
and then named the question: The sexy Bishop or something.
we can use graph traversal too
If someone is a bit meticulous he/she can print all the coordinates without any algorithm and get AC.
Just get the chess piece to the center and next moves are fixed.
I think if the chessboard size was changing and a condition of number of moves shouldn’t exceed n*n (I think I haven’t proved this yet) would work and that way literally writing the coordinates wouldn’t work and people would think of an algorithm
Since the problems states that block (r0, c0) is always black. Thus block (1, 1) may be black or white. That is, there are two possible orientations of chessboard.
Suppose in case 1: (r0, c0) = (4, 2) then this implies block (1, 1) is black. and suppose in case 2: (r0, c0) = (4, 2) then this implies block (1, 1) is white.
Thus using algorithm used in above video there are two possible lists of solution moves.
But since your code is acceptable on the Codechef judge, it seems to me that Codechef ignored one of the two possibilities.
Can somebody tell me whats wrong in my code i had implemented the same thing during the contest and got partial marks
https://www.codechef.com/viewsolution/30401423
Nice try
in problem statement says that all black cells satisfy r+c is even. So (1,1) is always black.
1 Like
Hi!
I implemented this using Graph traversal and used DFS but don’t know why it did not get accepted.
Can someone please help?
The approach:-
First of all, the chessboard I wrote the code for, is like matrix. So, converted the coordinates according to tester’s chess board.
After this, I check if all the black places have been visited. I have a valid moves indicator which tells a move is valid if and only if it lies inside the board and if the present place has not been visited more than once so that every black place is occupied 2 times at max. Then, simple DFS.
Here’s my code:
https://www.codechef.com/viewsolution/30500584
I am printing every move here and not final positions after a move. The concern was to get <=64 moves in total and I printed every move.
i think you are missing backtracked moves
That is being taken care of. I change the coordinates after every call. Moreover, if you print the chessboard in the end, only one type of blocks will be printed and they will have been visited at max two times.