atcoder_official's blog

AtCoder Beginner Contest 366 Announcement
By atcoder_official, history, 9 days ago, In English

We will hold AtCoder Beginner Contest 366.

We are looking forward to your participation!

  • Vote: I like it
  • +46
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it -14 Vote: I do not like it

Another speed round... Good luck anyways!

→ Reply
»
9 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Hope to solve A-F for me... anyways good luck for everybody!

→ Reply
»
9 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Good luck and have fun!

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can solve ABCD. Good luck for everyone!

→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved ABCD, but failed to solve E.

    I found an easy solution for E: https://atcoder.jp/contests/abc366/submissions/56576520

    → Reply
    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Unfortunately,I only solved ACD.There was a strange mistake in my code so I recieved a WA in B.

      → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, B is a bit troublesome.

        → Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Hardest contest and my worst performance in a while. Failed to solve E and F.

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I felt like giving up after e

→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to solve e

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody "hack" this solution for F:

  1. Sort pairs $$$(A_i, B_i)$$$.

  2. Take the largest $$$X$$$ elements from them. I selected $$$X = min(N, 17)$$$.

  3. Check every possible variants of $$$K$$$ elements from $$$X$$$ elements — the regular $$$O(X * 2^X)$$$.

Accepted submission: 56571044

→ Reply
»
8 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

$$$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)

→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You mean E right? Can you give some hints

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)) ?

→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Expand $$$f_i(f_j(x))$$$ and $$$f_j(f_i(x))$$$ and move the terms over correspondingly.

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hii, I tried doing this but could not get to this result, Can you please elaborate

      → Reply
      • »
        »
        »
        »
        8 days ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Oh yes, I was just doing something silly. Thank you for the explanation.

          → Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This comment has been deleted.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Unable to come up with equation for D, how to do it as uptil 2D could be visualized?

→ Reply