What is the logic behind the numbers you have stored in d??
1 Like
My solution is based on randomisation. It totally makes since since 8*N << N * N.
If we do probabilistic Analysis, We need to choose 8 cells out of every N. And N being So Large it is quiet Understood that Probability of choosing wrong cell is very less.
Hence Maintain an array of already chosen cells. Each time select a new cell randomly and check with existing cells if it forms rectangle or not. If it does, go for another cell. If it doesn’t then place a rook in this cell and add this cell to the array of existing cells.
My Solution https://www.codechef.com/viewsolution/24248890
6 Likes
The d are slope of diagonals on which rooks are placed, we choose them in such a manner that distance between any two of them is not the same. Though many such combinations are possible we choose the one which can have more than 8*N rooks.
How to Choose ?
It is a fact if we form diagonal on a N x N grids then main diagonal one from top left corner to bottom right corner will can have maximum number of Rooks = N , that’s it you need to make diagonals/lines nearer to main diagonal so that you can reach 8*N rooks.
it is possible that you may end up getting 750-760 , 780-785 rooks for some d[] the work around is simple if you are getting some less rooks start by adding 1 , 2 ,3 … to all elements of d[] so that some diagonals become of greater length and number of rooks would increase. Adding a constant to all elements of d[] would not do any harm for obvious reasons.
The speciality of this solution is that if you are able to get greater than 800 rooks for N = 100 , it is done for all values >100 as increase in length of diagonals is more significant than increase in N.
Hope this helps 
My Java solution for problem similar to one proposed by @oleg_b
FastReader fs = new FastReader();
int t = fs.nextInt();
// optimal Line Slopes
int slopes[] = {-90,-74,-59,-38,-24,-14,-6,-1,3,5,6,77};
while (t-- > 0) {
int N = fs.nextInt();
for( int i = 0 ; i < N ; i ++ ){
for(int j = 0 ; j < N ; j++){
if(Arrays.binarySearch(slopes,j-i)>=0) {
System.out.print("O");
}else{
System.out.print(".");
}
}
System.out.println();
}
}
2 Likes
I have the best solution. I stumbled upon it with luck. In the first column, keep rooks at co-ordinates:- 1,4,7,…43. Now for 2nd,column, just add 1 to the previous co-ordinates. Problem over. Took me only an hour to figure out 
4 Likes
@anon55659401,
Bro your output is very simple(not as complicated as of others).
and your variable names are awesome . XD
Just wanted to know …
how you arrive at this solution.
or how to find these coordinates.
2 Likes
I was not able to find these magic numbers for the diagonals, just found some of them, based on tries with prime numbers.
So I simply filled the missing fields randomly, checking each field if it is possbile to fill it.
wow ! really an unique approach and best thing about this solution is as N increases time will reduce as difference between 8N and NN also increase (correct me if i am wrong ).
I do not get the part with “if(n<125)…”
Can you explain?
Hahaha…
Link to my solution:-CodeChef: Practical coding for everyone
First of all, I’m a very chill person… I have end sem exams from 3-May to 18-May, so I knew I can’t devote more than 4-hours to the Long. So I did all my submissions on 11th may 
I realized this long is a bit hard…so to chill more ,I turned on my AC…wrote a code which checks if there is any rectangle or not… I place 2 rooks in each column… At 1 and 4 position, and my program said no rectangles, so I solved the problem for 2N rooks, now I placed the 3rd rook at 5,6 position, it did not work, so I placed it at 7 and program said no rectangle I kept placing other rooks like this till I reached 8N and finally submitted happily
Easy and smooth
1 Like
Absolutely correct. Ironically the time taken for n=1000 << time taken for n=100. You can see That for n<125 i have to generate points serially and check instead of random generation.
2 Likes
Execution time is inversely proportional to n( since n is small, same point may get repeated many times). Thus for small values, I generated points serially instead of random generation (so that same point isn’t repeated). Hence there is special condition for n<125
1 Like
you remember once we are talking about algo with O(1/n) complexity . see his solution is little similar to that XD.
1 Like
Lololololol, I am the famous creator of O(1/N) algorithm which can be applied to any problem. I guess it has been leaked 
Yea,the constraints were misleading, it is easy to do for n=1000,then n=100😂
1 Like
and impossible for further smaller N 
1 Like
Here is the unofficial editorial for ADAROOKS:- Unofficial Editorial for ADAROOKS2-MAY-2019-LONG-CHALLENGE
I added a note in my original reply - please see above.
I came upon a mathematical generalisation to this.
There always exists such a way of placing rooks such that there are p^3 rooks in a p^2*p^2 board where p is a prime. This relies heavily on modular arithmetic. The basis idea to be considered it is that the set a.x mod p where x varies from 0 to p-1 comprises of all numbers between 0 and p-1 when a is co-prime to p.
Using this, I pre-computed solutions for 121, 169, 361 and 1369. Then, I crop out the first n^2 elements from whichever pre-computed solution is necessary.
https://www.codechef.com/viewsolution/24207746
Just in case someone wants a look.
2 Likes
Thanks for sharing, this is wonderful! I was trying to do something similar but wasn’t able to. I was hoping I’d find a solution like this in the editorial or in the blog, so feels great to find one. Other solutions are very boring and ugly (no offense ).
1 Like
Never really thought that this question could have been done this way also, very unique approach.