1462E2 - Close tuples

#codeforces

Link : https://codeforces.com/problemset/problem/1462/E2

The crux here is to see that we only need to see elements for \(x+k\) where \(x\) is the minimum element in the tuple, and \(x+k\) is the maximum element in the tuple.

So we can leave the notion of the ordered elements inside the array, and keep track of magnitudes.

We can create a map, from the item value to it’s count. So an array like : 1 1 2 2 3 4 5, will create a map:

\[ 1 \rightarrow 2 \] \[ 2 \rightarrow 2 \] \[ 3 \rightarrow 1 \] \[ 4 \rightarrow 1 \] \[ 5 \rightarrow 1 \]

Next, we do a prefix sum. So the map will look like:

\[ 1 \rightarrow 2 \] \[ 2 \rightarrow 4 \] \[ 3 \rightarrow 5 \] \[ 4 \rightarrow 6 \] \[ 5 \rightarrow 7 \]

Here, let’s think we are at the first element 1. And if \(k = 2\), then \(1 + k = 3\), so we see how many elements there are until 3 => 5. This already includes the “1” we are looking at, so we should reduce this by 1, to 4.

Since we have decided that the minimum element will be 1, so we only need to worry about the remaining \(m-1\) elements. So we do a combination here, and say \(^4C_{m-1}\) here. Why? Because all maximum elements until 3 work just fine. Even if we have 2 as the largest element, it still would suffice the condition inside the problem.

Now some details: What about the second 1? So when we calculated the tuples for the first 1, we took the cases when the second one is also taken. So when we are calculating for the 2nd one, we should not take the first one into account.

Therefore, the total elements for calculation would become \(4-1 = 3\), and it’s combinations would be : \(^3C_{m-1}\) - This we need to keep decreasing for all the duplicates.

Note that since we are doing MODs in the end, the combinations can also be simplified by doing MODs. MOD of the denominator of the combination would be done via inverse modulus.

My submission : https://codeforces.com/contest/1462/submission/221887357