We will hold AtCoder Beginner Contest 366.
- Contest URL: https://atcoder.jp/contests/abc366
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240810T2100&p1=248
- Duration: 100 minutes
- Writer: MtSaka, sotanishy
- Tester: Nyaan, math957963
- Rated range: ~ 1999
- The point values: 100-200-300-400-475-500-600
We are looking forward to your participation!
Another speed round... Good luck anyways!
Hope to solve A-F for me... anyways good luck for everybody!
Good luck and have fun!
I hope I can solve ABCD. Good luck for everyone!
I solved ABCD, but failed to solve E.
I found an easy solution for E: https://atcoder.jp/contests/abc366/submissions/56576520
Unfortunately,I only solved ACD.There was a strange mistake in my code so I recieved a WA in B.
Yes, B is a bit troublesome.
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
Hardest contest and my worst performance in a while. Failed to solve E and F.
I felt like giving up after e
how to solve e
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.
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
21,2 1,50 2,1 2,2 . . 2,20
$$$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)
You mean E right? Can you give some hints
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.
finally a linear approach.
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)) ?
Expand $$$f_i(f_j(x))$$$ and $$$f_j(f_i(x))$$$ and move the terms over correspondingly.
Hii, I tried doing this but could not get to this result, Can you please elaborate
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
Oh yes, I was just doing something silly. Thank you for the explanation.
This comment has been deleted.
Unable to come up with equation for D, how to do it as uptil 2D could be visualized?