# Can't wait for the editorials of ADAROOKS2 and BINARY **URL:** \ **Category:** editorial\ **Tags:** editorial\ **Created:** [May 13, 2019, 8:49am UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460 "2019-05-13T08:49:48Z")\ **Posts on this page:** 20\ **Page:** 3
**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\ **Post date:** [May 13, 2019, 12:56pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/43 "2019-05-13T12:56:23Z")
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](https://discuss.codechef.com/t/pfruit-editorial/19423) ) but still TLE. If anyone got AC using NTT/FFT then I’m definitely stealing your code. 😛 ---
**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\ **Post date:** [May 13, 2019, 1:11pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/44 "2019-05-13T13:11:15Z")
If you like this then you might like [PFRUIT](https://www.codechef.com/JULY18A/problems/PFRUIT) and [SERSUM](https://www.codechef.com/MAY18A/problems/SERSUM). They also use the series expansion of e^x ( although the editorial for SERSUM doesn’t mention that approach. ) ---
**Author:** ![alei](https://discuss.codechef.com/user_avatar/discuss.codechef.com/alei/32/4178_2.png) [@alei](https://discuss.codechef.com/u/alei)\ **Post date:** [May 13, 2019, 1:14pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/45 "2019-05-13T13:14:06Z")
Sketches of solutions in my blog: [CodeChef May Challenge 2019 – aleigorithms](https://aleigorithms.wordpress.com/2019/05/06/codechef-may-challenge-2019/) ---
**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\ **Post date:** [May 13, 2019, 1:15pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/46 "2019-05-13T13:15:03Z")
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. ---
**Author:** ![apptica](https://discuss.codechef.com/user_avatar/discuss.codechef.com/apptica/32/307283_2.png) [@apptica](https://discuss.codechef.com/u/apptica)\ **Post date:** [May 13, 2019, 1:15pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/47 "2019-05-13T13:15:47Z")
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. ---
**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\ **Post date:** [May 13, 2019, 1:26pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/48 "2019-05-13T13:26:30Z")
I just saw that K=1 for the last subtask now 🤦‍♂️. I just assumed that the constraints for the last subtask are the same as the full constraints because I’ve never seen otherwise. 😢 It is technically my fault but the problem statement writers really should’ve mentioned such an important detail elsewhere. ---
**Author:** ![kukreja\_vlk](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kukreja_vlk/32/125882_2.png) [@kukreja\_vlk](https://discuss.codechef.com/u/kukreja_vlk)\ **Post date:** [May 13, 2019, 1:43pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/49 "2019-05-13T13:43:49Z")
I learned about Cayley’s formula and Prüfer sequence, though it wasn’t enough. Waiting for the tut. ---
**Author:** ![vivek\_1998299](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@vivek\_1998299](https://discuss.codechef.com/u/vivek_1998299)\ **Post date:** [May 13, 2019, 1:48pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/50 "2019-05-13T13:48:23Z")
Thanx…glad you liked it 🙂 ---
**Author:** ![shoryaj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shoryaj/32/21_2.png) [@shoryaj](https://discuss.codechef.com/u/shoryaj)\ **Post date:** [May 13, 2019, 2:00pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/51 "2019-05-13T14:00:30Z")
@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? ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [May 13, 2019, 2:18pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/52 "2019-05-13T14:18:50Z")
Arre bidu, ye long challenge toh apann ne 4 ghante mai niptaaya tha vo bhi akhri din mai. Chill rehneka apun ke jaise ---
**Author:** ![alei](https://discuss.codechef.com/user_avatar/discuss.codechef.com/alei/32/4178_2.png) [@alei](https://discuss.codechef.com/u/alei)\ **Post date:** [May 13, 2019, 2:31pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/53 "2019-05-13T14:31:53Z")
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. ---
**Author:** ![shoryaj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shoryaj/32/21_2.png) [@shoryaj](https://discuss.codechef.com/u/shoryaj)\ **Post date:** [May 13, 2019, 2:33pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/54 "2019-05-13T14:33:57Z")
I am so sorry. I omitted the word BINARY 😛 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. ---
**Author:** ![alei](https://discuss.codechef.com/user_avatar/discuss.codechef.com/alei/32/4178_2.png) [@alei](https://discuss.codechef.com/u/alei)\ **Post date:** [May 13, 2019, 2:41pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/55 "2019-05-13T14:41:40Z")
wow, finite projectives. How many rooks can you place? ---
**Author:** ![shoryaj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shoryaj/32/21_2.png) [@shoryaj](https://discuss.codechef.com/u/shoryaj)\ **Post date:** [May 13, 2019, 2:48pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/56 "2019-05-13T14:48:11Z")
@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? ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [May 13, 2019, 3:05pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/57 "2019-05-13T15:05:47Z")
I had a very amazing solution for Adarooks. I can place upto 10 rooks… 🙂 in each row. ---
**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\ **Post date:** [May 13, 2019, 3:06pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/58 "2019-05-13T15:06:24Z")
Your solution looks very interesting. Could you explain it in a lot more detail? I looked through [your code](https://www.codechef.com/viewsolution/24233410) and I understand what it does but why does it work? ---
**Author:** ![alei](https://discuss.codechef.com/user_avatar/discuss.codechef.com/alei/32/4178_2.png) [@alei](https://discuss.codechef.com/u/alei)\ **Post date:** [May 13, 2019, 3:10pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/60 "2019-05-13T15:10:33Z")
yes, linear. I’ll add author approach to my blog ---
**Author:** ![shoryaj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shoryaj/32/21_2.png) [@shoryaj](https://discuss.codechef.com/u/shoryaj)\ **Post date:** [May 13, 2019, 3:16pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/62 "2019-05-13T15:16:22Z")
@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. ---
**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\ **Post date:** [May 13, 2019, 3:17pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/63 "2019-05-13T15:17:25Z")
Yeah I missed that K=1 for the final subtask and @apptica already pointed that out to me. ---
**Author:** ![shoryaj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shoryaj/32/21_2.png) [@shoryaj](https://discuss.codechef.com/u/shoryaj)\ **Post date:** [May 13, 2019, 3:20pm UTC](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460/64 "2019-05-13T15:20:18Z")
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. [Previous page](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460.md?page=2) [Next page](https://discuss.codechef.com/t/cant-wait-for-the-editorials-of-adarooks2-and-binary/25460.md?page=4)