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๐
and impossible for further smaller N
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.
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 ).
Never really thought that this question could have been done this way also, very unique approach.