ADASHOP2 Video Solution

Official editorial coming soon
Video link:


BASH :slight_smile:

This was the easiest of all.
Here’s my code which proves why-

1 Like

Cmon they should’ve made the chessboard something like 69x69.


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

My solution

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.

Well mine can be more straightforward then yours :sweat_smile:

Can somebody tell me whats wrong in my code i had implemented the same thing during the contest and got partial marks

Dumb solution with complete static values

Nice try

in problem statement says that all black cells satisfy r+c is even. So (1,1) is always black.

1 Like

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:

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.