CHSQR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Simple

PREREQUISITES:

Basic programming skills

PROBLEM:

Given an odd integer K, you are required to find a K * K matrix such that each cell has a value between 1 and K and no two cells on the same row or column have the same value, among all the ways you should choose the one in which the distance between the center cell and closest cell containing value 1 is maximum possible.

EXPLANATION:

prove that F(K) = (K-1)/2:

First, it’s easy to see that F(K) can’t be bigger than (K-1)/2 because let’s consider the row which contains the center cell, in this row we should choose exactly one cell to have a value 1, if we choose leftmost or rightmost cell then the distance from the center cell would be (K-1)/2 so F(K) can’t be bigger than (K-1)/2.

now let’s prove that we can always find a matrix that satisfy F(K)=(K-1)/2, let’s fill the central row with values like this: 1 2 3 4 … K, and for each row below the central row we make it equal to the left shift of the row above it, and for each row above the central row we make it equal to the right shift of the row below it. in this way all cells which have value 1 will have at least (K-1)/2 distance from the center cell, and no two cells on the same row/column will have same value.

example filling the matrix

let’s try an example of how to create the matrix with K=5

first of all, let’s fill the central matrix as we described below (1 2 3 4 5) so we have the matrix like this so far:

* * * * *
* * * * *
1 2 3 4 5
* * * * *
* * * * *

after that, let’s fill the 4th row, it should be equal to the left shift of the central row so it’s (2 3 4 5 1), for the 5th row it’s again left shift of 4-th row so it’s (3 4 5 1 2) so the matrix so far is like this:

* * * * *
* * * * *
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2

now for the rows above the central row, let’s start with 2nd row, it is right shift of central row so it’s (5 1 2 3 4) the 1st row is right shift of 2nd row so it’s (4 5 1 2 3)

so we have the final matrix like this:

4 5 1 2 3
5 1 2 3 4
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2

implementation details

We can follow the details step by step to obtain the matrix. however, if you write down the matrix for few sizes you will notices an interesting pattern, if we first decrease all values by 1 so that we deal with 0-based numbers we will notice the upper-left cell have value (K+1)/2, if the index of the row or the column is increased by 1 then the value will be increased by 1 (modulo K) so we can figure out an immediate formula for each cell based on the indices of its row and column, which is simply mat[i][j]=((K+1)/2 + i + j) % K + 1, note we added 1 in the end in order to return to 1-base.

so we can use 2 nested loops and then write the formula inside them

int main(){
	cin>>K;
	for(int i=0;i < K;i++){
		for(int j=0; j< K;j++){
			cout<< ((K+1)/2 + i + j) % K + 1<< " ";
		}
		cout<< endl;
	}
}

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2

Will the left shift by 1 of matrix obtained from mat[i][j]=((K+1)/2 + i + j) % K + 1 be taken as a valid output?

  • 5 1 2 3 4
  • 1 2 3 4 5
  • 2 3 4 5 1
  • 3 4 5 1 2
  • 4 5 1 2 3

Is the above matrix valid? for k = 5

3

@jeffrycopps_2 Yes the output should be correct.

4

What does the phrase ‘closest cell containing value 1’ means. In the final matrix given above the distance between the position (3,3)[center of the square] and (5,4)[position of 1] is equal to 3 which is greater than (k-1)/2(as k=5 here) . What am I missing here??

5

There are some cells containing 1 with distance 2 to the center cell

6

But they are not the maximum distance right? Because the distance between the position (3,3) and (5,4) is 3?? In the question it is mentioned as maximum possible distance? So why the maximum distance is taken as 2 instead of 3 in this case…

7

@vishalraghavan closest cell containing 1 means that you have to maximize the distance of nearest 1 from the center, i.e., in question each row will contain numbers from 1 to K so, consider the middle row i.e., (k+1)/2th row the maximum distant cell from center is the end cells of that row, that means the maximum distance of closest 1 you can get from the center is if you put 1 in either first column((k+1)/2,1) or in last column((k+1)/2,k) of this row, and now you have to arrange other 1’s in such an order that any value of 1 doesn’t get lower distance than this value.

8

Thank you very much!!

9

#include

using namespace std;

struct node
{
int num;
node *next;
};

node *top=NULL,*save=NULL,*node1,*temp;

int main()
{
int t,n,i,j;
cin>>t;
while(t–)
{
cin>>n;
if(n==1)
cout<<n<<endl;
else{
for(i=0;i<n;i++)
{
node1=new node;
node1->num=i+1;

        if(top==NULL)
        {
            temp=node1;
            top=node1;
            node1->next=NULL;
        }
        else
        {
            node1->next=top;
            top=node1;

            if(i==n/2)
                save=node1;
        }
    }

temp->next=top;
temp=top;
top=save->next;
save=save->next;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j==n-1) // for removing the trailing space
{
cout<num;
save=save->next;
if(save->next==NULL)
save=temp;
}

            else
            {
                cout<<save->num<<" ";
                save=save->next;
                if(save->next==NULL)
                save=temp;
            }
        }
    cout<<endl;
    top=top->next;
    if(top==NULL)
        top=temp;
    save=top;
    }
}

}

return 0;
}

**Why is my answer treated as wrong??? **

10

The problem described is a similar to the printing of a particular pattern.

Here’s my solution.

1 Like