I wanted to share my solution to this problem here. I’m pretty much sure there exist many other approaches, so I was curious to use the opportunity in this discussion forum to learn from each other’s ideas. The contest is now officially over, so it makes sense to discuss the problems from it freely.
4 Likes
An observation to start with is that the problem exhibits additivity in the sense that if we know solutions for a board N_1 x N_1 and for a board N_2 x N_2, then we can combine them to get a solution for a board with size N = N_1 + N_2, by first placing the N_1 x N_1 solution in the top-left corner of a N x N board, then along the main diagonal adding the N_2 x N_2 board, and leaving all other items of the N x N board to be free (place no rooks there).
This is because the first board contains at least 8N_1 rooks, the second one has additionally at least 8N_2 rooks, giving us a total of at least 8N rooks. The rectangle-free property of the two solutions gives us rectangle-freedom of the combined solution: this is because any rectangle in the bigger board either lies entirely in one of the smaller ones, or touches both no-rooks areas → all these cases are impossible.
So next step is to focus on inventing a solution for some fixed size of N, or possibly a couple of different sizes of N, and then combine these solutions to arrive at a solution for each possible size in the task input: [100, 1000].
Let’s take two different lines (rows) from any given rectangle-free solution, and treat them as 0/1 vectors, where 1 means we have a rook at the given position, and 0 means we don’t have a rook. The rectangle-free property can be alternatively stated as: any two different lines contain at most one 1 in the same position.
This is what naturally led me to incidence matrices of finite projective planes. So what I was after at that point was a purely mathematical solution to the problem, with little-to-none computer science involved.
It is a well known fact that for each prime power N there exists a finite projective plane of order N, which constitutes of N^2 + N + 1 points, N^2 + N + 1 lines, where each line contains N + 1 points, each point belongs to N + 1 lines, and every two different lines contain exactly one common point (their intersection). The incidence matrix of such a plane, is a square (N^2 + N + 1) x (N^2 + N + 1) matrix of 0s and 1s, each line of which contains exactly N + 1 number of 1s (they indicate which points are lying on this line), and the number of common 1s in each two different lines is exactly one.
So incidence matrices of finite projective planes are automatically rectangle-free!
This is exactly what we need. Let’s enumerate some prime powers N, and corresponding value of N^2 + N + 1:
N: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, ...
N^2 + N + 1: 7, 13, 21, 31, 57, 73, 91, 133, 183, ...
While it is not necessarily true that all the values N^2 + N + 1 are at least 8N, one can write a trivial small program to prove that each integer N in the interval [100, 1000] can be expressed, in the obvious greedy way, as a sum of integers x_i in the second sequence above, such that the corresponding sum of rooks is at least 8N. The number of rooks for each individual x_i is equal to x_i multiplied by (1 + the corresponding number in the first sequence).
In fact, as I didn’t want to generate too many incidence matrices, I started searching for a minimal subset of these numbers which satisfies the conditions above. Simply cutting off numbers from these arrays, and testing if the shorter sequence works. And this is the one I found:
N: 3, 4, 5, 7, 9 → call this array b_i
N^2 + N + 1: 13, 21, 31, 57, 91 → call this array a_i
Theorem: Each integer N in [100, 1000] can be greedily expressed as a sum of numbers a_i (not necessarily different) such that the corresponding sum of a_i(1 + b_i) is at least 8N.
Proof: write a program and test that.
So all we need are the incidence matrices of the finite projective planes of order 3, 4, 5, 7 and 9, and then simply combine them as described above (technically speaking, for some order N, like N = 9, there exist more than one non-isomorphic planes of order N. The incidence matrix of any one of them will do, we don’t care which one. As long as it is an incidence matrix, it is rectangle-free, and that’s all we care about).
But how do we build these matrices and/or where to find them?
This article mentions the cyclic model of building these matrices - https://www.famnit.upr.si/sl/resources/files/konference/DM2012/kiss/dm2012-kiss.pdf - and gives the corresponding module sequences for the ones with order 3, 4, 5, 7 (page 22 of the PDF document). I wrote a stupid brute force program to find a module sequence for N = 9.
To give you an example, for the case N^2 + N + 1 = 13 here is the incidence matrix of the finite projective plane of order N = 3, built with the cyclic model, module sequence = {1, 2, 5, 7}, you can easily see the pattern on where we place the rooks, and then shift it on each next row to the right (circularly). Total number of rooks is (N + 1)(N^2 + N + 1) = 52
1\,1\,0\,0\,1\,0\,1\,0\,0\,0\,0\,0\,0
0\,1\,1\,0\,0\,1\,0\,1\,0\,0\,0\,0\,0
0\,0\,1\,1\,0\,0\,1\,0\,1\,0\,0\,0\,0
0\,0\,0\,1\,1\,0\,0\,1\,0\,1\,0\,0\,0
0\,0\,0\,0\,1\,1\,0\,0\,1\,0\,1\,0\,0
0\,0\,0\,0\,0\,1\,1\,0\,0\,1\,0\,1\,0
0\,0\,0\,0\,0\,0\,1\,1\,0\,0\,1\,0\,1
1\,0\,0\,0\,0\,0\,0\,1\,1\,0\,0\,1\,0
0\,1\,0\,0\,0\,0\,0\,0\,1\,1\,0\,0\,1
1\,0\,1\,0\,0\,0\,0\,0\,0\,1\,1\,0\,0
0\,1\,0\,1\,0\,0\,0\,0\,0\,0\,1\,1\,0
0\,0\,1\,0\,1\,0\,0\,0\,0\,0\,0\,1\,1
1\,0\,0\,1\,0\,1\,0\,0\,0\,0\,0\,0\,1
So here is the final solution: CodeChef: Practical coding for everyone
It simply breaks N into summands within the array A[] = {13, 21, 31, 57, 91}, and for each one of these summands prints out the incidence matrix, as per its module sequence (called adds in the program)
Note: I know this might be a bit disappointing to those of you who appreciate only computer science solutions, but to give you an idea about this approach and its power: for N = 91 the solution contains 91(9 + 1) = 910 rooks which is much bigger than the desired amount of 8N = 728. We have placed 182 = 2N more rooks than desired! 
Finally, I enjoyed thinking on this problem a lot. I would have never arrived at this solution within pressuring time constraints of a ‘normal’ contest of a couple of hours. So I would like to use this opportunity to thank the CodeChef platform for inventing these long rounds. They are really awesome opportunities to dive deeply into the problems without worrying too much that time is ticking away.
5 Likes
I developed my answer from the question, where it says 8N rooks have to be placed. So I first thought that I’ll need 8 rooks per column and row (think symmetry). The result was I was always missing out nearly 40-60 rooks no matter what sort of starting placements I chose.
See this Fitting 8 per column. My approach is a greedy one, filling from left most column to right.
Finally to get it to work, I just changed per column limit to 9, giving this answer 9 max per column. I still don’t understand how it is proved 8N elements minimum are possible. Waiting for the tut.
1 Like
guys pls checkout max power problem and help me
The diagonal approach is quite optimal. For the given constraints, the solution is short:
#include <bits/stdc++.h>
using namespace std;
int main() {
const vector<int> d = {0, 1,-2, 5,-8, 15,-20, 31, 42,-48};
int T, N;
cin >> T;
while(T--) {
cin >> N;
vector<string> s(N, string(N, '.'));
for(int k : d) {
if (k >= 0) { for (int n=k; n<N; ++n) s[n-k][n] = 'O'; }
else { for (int n=-k; n<N; ++n) s[n][n+k] = 'O'; }
}
for(auto& row : s) { cout << row << "\n"; }
}
return 0;
}Extra note how the d numbers were chosen:
We start with diagonal 0. At this point we are free to add any other diagonal but we choose diagonal 1 since it gives the greatest number of rooks (the diagonal -1 has the same).
Now the diagonals -1 and 2 are “tainted”. Therefore we choose diagonal -2 as the greatest one. Now the following diagonals are also “tainted”:
-2 + 0 => 2
-2 + 1 => 4
-2 + 0,1 => 3
0 + -2 => -4
1 + -2 => -5
1 + 0,-2 => -3A “non-tainted” diagonal closest to 0 is 5 now, so we choose 5. As a result, the following diagonals become “tainted”:
5 + 1 => -3 (double-tainted)
5 + 0 => -5 (double-tainted)
5 + -2 => -9
5 + 0,1 => -4 (double-tainted)
5 + 0,-2 => -7
5 + 1,-2 => -6
1 + 5 => 9
0 + 5 => 10
-2 + 5 => 12
0,1 + 5 => 6
-2,1 + 5 => 8
-2,0 + 5 => 7A “non-tainted” diagonal closest to 0 is -8 now, so we choose -8.
Rinse and repeat until the aggregated sum of rooks exceeds 8N for N=100.
5 Likes
My solution depended on the idea that if we divide the board into at least 8 by 8 equal-sized square blocks, with one rook in each row and one in each column of each block, then the problem is to fill the blocks so that the condition about rooks forming a square is satisfied. I started by filling the top left block diagonally, and repeating this pattern along the top row of blocks and down the left row of blocks. For the next block in from the corner, shift each rook one place to the right, moving the rook in the last row to the first column. For subsequent rows and columns, move the rooks (row_i * column_i) to the right, where the indexes are counted from 0.
In order to avoid repetitions, the length of the side of each block must be a prime number. So I first evaluate the side as Ceiling(Sqrt(N)) and then round up to the next prime number. We always have at least 9N rooks on the board. In the implementation I cache the board for each possible prime number up to 37, for N up to 1000.
You can see my solution (in C#) at CodeChef: Practical coding for everyone
1 Like
Let me clarify the sentence above. It should read
For each row of subsequent blocks, move the rooks (row_i * column_i) to the right, where these are indexes of the blocks counted from 0.
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