You are not logged in. Please login at www.codechef.com to post your questions!

×

CHQUEENS - EDITORIAL

PROBLEM LINK:

Practice
Contest

Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Counting, Implementation.

PROBLEM:

Given a field of $N*M$ dimension with King Chef being located at position $(X, Y)$, count the number of ways of choosing positions of two queens on the same field, such that they cannot see each other. If they see each other, it will be chaos (difficult choice for Chef :P)

Chef's Queens, just like chess queens, can see in horizontal, vertical and diagonal direction, but cannot see through King Chef.

SUPER QUICK EXPLANATION

  • Fix position of one queen, and try to count the number of positions where the other queen may reside, without causing chaos.

EXPLANATION

This problem actually has that much only to explain, as I did in super quick explanation, so, I'm sharing my idea, followed by another idea.

First of all, we know, that both queens can see each other if they share a same row or column or diagonal and Chef isn't between two queens.

Suppose, we fix position $(R, C)$ for the first queen.

So, this queen can see in all elements of row R unless barred by Chef, which can happen if CHef and First Queen is in the same row, which happens when $R==X$. Similar explanation follows for the Same column and Same diagonal.

Basically, this is all needed to implement the solution.

For every position, we can see, that two positions are immediately unavailable, the positions of chef and queen. After that, we can count the number of positions in same diagonals (See that a position is lying in two diagonals, from top left to bottom right and the other one from top right to bottom left), as well as same column and diagonals.

My Approach

I Decided to count the unordered pairs of positions of both queens because it reduces number of cases to be considered. (We only need to consider two diagonals, only the part lying to the right of fixed position.)

For a position $(R,C)$ i try to place other queen only in any column right to $(R, C)$, that is, a position with column greater than $C$. We see, that there are $(C-1)*N$ such positions.

But this includes various banned positions.

  • which are in the same row as the First queen. There are $M-C$ such positions.
  • sharing diagonal coming from upper right direction. We can prove that there are $min(M-C, R-1)$ such positions. After these steps, we will either reach the top or right border after these many steps.
  • sharing diagonal coming from bottom right direction. We can prove that there are $min(M-C, N-R)$ such positions. After these steps, we will either reach the bottom or right border after these many steps.

But, out of these positions, some of the positions may not be banned, due to chef being present in between. We can see, that these positions are

  • If sharing the same row as Chef, and Chef lies to the right of Queen, then there are $(M-Y)$ such valid positions.
  • If sharing same diagonal coming from upper right direction, there are $min(M-Y, X-1)$ such valid positions.
  • If sharing same diagonal coming from bottom right direction, there are $min(M-Y, N-X)$ such positions.

In the problem, pairs are ordered, that is, First queen may also lie to right of second queen. So, we multiply this count by 2.

Hence, we have counted the number of ways to place queens without chaos in different columns. But we still need to count the number of ways to place queens in same rows as Chef. But these pairs are unordered.

See, there are $(X-1)$ empty cells above Chef's position and $(N-X)$ empty positions below Chef's position in the same column. We can place the First queen in $(X-1)$ ways and Second queen in $(N-X)$ ways. We can also choose in two ways, whether to place the first queen in the upper position, or second queen. Hence, the total number of ways to place queens in the same row, with the chef in between, is $(X-1)*(N-X)*2$.

Adding this to count above, we have found the number of ways to place queens on board without collision.

Alternative solution

There also exist faster solutions where we first count the total number of ways to place queens and then exclude position pairs, which lead to chaos.

Small hint:

For the same row, with the chef in between, there are $(Y-1)*(Y-2)/2+(M-Y)*(M-Y-1)/2$ such position pairs.

Can you find the whole solution? Can you generalize this form to diagonals? Share your solution in case you achieved this complexity during or after the contest.

PS: Any Comments about Chef having two Queens waiting for him, Even causing chaos, just at sight of another queen? Lucky Chef xD.

Time Complexity

Time complexity is $O(N*M)$ per test case for my solution, though it may also be possible to achieve linear or constant time complexity (I expect).

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 03 Nov '18, 17:30

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 05 Nov '18, 01:11

admin's gravatar image

0★admin ♦♦
19.8k350498541


Hello, @thucnguyen.when i just convert your code into python 2 (by simply replacing input() with raw_input() ) and submit the solution in pypy 2.6.0 and i get the correct answer(https://www.codechef.com/viewsolution/21485615 ). You can read an excellent explanation for this by @gorre_morre here

link

answered 05 Nov '18, 22:59

vipin1407's gravatar image

5★vipin1407
2146
accept rate: 10%

edited 06 Nov '18, 16:59

Explanation link not working, fixed solution link.

(06 Nov '18, 16:11) taran_14076★
1

Everything fixed

(06 Nov '18, 17:06) vipin14075★

I had also been waiting for you Chef Taran ;) . To read this editorial! :)

Thank you for taking my feedback and offering a detailed explanation. I seriously love your editorials! Looking forward to editorials of rest of the questions and November long :)

link

answered 05 Nov '18, 01:59

tarini_1407's gravatar image

0★tarini_1407
352
accept rate: 0%

I submited solution with the algorithm similar to the editorial above, in Python 3 and got Time Out. I then successfully implemented better approach (similar to alternative approach above) with time complexity of O(min(N,M)) for each test case.

Full code is here: https://repl.it/@ThucNguyen1/CHQUEENS

link

answered 05 Nov '18, 07:28

thucnguyen's gravatar image

2★thucnguyen
1
accept rate: 0%

I would like to have some test cases, my solution is not being accepted and I can't figure out why

link

answered 06 Nov '18, 01:02

tuket's gravatar image

3★tuket
1
accept rate: 0%

Like, you may try all positions of the chef on 4*4 board and verify the answer. Or any other random test cases.

(06 Nov '18, 16:11) taran_14076★

I've tried with all 4x4 and 5x5 combinations but my solution is not accepted

(07 Nov '18, 01:34) tuket3★
1

For test case 2 3 1 2, the correct answer is 6 while your code prints 2.

(07 Nov '18, 02:03) taran_14076★

Thank you!!

(07 Nov '18, 02:21) tuket3★

Oh, it was because I had X and Y swapped! So, X was the row and Y the column... Thank for the help!

(07 Nov '18, 02:28) tuket3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×850
×728
×150
×52
×4

question asked: 03 Nov '18, 17:30

question was seen: 850 times

last updated: 07 Nov '18, 02:28