ADASHOP2 Video Solution

editorial
,
1

Official editorial coming soon
Video link: https://www.youtube.com/watch?v=T3447ARuW-w

2 Likes
2

BASH :slight_smile:

3

This was the easiest of all.
Here’s my code which proves why-
https://www.codechef.com/viewsolution/30316527

1 Like
4

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

7 Likes
5

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
6

this is also known as backtracking

7

My solution https://www.codechef.com/viewsolution/30495433

8

and then named the question: The sexy Bishop or something.

9

we can use graph traversal too

10

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

11

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.

12

Well mine can be more straightforward then yours :sweat_smile:
https://www.codechef.com/viewsolution/30511072

13

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

14

Dumb solution with complete static values
https://www.codechef.com/viewsolution/30304133

15

Nice try

16

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

1 Like
18

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

19

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.

20

i think you are missing backtracked moves

21

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.