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

×

ADAKNG - Editorial

2
2

PROBLEM LINK:

Div1
Div2
Practice

Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey

DIFFICULTY:

Cakewalk

PRE-REQUISITES:

Basic Looping, $2-D$ arrays, Conditionals, Greedy

PROBLEM:

A king is placed at cell $(r,c)$ $-$ $r$ being the row and $c$ being the column number. How many cells can it visit in at most $K$ moves?

QUICK-EXPLANATION:

Key to AC- Realize either of the $3$ things below-

  • Lets say we want to go at a cell at distance $(k_1,k_2)$. The optimal strategy is going diagonally until either $k_1$ or $k_2$ becomes $0$, and then moving horizontally or vertically (as we reached the same row/column now) until the cell is reached. Number of moves traversed are $max(k_1,k_2)$ .
  • This question is a standard BFS on matrix question.
  • The possible cells king can visit will form a square (or rectangle, depending on where he is placed). The area of this figure is the answer.

The quickest and most intuitive way to solve the problem is to realize that to go to a cell at distance of $(k_1,k_2)$ from our starting cell, we need $max(k_1,k_2)$ moves, for example, to visit cell $(X,Y)$ we get $k_1=|X-r|$ and $k_2=|Y-c|$. If the max of these if $\leq K$, we can visit this cell. Check this for every cell and print the answer.

EXPLANATION:

Most of the interesting stuff is there in quick explanation itself. We will simply expand some of the points, see the reasoning of why they occur and derive intuitions to solve such problems in the main explanation. However, the quick explanation section itself is self sufficient :).

1. A cell $(X,Y)$ can be visited if $max(|X-r|,|Y-c|) \leq K$

Lets say that the cell we're checking is $(X,Y)$. Let the distance of this cell from $(r,c)$ be defined as earlier, $(k_1,k_2)$. What happens when you move diagonally? You subtract $1$ from both $k_1$ and $k_2$. Had you moved horizontally, only one of them would have reduced, but because we moved diagonally, we came closer to the cell than we would have come by moving horizontally or vertically.

It is intuitive to see that, Greedy will hold. (Formally, it will hold true because there is no way we can come to a cell in lesser moves by visiting more cells). Hence, we move diagonally as long as we can. Without loss of generality, lets say $k_1 > k_2$. After moving diagonally for $k_2$ moves, the distance left to cover is now $(k_1-k_2,0)$.

Hence, total moves taken = $\underbrace{k_2}_ \text{Diagonally} + \underbrace{(k_1-k_2)} _ \text{Horizontally/Vertically}=k_1$ where $k_1$ was maximum of the two.

As an exercise - Repeat this proof taking $k_2$ as maximum and come to the same result.

2. Standard BFS on Matrix -

Who cares for observation when you can write a quick, bugless code for this algorithm within seconds? Well...technically you should care for observations because they make work quicker. :p

Anyways, theres nothing to tell here in this section, the exact standard algorithm is used. The reason I listed this out here is, because we all want some trivial problems on the algorithm after newly learning it. Mark this question as a good question for practice after learning this algorithm, even if it does seem like an overkill right now. The reason is, if you get a WA or RE in this question, then the fault will be in your BFS part - because thats the only part in this question. You'd hence save some time debugging while you discover an optimal way to implement the algo :)

3. Cells that king can visit will form a square/rectangle-

Setter's solution uses this

Say king is at middle of the chessboard. Refer to image below and observe the pattern-

alt text

  • $k=0-$ Only the cell he is lying on is visited.
  • $k=1-$ He can visit all cells immediately next to him. This is the yellow square in the picture Seems trivial till now?
  • $k=2-$ He can visit all cells on yellow square in $1$ move. We can see from picture that, he can visit all cells of orange square, from yellow square, in additional $1$ move. Hence, he can visit the cells in orange square in $2$ moves.

