I spended almost 3-4 days in trying to solve this problem and i also caught all your mentioned observations except this " we will create road between two points whose Distance between parallel lines is minimum".
For ADAROOKS, I managed to place \Theta(N \log N) rooks - on row i, place rooks on columns i + 2^k - 1 where k starts from 1 (all 1-based indexes) untill you reach the end of the board. It is not too hard to show that no rectangles will be formed this way. The first row has \log_2(N) rooks, and you can show the asymptotic behavior claimed.
The actual number of rooks will eventually be greater than 8N, because of the asymptotics.
However, for N = 100, the above gives around 500 rooks only. You need to find certain diagonals in the bottom quadrant (currently empty) along which you can place rooks to reach 800. This made it tricky, but I got an AC this way.
TREEDEG too was quite hard. I got the generating function for all trees on n vertices, but then, the actual answer you need requires evaluating some n^{th} mixed derivative at some n-dimensional point. Will be very interesting to see if someone actually solved it this way, I feel like DP was the actual way to go here.
In the problem WTBTR I was pretty confused about multiplying by sqrt(2). My approach was correct until it was multiplied by sqrt(2). Can anyone describe his idea of this problem to me?
You don’t have to multiply your answer with sqrt(2). According to the formula of minimum distance of line from a point, the denominator will always be sqrt(2) .
distance of a line x1+y1+c from a point (x,y) is given by
d = Ax+By+c/ sqrt(A^2+b^2)
Since A and B are both 1or -1 so the denominator will always be sqrta(2)
Soln -Randomly place 8 rooks in every row and make sure conflicts doesnt arise. This can be done using a helper array which marks whether ith,jth column can be used simultaneously in present row.
If this is the intended solution then I really think the time limit is unfair. I had the exact same solution but mine was taking around 6 seconds for n=2\cdot 10^6. Also, n\log^2n for n = 2\cdot 10^6 is around 8.8\cdot 10^8.
Plus the n \log n in that is from NTT/FFT which has a high constant.
Plus there is an additional n \log k for actually calculating the polynomial you want to exponentiate. I even used a faster way to exponentiate ( as discussed here ) but still TLE.
If anyone got AC using NTT/FFT then I’m definitely stealing your code.