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:
- Price Update: For a gem $$$i$$$, the value of $$$curr_i$$$ is updated.
- 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:
- 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 [email protected], for further discussions.
- Note that $$$r_i$$$ would keep on changing at (potentially) every time step. And, on every time step, we need to solve the problem.
- 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.
