Hello Codeforces community,

I have been battling with an algorithmic problem for quite some time, and I would appreciate any insights on a sub-linear approach.

1. Inputs

There are $$$n$$$ players and $$$k$$$ gems. For each gem $$$i$$$, we maintain:

• $$$curr_i$$$: Price of $$$i$$$-th gem at the current time step.
• $$$r_i$$$: Current rate of appreciation of the $$$i$$$-th gem.
• $$$t_i$$$: Timestamp of the last update of $$$r_i$$$.

At $$$t = 0$$$, each player chooses two gems: index $$$u$$$ (numerator) and index $$$v$$$ (denominator) with fixed quantities $$$q_u$$$ and $$$q_v$$$.

2. Updates

At each time step $$$t \gt 0$$$, at most one of the following occurs:

1. Price Update: For a gem $$$i$$$, the value of $$$curr_i$$$ is updated.
2. Rate Update: For a gem $$$i$$$, $$$r_i$$$ is updated to a new value and $$$t_i$$$ is set to the current time $$$t$$$.

3. Scoring System

The score of a player is calculated based on the historical rate updates of their chosen gems $$$u$$$ and $$$v$$$ from time $$$0$$$ to the current time $$$t$$$.

Let the numerator gem $$$u$$$ have rate updates at times $$$0 = t_{u,0} \lt t_{u,1} \lt t_{u,2} \lt \dots \lt t_{u,m} \le t$$$. Let $$$r_{u,i}$$$ be its rate during the time interval $$$[t_{u,i}, t_{u,i+1})$$$ (where $$$t_{u,m+1} = t$$$). Similarly, let the denominator gem $$$v$$$ have rate updates at times $$$0 = t_{v,0} \lt t_{v,1} \lt t_{v,2} \lt \dots \lt t_{v,p} \le t$$$, with rate $$$s_{v,j}$$$ during the interval $$$[t_{v,j}, t_{v,j+1})$$$ (where $$$t_{v,p+1} = t$$$).

The score of a player at time $$$t$$$ is defined as:

4. Output

Find the indices of all players whose $$$Score_t$$$ is below a given threshold $$$th$$$.

Constraint: The solution must achieve a worst-case time complexity better than $$$\mathcal{O}(n)$$$ per time step.

I would deeply appreciate any help from your end!

Best,
UncarvedBlock ---

Edits:

1. This is a problem which finds applications in collateralized borrowing, primarily in Decentralized Finance. If any of you are interested, please feel free to contact me at (singh.om.mail01@gmail.com), for further discussions.
2. Note that $$$r_i$$$ would keep on changing at (potentially) every time step. And, on every time step, we need to solve the problem.
3. As A_Le_K pointed out, all the indices cannot be printed in a time complexity of less than $$$\mathcal{O}(n)$$$. However, the idea is to store the information in such a data structure, so that we can return a single index, and claim all the indices less than that particular index have a score below the said threshold.