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

×

ADASCOOL - Editorial

0
1

PROBLEM LINK:

Div1
Div2
Practice

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

DIFFICULTY:

Simple

PRE-REQUISITES:

Logic reasoning, Conditionals

PROBLEM:

You are given a $N*M$ matrix where every element can be swapped by its direct neighbour (up, down, left and right). Is it possible to swap them such that no element is at its original place?

QUICK-EXPLANATION:

Key to AC- Realize that answer is not possible only if $N$ and $M$ both are odd.

We can prove that, if at least one out of $N$ or $M$ is even, then an answer exists (Eg- say, if number of columns are even, then swap elements at column $1$ with those at column $2$, column $3$'s elements with column $4$'s etc.). However, if both $N$ and $M$ are odd, there will be at least $1$ student who cannot be fitted anywhere, making the answer as NO.

The implementation for iterating over all cells, checking the condition and updating answer is below-

View Content

EXPLANATION:

Since this is one of the simpler problems, the editorial will be written in a way as such, how you can think during contest to have solved this problem. We will start with analyzing trivial cases, and then expand them to complex ones , i.e., typical divide and conquer :) (Divide the problem into cases which are easy to conquer :p)

1. Trivial cases-

Lets forget that we have a matrix. Lets say that we only have $1$ row and $M$ columns. Lets analyze this scenario.

  • If $M$ is even, then we can swap students at column $1$ and $2$ with each other, elements at column $3$ and $4$ with each other and so on. Since $M$ is even, every student has been swapped.
  • If $M$ is odd, you will find that an answer cannot exist.

Lets analyze case of odd $M$ more deeply. Say, we take example of $M=3$. Say, the initial seating arrangement is like $1,2,3$. We need to make sure no element is at its place. But notice that $1$ and $3$ both have only $1$ option, i.e. $2$'s table. But only $1$ student per table is allowed, hence no answer.

Lets take another, $M=5$ now. We place $1$ at $2's$ place to get $.1...$ (supposing we are yet to seat rest of them). Now, if we seat $2$ at $1's$ place, we get a case similar to $M=3$ for $3,4,5$ and answer wont be possible. But, if we put $2$ at $3's$ position, it wont be possible to fill $1's$ place and hence $1$ student will still be left.

Nice!! We can extend this logic to claim that if there is only $1$ row, no answer exists for odd $M$. But, whats next?

2. Extending the Answer for $2-D$ Matrix-

Say now we have $N$ rows. Lets again make cases-

  • If $M$ is even, we can follow the pattern discussed earlier for every row and satisfy each row independently. Hence, answer exists.
  • If $M$ is odd - Can we claim that an answer wont exist? Or will we have to take $N$ in account??

Hmm, the $M$ being odd case is not so simple. Lets break it down further-

  • $N$ is even and $M$ is odd - Recall that we can swap $up$ and $down$ as well!! Hence, lets solve the problem independently for each column, by swapping students up and down. (An alternate way to look at it is, just rotate the matrix by 90 degrees such that rows become columns and vice versa. Now apply our previous procedure.)
  • If $N$ is odd and $M$ is odd - In our earlier analysis, when $N$ was $1$, the issues we faced were that, either the last element could not go anywhere, or the seat of first element was vacant. We can prove that the answer for such a case will not exist. The proof is below-

Lets use a chess board proof to prove above claim :)

Label any cell white. Its neighbors must be black. If $N$ and $M$ are both odd, then there are a total of odd number of cells, which means that number of white cells is NOT equal to number of white cells.

Ultimately, the operation asks us to place a white cell to its neighboring black one, and vice versa. But if number of white and black cells are not equal, we can see that there will always be $1$ student left out in every configuration. This completes the proof for non-existence of answer for odd $M$ and odd $N$.

SOLUTION

Setter

View Content

Tester

View Content

Editorialist

View Content

$Time$ $Complexity=O(1)$
$Space$ $Complexity=O(1)$

CHEF VIJJU'S CORNER :D

1. Prove that filling the matrix spirally wont work. (Hint: The last element becomes the middle element).

2. Prove or disprove that the analysis we did above is exhaustive. Did we leave out any possibility? Or did we cover them all due to the constraints of swapping only with neighbours?

3. If $N$ and $M$ are both $\leq 50$, is the value of $T\leq 5000$ reasonable? Can a smaller value suffice? Why/Why not?

4. Notice the spelling of School in Problem Code :D

5. Solve this alternate version of problem-

The problem is same, except that the rows are now, circularly arranged. Meaning, Row $1$ and Row $N$ are adjacent. Give a brief algorithm to solve the problem under this new constraint.

Hints-

View Content

6. Similar problems-

  • Trace - Based on analysis of 2-D matrices.
This question is marked "community wiki".

asked 19 Jan, 16:55

vijju123's gravatar image

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

edited 21 Jan, 01:14

admin's gravatar image

0★admin ♦♦
19.8k350498541


1.when we will shuffle the matrix spirally,the row and column would get reduced by a factor of 2 in each operation.when both the row and column are odd a single element is always left out.

2.All the possibilities were covered due to the constraints. If diagonal shuffling is allowed then the answer would always be YES.

link

answered 21 Jan, 08:39

krm24's gravatar image

3★krm24
312
accept rate: 0%

  1. Correct.

  2. Can you prove the diagonal shuffling one? Are you talking of the circular shuffling problem I gave?

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

5.the ans is always YES because shuffling can be done row-wise.

1->2->3->4....->n->1

link

answered 22 Jan, 09:15

krm24's gravatar image

3★krm24
312
accept rate: 0%

Good try - but theres a corner case!

$N=1$. For this, we cannot follow above logic :p. Will award you $10$ karma for partially correct answer :)

(22 Jan, 12:08) vijju123 ♦♦5★
1

Thanks for the insight.Next time I will do better.

(22 Jan, 23:17) krm243★
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,173
×181
×39
×33

question asked: 19 Jan, 16:55

question was seen: 1,106 times

last updated: 22 Jan, 23:17