1684D - Traps

#codeforces

Question link : https://codeforces.com/problemset/problem/1684/D

Crux

Let’s say we instantaneously get a damage of \(n - i\) when some trap is skipped (instead of addition to the damage done by the traps after this trap as bonus).

But this has an issue right? Let’s say we skip a trap, add \(n-i\) and later we skip another trap. In that case, this trap didn’t give the additional bonus damage, so the current skipped trap’s damage will decrease to \(n-i-1\). So how are we dealing with that?

We are not. So let’s say we skip \(k\) traps. For the first trap skipped, we instantaneously added a damage of \(n-i\) (where \(i\) is the position of the skipped trap). Since there are \(k-1\) traps after this one, it means that we would actually have a damage of \(n - i - (k - 1)\). But we are taking \(n-i\). So we have \(k-1\) more damage here. Similarly, for the second trap \(n - i_{2}\) would be considered, which is \(k-2\) more than intended.

If we continue in this manner, we would have : \(k - 1 + k - 2 + ... + 1 = \frac{k \times (k - 1)} {2}\) more damage, than the actual value.

Let’s say we are comparing different permutations of traps to be skipped. If we just consider \(n-i\) values instead of \(n - 1 - (k - j)\) values (where \(k - j\) is the number of traps after the current traps), then in all cases, the sum would be \(k \times (k - 1) / 2\) more than the actual value.

So we can just depend upon the \(n - i\) increase in damage, and a decrease in damage by \(a_{i}\) (because the trap is being skipped).

So we create another array : \(b_i = a_i - (n - i)\), which points to the reduction in damage because of skipping the \(i^{th}\) trap. We sort this, and find k largest values.

Then we reduce the sum of these from the total sum. Then we also remove \(k \times (k - 1) / 2\) from the total, and that is the answer we are looking for.