IEM904-Editorial

editorial
1

Practice

DIFFICULTY:

MODERATE

PREREQUISITES: Data Structure, Backtracking Algorithm

PROBLEM: CodeChef: Practical coding for everyone

Author: Sumanta Chakraborty

EXPLANATION:

Input:

(1,1)
(2,2)
(3,3)
(4,3)

Output:

Invalid
Queen 4
2

Hence, for the above input the 1st queen has been placed at the 1st row, the 2nd queen has been placed at the 2nd row, the 3rd queen has been placed at the 3rd row and the 4th queen has been placed at the 4th row. Also, the column position of each queen is in the range between 1 and 4 (inclusive). Hence, the 1st queen’s cell position is valid.

Now, the 2nd queen is placed in the same diagonal with the 1st queen. Hence, the 2nd queen’s cell position is valid.

The the 3rd queen is placed in the same diagonal with the 1st queen and in the same diagonal with the 2nd queen. So, the 3rd queen’s cell position is valid.

Now, the 4th queen is neither in the same column or in the same diagonal with the 1st queen. So, the 4th queen’s cell position is not valid. Therefore, the output will display ‘Invalid’.

Since the placement is invalid, the output displays ‘Queen 4’ which is the 1st wrongly placed queen which is detected to be at the wrong cell position, starting from the 1st cell position.

Also, since the placement is invalid, Prof. Mondal has imposed new criteria. According to the new criteria, there are 2 sets of intermediate cell positions possible between the 1st and the 4th cell positions. One set of intermediate cell positions between the 1st and the 4th cell positions is {(2,2), (3,4)} for the 2nd and the 3rd queens, respectively because in such moves no two queens have been placed in the same row or in the same column. Similarly, another set of intermediate cell positions between the 1st and the 4th cell positions is {(2,4), (3,2)} for the 2nd and the 3rd queens, respectively.

Test Cases:

1
Input :
(1,1)
(2,2)
(3,3)
(4,3)
Output:
Invalid
Queen 4
2

2
Input :
(2,1)
(3,2)
(4,3)
(1,3)
Output:
Invalid
Queen 1
0

3
Input :
(1,9)
(2,1)
(3,1)
(4,1)
Output:
Invalid
Queen 1
0

4
Input :
(1,1)
(2,2)
(3,3)
(4,4)
Output:
Valid

5
Input :
(1,4)
(2,3)
(3,1)
(4,1)
Output:
Invalid
Queen 3
2

6
Input :
(1,4)
(2,3)
(3,2)
(4,1)
Output:
Valid

7
Input :
(1,1)
(2,2)
(3,1)
(4,3)
Output:
Invalid
Queen 4
2

Source Code (Python 3.6):

Click here

2

IS THERE ANY EDITORIAL FOR IEM901 , IF YES PLEASE SHARE :pray:

1 Like
3

Yes, we will upload the other editorials shortly. We’re doing one by one :slight_smile:

1 Like
4

If they end up like this, there’s no point in posting them. We can already see successful submissions and most users don’t even use python. This is just literal spamming of forums without providing any value. The original problems sucked in their own, the problem statements were messy and now the editorials are a literal piece of crap. You even take time to copy the source code and test cases?! I’d feel ashamed to show this to a group of friends, let alone post it on a public website.