What about $k=3$? We can do a similar reasoning that, with $1$ more move we can visit all cells of green square from orange square.

From the picture, can we derive some formula for the length of this square? Yes!!

The king, in $k$ moves, can visit cells with column number from$[r-k,r+k]$ and row numbers between $[c-k,c+k]$. However, we also need to check that he does not fall off the board while doing so! (Eg- what if r=1 and k=5?). We see that, on adding the condition of not falling off the board, some rows/columns get removed from square and it becomes a rectangle.

Hence, our expression becomes-

$dx=min(c+k,8)-max(c-k,1)+1$ and $dy=dy=min(r+k,8)-max(r-k,1)+1$ where $dx$ and $dy$ are length of horizontal and vertical sides of rectangle. The $+1$ in the formula is to account for the row/column the king is standing it.

The area, i.e. $dx*dy$ is the answer.

SOLUTION

Setter - Used approach $3$.

View Content

Tester - Used approach $1$.

View Content

Editorialist - Used BFS

View Content

$Time$ $Complexity=O(1)$ for Setter $-O(N*N)$ for tester and editorialist where $N=$length of board
$Space$ $Complexity=O(1)$ for setter and tester $-O(N*N)$ for editorialist

CHEF VIJJU'S CORNER :D

1.Analyze how the question would be different if we replaced king with other chess pieces, say queen, rook, knight etc.
2.Give an algorithm to solve the modified version of the problem-

Instead of $8 \times 8$, the chessboard is of infinite size. You need to tell how many cells can be visited within $K$ moves $(1 \leq K \leq 10^9)$ if the piece we have is a-

  • King
  • Queen
  • Rook
  • Queen (If one of the dimension is finite)
  • Rook (If one of the dimension is finite)
  • Bishop (If one of the dimensions is finite)

Last three are difficult (in fact, you can find a question on the bishop case already). Just try to analyze for the king part and give your answer.

3.Related Problems-

This question is marked "community wiki".

asked 18 Jan, 12:25

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 21 Jan, 01:15

admin's gravatar image

0★admin ♦♦
19.8k350498541


I went with what Chef Vijju is pointing. I initially considered it a board of infinite size.Now for given r,c and k,on an infinite board we could move (2k+1)×(2k+1) boxes. So now just restricting things to 8×8 we can reduce the above expression into {min(8,r+k)-max(0,r-k)+1}*{min(8,c+k)-max(0,c+k)+1}.

link

answered 21 Jan, 02:08

whiteshadow98's gravatar image

4★whiteshadow98
161
accept rate: 33%

edited 21 Jan, 02:10

Correct!!! :)

(21 Jan, 10:38) vijju123 ♦♦5★

(r′−r)^2+(c′−c)^2 ≤ 2 Why this condition is mentioned in problem statement ?

link

answered 21 Jan, 14:09

unknown_11's gravatar image

3★unknown_11
1
accept rate: 0%

To tell how king moves.

(22 Jan, 12:06) vijju123 ♦♦5★

how to solve Anton And Chess problem can anyone explain thanks!

link

answered 21 Jan, 15:27

knakul853's gravatar image

3★knakul853
964
accept rate: 16%

can't we do it using dfs instead of bfs..is there will be any problem??

link

answered 22 Jan, 00:37

bhuvnesh97's gravatar image

3★bhuvnesh97
1
accept rate: 0%

Yes, you can. But I discussed BFS as its a very hot topic on matrices :D

(22 Jan, 12:06) vijju123 ♦♦5★

since the constraints are pretty small..you can just brute force over all possible positions of king for each move https://www.codechef.com/viewsolution/22590129

link

answered 22 Jan, 18:40

ashokshaun's gravatar image

3★ashokshaun
73
accept rate: 33%

edited 22 Jan, 18:44

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:

×1,653
×1,001
×506
×191
×33

question asked: 18 Jan, 12:25

question was seen: 2,123 times

last updated: 22 Jan, 18:44