induk_v_tsiane's blog

Kth maximum from a set of linear functions.
By induk_v_tsiane, history, 14 months ago, translation, In English

Hi, Codeforces.

Recently I have been thinking about the following task:

You are given $$$N$$$ lines of form $$$f_i(x) = a_i * x + b_i$$$ and $$$Q$$$ queries of form $$$x_j, k_j$$$ — if we sort all of the values of lines in point $$$x_j$$$, which line would be on the $$$k_j$$$-th spot? The queries are offline. I will use $$$K$$$ — the maximum out of all $$$k_j$$$.

I thought about this and developed some methods:

The first one runs in $$$O(sqrt(N)logN + KlogKsqrt(N)$$$ pre query and is online. We use sqrt-decomposition, build CHT on every block, for each query we do the following: run over the blocks, get $$$K$$$ minimums and the blocks where they occurred. Now we know that the needed minimum lies inside one of this blocks, we can now iterate over $$$K * sqrt(N)$$$ blocks, maintaining the $$$K$$$ smallest values with a set.

The second one runs in $$$O(NKlogNlogMAX)$$$ total: for each position from $$$i$$$ to $$$K$$$, we do the following: process the queries left to right, get the current minimum with its index. On the next walkthrough, we will use D&C to delete that line before this query using Li-Chao tree, and then add it back.

The third one runs in $$$O(N^2logN + QlogQ)$$$. We generate all $$$O(N^2)$$$ points of intersection, sort them together with the requests, then simply swap the two lines which intersect.

So, all of these are kinda not good enough(((. If anyone can share any ideas, I will be extremely grateful.

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

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

Auto comment: topic has been translated by induk_v_tsiane (original revision, translated revision, compare)

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

What are the constraints on K?

I've seen a code written by SSRS_ which answers these queries offline using what he calls $$$Kth$$$ $$$Li$$$ $$$Chao$$$ $$$Tree$$$.

You can check his code here: https://mirror.codeforces.com/contest/1866/submission/221707573

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

    It is not a task, just something I was thinking of. Anything polynomial is good.

    SSRS_, could you help with understanding?

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

For the special case when $$$K = 2$$$ you can split the functions randomly into two groups. The probability that the first and the second maximum will be in the same group is about 1/2. Do this 20 times and build 2 Li Chao trees (one for each group) for each iteration. Now, for the query, just go through the 20 iterations, and take the biggest element from the half which gives the lower maximum.

Not too useful for the general problem, but wanted to share it because I thought it was neat. Saw it in one IATI/Shumen task a few years ago (I think P5 from 2019).

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

    This case was just recently in 1866K - Keen Tree Calculation

    In my personal way of dodging cht/li-chao and inventing it every time during contest, I came up with two sets solution:

    Lets sort functions by $$$a_i$$$ and maintain only subset of items with descending $$$b_i$$$. With increasing $$$x$$$ some items will consume right neighbor. Every time last item in such set is maximum for current $$$x$$$.

    To find second maximum we can send all removed items to second layer with same rules.

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

By means of "good enough", I think if $$$K$$$ does not have a clear bound, then the third solution is optimal. In fact it is equivalent to the time complexity of a kinetic sorted list. If $$$K$$$ is bounded, then while I did not prove this, I think $$$O(NK \log K+N\log^2N+Q\log Q)$$$ should be possible. Consider maintaining a kinetic sorted set AND a kinetic heap at the same time. There can be only $$$O(NK)$$$ intersections between the $$$K$$$ largest elements, so we consider the $$$K$$$ largest elements and the rest separately. For the $$$K$$$ largest elements, we use a sorted list. For the rest, we use a kinetic heap. The kinetic sorted list must deal with $$$O(NK)$$$ events, and each event needs $$$O(\log K)$$$ time. The kinetic heap must deal with $$$O(N \log N)$$$ events, and each event needs $$$O(\log N)$$$ time. Therefore the total time complexity should be $$$O(NK \log K + N \log^2 N)$$$, and $$$O(Q \log Q)$$$ for sorting the queries.

EDIT: nevermind the previous edit, that was likely not true

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

A k-level algorithm might help?

Besides, can you elaborate more on your first algorithm? For example, why there will be $$$K\sqrt{N}$$$ blocks?

→ Reply
»
14 months ago, # |
  Vote: I like it +23 Vote: I do not like it

You can use the fact that queries are offline. Build a kinetic segment tree over the lines, and for each query point $$$x_j$$$ remove $$$k_j - 1$$$ lines with smallest value, query, then add those lines again. This is probably something $$$O(n \log^2 n + q K \log n)$$$. Maybe there is some fancy research papers that only has $$$\sqrt K$$$ dependency, but I think it's hard to completely get rid of them.

I have a post about kinetic segment tree but unfortunately it is in Korean.

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

    Hi, thank you!

    There seems to be an online solution in O(KlogNlogK), which uses a Li-Chao tree, but maintains K smallest elements at each point.

    However, thank you for the answer!

    → Reply