atcoder_official's blog

AtCoder Beginner Contest 366 Announcement
By atcoder_official, history, 4 months ago, In English

We will hold AtCoder Beginner Contest 366.

We are looking forward to your participation!

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

»
4 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Another speed round... Good luck anyways!

→ Reply
»
4 months 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
»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Good luck and have fun!

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months 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
»
4 months 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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I felt like giving up after e

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

    how to solve e

    → Reply
    • »
      »
      »
      4 months 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
»
4 months 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
»
4 months 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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You mean E right? Can you give some hints

    → Reply
    • »
      »
      »
      4 months 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
»
4 months 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
  • »
    »
    4 months 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
    • »
      »
      »
      4 months 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
      • »
        »
        »
        »
        4 months 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
        • »
          »
          »
          »
          »
          4 months 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
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This comment has been deleted.

→ Reply
»
4 months 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