Can't wait for the editorials of ADAROOKS2 and BINARY

editorial
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
41

Really nice approach. That part where you generated the required expression using expansion of e^x was really a new thing to learn ! :slight_smile:

42

ADAROOKS2 is easy, if you find the pattern :slight_smile:

43

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. :stuck_out_tongue:

44

If you like this then you might like PFRUIT and SERSUM. They also use the series expansion of e^x ( although the editorial for SERSUM doesn’t mention that approach. )

45

Sketches of solutions in my blog: CodeChef May Challenge 2019 – aleigorithms

3 Likes
46

I had the exact same solution but this just seemed like a random thing that worked. I would like to see a provably largest solution/bound for this.

47

I got AC using NTT. Since K = 1 for larger test cases, so you can actually calculated e^(nx) directly, no need to do exponentiation of the polynomial as the power series of e^x was similar to the generating function.

48

I just saw that K=1 for the last subtask now :man_facepalming:.

I just assumed that the constraints for the last subtask are the same as the full constraints because I’ve never seen otherwise. :cry:

It is technically my fault but the problem statement writers really should’ve mentioned such an important detail elsewhere.

1 Like
49

I learned about Cayley’s formula and Prüfer sequence, though it wasn’t enough. Waiting for the tut.

50

Thanx…glad you liked it :slight_smile:

51

@alei what was the time complexity of the solution expected by the setter, considering your post mentions you expected a lot of WAs for it?

52

Arre bidu, ye long challenge toh apann ne 4 ghante mai niptaaya tha vo bhi akhri din mai. Chill rehneka apun ke jaise

1 Like
53

for which problem? I didn’t expected too many WAs in ADAROOKS2 because its easy to check the conditions before submiting. I don’t know why BINARY got few ACs, I saw a similar problem in SnackDown last year, I was expecting it to be problem 3 or 4 in div2.

54

I am so sorry. I omitted the word BINARY :stuck_out_tongue:
I tried a lot of solutions for this problem, and my last one was of linear time. Still I got TLE on 2 test cases. Hence the question.

ADAROOKS personally was easy for me, primarily because I used the concept of finite projective planes.

55

wow, finite projectives. How many rooks can you place?

56

@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 :stuck_out_tongue:
What was the time complexity expected for BINARY?

1 Like
57

I had a very amazing solution for Adarooks. I can place upto 10 rooks… :slight_smile: in each row.