wow, finite projectives. How many rooks can you place?
@alei basically I used the formula p^2 + p + 1 > N. Gave me all primes between 11 and 37, both inclusive, for given values of N. Then just chose my matrix based on the value of N. The approach worked solely because N started from 100 and thus the smallest matrix (100x100) has 9 rooks per row. And it only increases with N.
You didn’t answer my question though 
What was the time complexity expected for BINARY?
1 Like
I had a very amazing solution for Adarooks. I can place upto 10 rooks… 
in each row.
Your solution looks very interesting. Could you explain it in a lot more detail? I looked through your code and I understand what it does but why does it work?
n*log^2n was not an intended soln for last subtask. O(n) was an intended soln for last subtask.
yes, linear. I’ll add author approach to my blog
@alei sounds good since I am curious if manipulation of the whole block of bits in a single pass wasn’t enough optimization, what was.
I would say its a coincidence because if N would have been smaller my approach would have failed. But any incidence matrix of this sort has this inherent property that the 1s do not form a rectangle and that is what we needed for this question. Since the whole matrix has this property, it wasn’t likely that its subset won’t have it as well. The only question was of satisfaction of 8N criteria, which I checked at N = 100.
@sapjv You can also use cout << setprecision(10) << n/2.0; as the setprecision function removes the error caused due to double.
You live real THUG LIFE! 
1 Like
I don’t know where is the editorial of may long challenge? Please help me to find the link.
Quite pathetic that some people always ask for solutions on StackOverflow and try to climb rating that way: algorithms - How do we place $8n$ objects in a grid of size $n \times n$? - Computer Science Stack Exchange I don’t know what’s the point doing stuff this way.
4 Likes
How the stackers and some people here are able to solve it so fast…I have given a lot of time to this question still did not got anything on time…Is the finite projections solution so obvious?..i have not even heard of it…any good tutorials for it??.. 
not published yet…
same i am thiking !
1 Like
No bro no… The obvious solution is this one… In the first column, place rooks at co-ordinates:-1,4,7…47 … Then for the second column, add 1 to previous co-ordinates and hence, the problem is over 
Link to my solution:-CodeChef: Practical coding for everyone
@thesmartguy read this. Its the same question and more than 2 years old. My guess is this is why a lot of people knew about this approach.
1 Like