Problem Link : - Contest Page | CodeChef
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 )