Unofficial Editorial for ADAROOKS2-MAY-2019-LONG-CHALLENGE

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 :slight_smile: )

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

Such that no four-of them form a rectangle :slight_smile:

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… :slight_smile:

}

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 :slight_smile:

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

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 :slight_smile:

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 :frowning:

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

Even this goes wrong :frowning:
“1,2,4,7”:—>Also goes freaking wrong :frowning: :sleepy::sleepy::sleepy::sleepy:

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

Goal is 8*n :wink:

Now for 5:-
Try all numbers ahead of 8 like :wink: -
1,2,4,8,9:---->Wrong Answer
1,2,4,8,10:—>Wrong Answer :slight_smile:

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

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

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

Configuration for 8(n) rooks is:- 1,2,4,8,13,21,31,45 :slight_smile:
And my friends, a hard problem has been solved with basic logical approach :slight_smile:

My link to the solution : -
https://www.codechef.com/viewsolution/24244089
(Note:–>For any doubts , ask me in the comments :slight_smile: )

15 Likes

how do you know that you will surely get the some pattern from previous pattern of less rooks. suppose you get the solution of 4N rooks with by doing hit and trial ,then how you can be so sure that after some addition in 4N rooks pattern you will definitely get some pattern for 5*N rooks and so on?

1 Like

Arre bhai, after 4 rooks in a column(you already develop confidence that if you can convert from 3 to 4, then 4 to 5 is also possible) , there is so much space still left in the column, so it is sure that you can place one more rook at some place as question asks about 8(n) rooks, means, you can surely place many rooks up in the column, and the most basic configuration always work, because if you want no 4-rooks forming rectangle then you should never place a pair rooks in a column with same distance between them, in this question if you want AC, you need to take some risks
:slight_smile:

great find. thanks for sharing!

1 Like

if you gotta save all this hit and trial work, you can simply make an array so that no element of it is the sum of any number of consecutive terms of the same array…in order to make the answer array, set the first element of it to 1 and then go on adding the elements of previous array to it!

yup, I already did that and it gives wrong answer bro :slight_smile: So hit and trial is necessary, whatever you mentioned, just implement and submit, and it gives WA,I’ve tried it :slight_smile:

i got ac by implementing it…

The configuration : - 1,(1+1=2),(2+2=4),(4+3=7…),THIS PATTERN GIVES WRONG ANSWER :slight_smile:

that’s not the configuration…difference array works out as {1,2,4,5,8,10,14}
so answer array is:{1,2,4,8,13,21,31,45}

Nope, your pattern is : - 0,1,3,7,12,20,30,44
Which cannot be obtained by adding the previous element :slight_smile:

I’ve given the approach which can be used by the person who is solving this type of problem very first time in the contest :slight_smile: I solved it in the contest and only this approach resonated with me , or else how can we ever find the exact above co-ordinates? Answer?

How did you get : - {1,2,4,5,8,10,14} , can you explain how did you get this??

+how do you prove that your pattern will never form any rectangle ? :stuck_out_tongue:
this one:- {1,2,4,5,8,10,14}

I mean to say we don’t need a program to check…all we have to do is pick a number, check if it can be obtained by adding any number of consecutive elements of the array we are forming and that’s it!!
e.g . i start by {1,2}…now 3=1+2 so {1,2,4}…{1,2,4,5}…now 6=2+4…7=1+2+4…{1,2,4,5,8}…9=4+5…{1,2,4,5,8,10}…11=2+4+5…12=1+2+4+5…13=5+8…{1,2,4,5,8,10,14}…Viola! it’s done!!

3 Likes

assume we find 2 rooks in the same column in 2 different rows…now since the difference between 2 rooks in the same row can not be obtained by adding consecutive terms, there will NEVER be another common rook among those 2 rows…

1 Like

I did not understand what you did but sounds good :slight_smile: + I don’t know why we are trying to find elements which cannot be made by sum of any of the consecutive elements??

There must be some deep logic to it and noob like me did not get it, so I guess hit and trial worked better for me during the contest :slight_smile: :joy::joy::joy:

2 Likes

How did you check that your combination would not form a rectangle ?

Check the editorial, I’ve written the code for it.
Only when I knew that my configuration is free of rectangles, I submitted it, I cannot check for rectangles in the code of problem, as it will give TLE obviously.

I got it thanks. Yours was the easiest to understand. If you don’t mind then can we connect over fb so to communicate in a better way.

1 Like

Thankyou!!! Sure :slight_smile: :slight_smile:

this approach is simply elegant

1 Like