Problem: Dynamic Scoring System
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. We maintain four arrays of length $$$k$$$:
- $$$prev_i$$$: Price of $$$i$$$-th gem at the previous time step.
- $$$curr_i$$$: Price of $$$i$$$-th gem at the current time step.
- $$$r_i$$$: 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, 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. (Note: $$$prev_i$$$ takes the previous value of $$$curr_i$$$).
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 at time $$$t$$$ is defined by the following recurrence:
Initial Condition: $$$Score_0$$$ is given for each player.
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
