KiloBoom#519

KiloBoom (Editorial)

Subtask solution:

  • Since c=0, then at any point of the game experience income equals 0 \cdot l + k = k, and hence is constant. This doesn't change with level-ups and magnet usage, hence one can just activate one magnet exactly after the -th second and collect t \cdot k experience. Thus outputting t \cdot k is sufficient.

Subtask solution:

  • Claim that will be used later in the solution as well: last magnet used must always be used after the -th second.

  • Proof: suppose last magnet was used after -th (n < t) second. Then, by using it t-n seconds later, one could collect at least (t-n) \cdot k experience more.

  • From follows that if m=1, answer is t \cdot k, and if m = 2, one can brute force the time of usage of the first magnet in and use some math to calculate the answer.

Subtask solution:

  • Expanding subtask solution, for m=3, one can still bruteforce the time of usage of the first two magnets, but being able to calculate the level given the amount of experience (i.e. \lfloor \log_2(x) \rfloor) in constant time is needed. One can use C++ built-in function \text{__builtin_clzll()}

Subtask solution:

  • We will use dynamic programming to solve this subtask. Define to be the maximum amount of experience possible to collect after using magnets during first seconds, and lv[i][j] = \lfloor \log_2(dp[i][j]) \rfloor.

  • The transition will be the following: dp[i][j] = \max_{p < j}\Big(dp[i-1][p] + (lv[i-1][p] \cdot c + k) \cdot (j - p) \Big), which can be calculated in time for each .

  • Thus the total complexity of this solution is O(t^2 m) which works with t \le 100.

Full solution:

  • We will expand the approach from subtask :

  • Key claim is: at any point of the game, level of the player is .

  • Proof: Suppose that at some moment , the level becomes at least . That means that 2^{40} \le (40 \cdot c + k) \cdot n. Substituing c = k = 10^5, n \le t = 2 \cdot 10^4 we get 2^{40} \le (40 \cdot 10^5 + 10^5) \cdot 2 \cdot 10^4 = 82 \cdot 10^9 which is not true.

  • Another trivial, but useful observation is dp[i][j] \le dp[i][j+1] from which follows lv[i][j] \le lv[i][j+1].

  • Therefore, on a layer of dp, indices with same level form contiguous segments.