Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

UncarvedBlock's blog

Is there a sub-linear approach for this dynamic scoring problem?
By UncarvedBlock, history, 8 months ago, In English

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:

$$$ Score_t = \frac{curr_u \cdot q_u \cdot \prod_{i=0}^{m} \big(1 + r_{u,i} \cdot (t_{u,i+1} - t_{u,i})\big)}{curr_v \cdot q_v \cdot \exp\left(\sum_{j=0}^{p} s_{v,j} \cdot (t_{v,j+1} - t_{v,j})\right)} $$$

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 [email protected], 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.
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    8 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +1 Vote: I do not like it

    0) Source of problem

    1) Why is there an exponent in numerator, but not denominator?

    2)

    Output Find the indices of all players whose Score is below a given threshold

    Size of output indices could be $$$#players == n$$$ (all players below threshold) which is $$$O(n)$$$ already.

    3) Is the size of input arrays $$$r_{u,i}$$$ and $$$t_{u,i}$$$ $$$O(k*m)$$$? If so and no additional constraints — I don't see dependancy between gems and no monotonicity for growth/decline for both numerator/denominator for each gem/player?

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

      Thanks for your comments A_Le_K. Here are the clarifications:

      0.This problem is a fundamental problem from collateralised debt handling. To give you some context: On lending platforms, people typically deposit a collateral, to get some debt against it. Usually, the collateral is a safer asset, and debt is a taken for a risky asset. (More details in the next clarification.)

      1.In finance, there is a certain rate associated with 'each asset', which keeps on changing according to the prevailing demand and supply. The lending platforms make money by growing the collateral asset's value linearly at the rate associated with collateral, and the debt value exponentially at the rate associated with the debt (hence the exponent in denominator and none in the numerator).

      I tried my best to create the Problem Statement so that it appeals to everyone. But, to give you how everything is related to the real world:

      $$$u$$$: Collateral Asset.

      $$$v$$$: Debt Asset.

      $$$r_{u, j}$$$: Rate at which collateral grows linearly, until a new rate is updated.

      $$$s_{v, j}$$$: Rate at which debt grows exponentially, until a new rate is updated.

      I hope that clarifies the formula I have written in the post. $$$curr$$$: Simply the current price of the collateral and debt, to get its value in $ (let's say).

      2.Yes. That's an oversight. I will edit the post shortly. But the idea is that we want to rearrange the players in such a data structure, that at any given timestamp, we know the index upto which all the players have their scores lesser than the threshold. For example: maybe we store them in a sorted data structure by their scores, so that we can directly figure out 'upto what index' are players whose scores are below a threshold present.

      3.Yes. But I think you have misinterpreted slightly. It is along these lines: There are m rate updates for the collateral asset (numerator), and each of these rates are valid only until the next rate update. Once the new rate update takes place, we add a new linear term for the collateral, and so on. There are p rate updates for the debt asset (denominator), and compounding happens exponentially. Again, each update is valid only until the next rate update. Finally, m and p aren't known beforehand. The only event we know of is the rate updates (out of which m will simply be the number of times collateral assets' index rate changed, and so on).

      I will modify the post shortly, and try to make things more clear. Please feel free to ask me any required clarifications, and thanks a lot for your time!

      → Reply