PROBLEM LINK:
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
Given an array A consisting on N integers. Define:
- F(A,i,j)=(A_j-A_i)\cdot (j-i).
- \text{beauty}(S,A) =\sum F(A,i,j) for all valid pairs (i,j) in S.
- V(A) =\max\text{beauty}(S,A) over all valid S.
Given an ordered list of K operations. Each operation swaps two elements in A. Let R be the multiset of all possible arrays obtained when we apply some subsequence of the operations on A. Calculate
EXPLANATION:
It isn’t hard to deduce that
Then, lets define
where R follows from it’s definition in the problem. The answer we are looking for then equals \sum s[i][j]\cdot(j-i). All that remains is to calculate the matrix s efficiently.
The problem at hand is now slightly similar to this problem. It is recommended (but not mandatory!) to solve that problem before coming back to this.
Let dp[i][j][k] equal \sum_{P\in F} \max(0, P_j-P_i) where F is the multiset of all possible arrays obtained when we apply some subsequence of the first k operations on A.
Then, it’s clear that s[i][j]=dp[i][j][K].
The base case dp[i][j][0]=\max(0,A_j-A_i) for all 1\le i,j\le N is trivial to deduce. The transitions are then (op_{k,1} and op_{k,2} refer to the indices of elements swapped in the k^{th} operation) -
- dp[i][op_{k,1}][k] = dp[i][op_{k,1}][k-1]+ dp[i][op_{k,2}][k-1]
- dp[i][op_{k,2}][k] = dp[i][op_{k,2}][k-1]+ dp[i][op_{k,1}][k-1]
- dp[op_{k,1}][i][k] = dp[op_{k,1}][i][k-1]+ dp[op_{k,2}][i][k-1]
- dp[op_{k,2}][i][k] = dp[op_{k,2}][i][k-1]+ dp[op_{k,1}][i][k-1]
for all 1\le i\le N, and
- dp[x][y][k]=2\cdot dp[x][y][k-1]
for all other x,y\notin \{op_{k,1},op_{k,2}\}.
Elaborate please?
We can either apply the k^{th} operation, or ignore it. The second term in the RHS is when we apply the k^{th} operation, and the first is when we ignore it.
In the last transition, swapping elements op_{k,1} and op_{k,2} doesn’t change the value of dp[x][y][k], so dp[x][y][k-1] is added twice.
The time and memory complexity of this approach is O(N^2K) and O(N^2) respectively, too slow to pass for the given constraints.
Luckily, we can optimise! Observe that calculating the first four transitions takes O(NK), so the bottleneck is transition 5.
Instead of explicitly computing dp[x][y][k] in each iteration, we can do it lazily, updating the value only when the value is required.
More precisely, let last[x][y] be the largest valid value such that we explicitly calculated dp[x][y][last[x][y]] in the past. Then, we can rewrite transition 5 as:
which can be computed efficiently using suitable preprocessing! Refer my code linked below for implementation details 
.
TIME COMPLEXITY:
Initialising the DP table takes O(N^2). Computing the DP then takes O(NK). Computing the final answer takes O(N^2), making the total time complexity
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters