Can't wait for the editorials of ADAROOKS2 and BINARY

editorial
21

Thanks @shivamchef

I will also explore and learn from it.

22

It seems not, It is the error i also faced the same and then corrected it.

23

ur welcome :slight_smile: .

24

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".

Thanks @vasco_lorde for clarifying the problem.

1 Like
25

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.

26

oh i cant beilive this i was so close . :persevere:

27

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.

28

ADAROOKS2 basically breaks down to “find a row of rooks where no two pairs of rooks have the same distance from each other”.

Then print this line n times where each line is shifted by a different offset and padded by dots to get the correct width.

One valid solution is where each line is shifted by its own line number:
O…O…O…O.OO…O…O…O…O…
.O…O…O…O.OO…O…O…O…O.
…O…O…O…O.OO…O…O…O…O

(ideally start with offset +48 or so and just add one for each line)

edit: the forum won’t let me post too many dots and the output is fcked up.
it looks like this: screenshot

2 Likes
29

Hi, I dont know if it helps, but see if you can understand my approach(I dont think I have explained that well),

https://pastebin.com/raw/EX76ZX2g

30

Thank you! I was looking at a different generating function:

f(x_1, \ldots, x_n) = (x_1 + \ldots + x_n)^{n - 2} = \sum_Tx_1^{d_1 - 1} \ldots x_n^{d_n - 1}

which is harder to manipulate. Your approach is great!

31

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?

32

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)

1 Like
33

:frowning: I missed this… I calculated this exactly. But I didn’t consider that a^2+b^2 is going to be always sqrt(2). :smile: LOL.

1 Like
34

I didnt tried Binary. And I hate Adaroks2. :stuck_out_tongue:

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.

1 Like
35

For ADAROKS2, you can use idea similar to this A005282 - OEIS

2 Likes
36

You missed a big deal :smile:

37

Thank you for this :heart:

38

you left these two then which one u solved???

39

ADAPWN and TREDEG. :stuck_out_tongue_winking_eye:

I’m in Div1. So Binary is zero score for me. I tried Adaroks on 3rd and 4th last day. I solved Adaroks after ~50 submissions on 3rd last day.

1 Like
40

Rotate the points so that you don’t have to worry about the square roots at all.

2 Likes