Problem Link : - https://www.codechef.com/MAY19A/

Editorialist:- https://www.codechef.com/users/karangreat234

**Solution:-**

(I’ll try to explain the solution without any advanced theory or projection planes.I’ll make it very easy and logical to understand…so even a beginner can understand )

Everybody knows that we have to keep atleast 8*N rooks on a chessboard of size NxN… …

Such that no four-of them form a rectangle

First you should create this program, which takes any personal configuration of rooks you have taken and says if there is any rectangle or not…

Here is the pseudo-code : -

//create a 2-D array of size NxN…initialize all the cells with zero…

//i,e… a[i][j]=0

//place rooks wherever you want…

//i,e…a[i][j]=1

i=0;

while(i<n)

{

j=0;

while(j<n)

{

if(a[i][j]==1)

{

//check if there is a ‘j1’>‘j’ , where a[i][j1]=1 ; if yes, then check if there is a ‘i1’>‘i’ such that

//a[i1][j1]1=1…if yes…then check if a[i1][j]==1…if yes, then there

//exists a rectangle and your code is incorrect…

}

j++;

}

i++;

}

Now,lets see how can we place 24-rooks on a 8 cross 8 chessboard : - (Below link shows the exact configuration)

For the first-column, we keep 3-rooks at position:-‘1,2,4’

For the second-column, we just keep 3-rooks at position:-‘1+1,2+1,4+1’

And so on for the next-columns

Hence, for a 100x100 chessboard, I try the following/above approach, and UREKA!!!

I AM ABLE TO PLACE 300-ROOKS ON 100X100 CHESSBOARD WITH NO RECTANGLES…

We reach an observation, for any chessboard of size nxn where, n>=8, we can always place 3*n rooks

Now, the next logical question is how to place 4*n rooks??

I place “4” of them at:- '1,2,4,5’and it shows wrong!!There are some rectangles formed

So, we try for “1,2,4,6”

Even this goes wrong

“1,2,4,7”:—>Also goes freaking wrong

Then I place rooks at 1,2,4,8 position and hurray, I got 4*n rooks configuration

Goal is 8*n

Now for 5:-

Try all numbers ahead of 8 like -

1,2,4,8,9:---->Wrong Answer

1,2,4,8,10:—>Wrong Answer

Finally, correct answer for 5:- 1 , 2, 4, 8, 13

Hence,we got the correct answer for 5*n rooks

Similarly, try for 6(n) , 7(n) and 8(n)…

Configuration for 8(n) rooks is:- 1,2,4,8,13,21,31,45

And my friends, a hard problem has been solved with basic logical approach

My link to the solution : -

https://www.codechef.com/viewsolution/24244089

(Note:–>For any doubts , ask me in the comments )