Блог пользователя atcoder_official

Автор atcoder_official, история, 3 месяца назад, По-английски

We will hold AtCoder Beginner Contest 366.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Another speed round... Good luck anyways!

»
3 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Good luck and have fun!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
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

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I felt like giving up after e

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how to solve e

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
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)

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You mean E right? Can you give some hints

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 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.

»
3 месяца назад, # |
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)) ?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

This comment has been deleted.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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