### atcoder_official's blog

By atcoder_official, history, 5 weeks ago,

We will hold AtCoder Beginner Contest 366.

We are looking forward to your participation!

• +49

 » 5 weeks ago, # |   -14 Another speed round... Good luck anyways!
 » 5 weeks ago, # |   +13 Hope to solve A-F for me... anyways good luck for everybody!
 » 5 weeks ago, # |   +10 Good luck and have fun!
 » 5 weeks ago, # |   0 I hope I can solve ABCD. Good luck for everyone!
•  » » 5 weeks ago, # ^ |   0 I solved ABCD, but failed to solve E.I found an easy solution for E: https://atcoder.jp/contests/abc366/submissions/56576520
•  » » » 5 weeks ago, # ^ |   0 Unfortunately,I only solved ACD.There was a strange mistake in my code so I recieved a WA in B.
•  » » » » 4 weeks ago, # ^ |   0 Yes, B is a bit troublesome.
 » 5 weeks ago, # | ← Rev. 2 →   +3 Disclaimer: contest has ended.What is the intended time complexity for F? $O(N\log N+NM)$ TLEs for F, but isn't $NM$ at most $2\times10^6$?Edit: The intended time complexity for F is $O(N\log N+NM)$, but why does this not pass? Thanks
 » 5 weeks ago, # |   +3 Hardest contest and my worst performance in a while. Failed to solve E and F.
 » 5 weeks ago, # |   0 I felt like giving up after e
•  » » 5 weeks ago, # ^ |   0 how to solve e
•  » » » 5 weeks ago, # ^ |   0 Think it like this. We want to find center of N points on grid. How to find center of the N points on grid ? ( please find leet code question for the same, I remember solving one question on leet code , Keep in mind , there can be multiple center's of N points )To find the center sort all the 'x' cordinates, and sort all the 'y' coordinates and then find median of each one of them. Now, from center we can move some points to left, and some points to right. for that I had used binary search, I found few linear solution as well. I couldn't do it in linear time.
 » 5 weeks ago, # |   0 Can anybody "hack" this solution for F: Sort pairs $(A_i, B_i)$. Take the largest $X$ elements from them. I selected $X = min(N, 17)$. Check every possible variants of $K$ elements from $X$ elements — the regular $O(X * 2^X)$. Accepted submission: 56571044
•  » » 5 weeks ago, # ^ |   0 21,2 1,50 2,1 2,2 . . 2,20
 » 5 weeks ago, # | ← Rev. 3 →   0 $O(N + M + D)$ amortized solution for E (well I also use sorting to find median of $y$-coordinates, but that's it, you could use k-th order statistic or median of medians if you really want)
•  » » 5 weeks ago, # ^ |   0 You mean E right? Can you give some hints
•  » » » 5 weeks ago, # ^ |   0 One of the steps is similar to Japanese video editorial: if you fix coordinate $X_i$ you just need to find the interval $[Y_l, Y_h]$ in which points will not have sum of distances greater than $D$.For a fixed $X_i$ you can find sum of differences of $X$ coordinates in $O(1)$ with prefix sums.Now, all good points will lie in some kind of a "diamond" shape, and as you go over all $X$ coordinates from left to right this interval $[Y_l, Y_h]$ will first be increasing, then decreasing (or it could also be empty all the time).For any coordinate $X$ the best point is median of $Y$ coordinates, because it minimizes the difference for all $Y_i$. At this point you could just binary search both $Y_l$ and $Y_h$ up to this median value.However, since interval $[Y_l, Y_h]$ is first increasing, then decreasing, you can just do kind of a two-pointer approach, in total you will move both low and high pointers at most $3 \cdot (M + D)$ times.
•  » » » » 5 weeks ago, # ^ |   0 finally a linear approach.
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone please help me how did we reach the conclusion in problem F : If (Ai — 1)/Bi > (Aj — 1)/Bj, then fi(fj(x)) > fj(fi(x)) ?
•  » » 5 weeks ago, # ^ |   0 Expand $f_i(f_j(x))$ and $f_j(f_i(x))$ and move the terms over correspondingly.
•  » » » 5 weeks ago, # ^ |   0 Hii, I tried doing this but could not get to this result, Can you please elaborate
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Something like this$f_i(f_j(x)) > f_j(f_i(x))$ $a_i (a_jx + b_j) + b_i > a_j (a_ix + b_i) + b_j$ $a_ia_jx + a_ib_j + b_i > a_ja_ix + a_jb_i + b_j$ $a_ib_j + b_i > a_jb_i + b_j$ $a_ib_j - b_j > a_jb_i - b_i$ $b_j(a_i - 1) > b_i(a_j - 1)$ $\frac{a_i-1}{b_i} > \frac{a_j-1}{b_j}$Hope it helps
•  » » » » » 5 weeks ago, # ^ |   +1 Oh yes, I was just doing something silly. Thank you for the explanation.
 » 5 weeks ago, # | ← Rev. 2 →   0 This comment has been deleted.
 » 4 weeks ago, # |   0 Unable to come up with equation for D, how to do it as uptil 2D could be visualized?