Confusion in CHSQR Problem

help
,
1

I am not getting the definition of F(K) can anyone explain me? and let me know if i am not allowed to ask this in the comment section below and i will delete my question

1 Like
2

For any input K, center of the square will be at the position ((K+1)/2, (K+1)/2) in 1-based indexing.
And according to given conditions, all the rows will contain 1 exactly one time.

Let’s say 1 is located at (i1, j1), (i2, j2), … (ik, jk) positions in k rows respectively.

Now, distance between center and position of 1 for each row can be given by,
|(K+1)/2 - i1| + |(K+1)/2 - j1|, |(K+1)/2 - i2| + |(K+1)/2 - j2|, … |(K+1)/2 - ik| + |(K+1)/2 - jk|

Now, first we have to find minimum value of all k terms stated above. Let’s say minimum value is x. Now, there can multiple possible values of k positions of 1 in square, thus deriving multiple values of x. We need to maximize the value of x. And that max value is F(K).

Formally, F(K) is maximum possible distance from center to nearest 1.

3

If you construct all the squares satisfying the given conditions, and take the distance of the nearest “1” from the center for all of these squares , and then take the maximum of these distances ,after this the result you get is represented by F(k)

3 Likes
4

#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 output treated as wrong?? please help…

5

Please don’t answer this question till the contest is not finished.

6

look at comment section in problem page … its explained there by problem author himself