PROBLEM LINK:
Author: Jakub Safin
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DP, Prefix minimum
PROBLEM:
Given is an array where each element belongs to an alphabet of numbers from 1 to N. It is allowed to transform some numbers to others. You need to make the array sorted by changing the minimum number of characters.
EXPLANATION:
Given the available transformations, we can find out all possible transformations using DFS or BFS or Floyd-Warshall treating each character as a vertex and available transformations as edges. A character corresponding to a vertex can be transformed to another character corresponding to another vertex if and only if it can be reached by travelling through one or more edges.
Sub-task 1:
We can solve this subtask with simple recursion. While applying recursion, let’s maintain an array setValue[1…N] which maintains the current set values of all the characters at any respective time.
We assume setValue[0] = -1, so that setValue[i] >= setValue[i – 1] argument is valid for all i from 1 to N.
We call each character starting from the left with one argument: Cost till this character, i.e number of indices i where a[i] != setValue[i].
When we are at some character, we have two choices:
- If a[i] >= setValue[i – 1], then setValue[i] = a[i] and call i+1th character with the same cost.
- Set setValue[i] to the least possible character that a[i] can be transformed to and call i+1th character with cost equal to current cost + 1.
Psuedo Code:
Let b[i][j] store the least value greater than j that i can be transformed to.
Recurse(int i, int cost){
If(i == n + 1){
ans = min(ans, cost);
return;
}
If(a[i] >= setValue[i – 1]){
setValue[i] = a[i];
Recurse(i + 1, cost);
}
If(b[i][setValue[i – 1] != -1){
setValue[i] = b[i][setValue[i – 1];
Recurse(i + 1, cost + 1);
}
}
Subtask 2:
We maintain a 2-D DP array where DP[i][j] stores the minimum number of changes needed to make the subarray from 1 to i sorted and the last element, i.e a[i], is transformed to j.
We can use the following recurrence relation:
If a[i] can be changed to j, then
DP[i][j] = min(DP[i - 1][ k] + 1) for all k <= j. (If a[i ] == j, then we can omit the +1 inside the minimum function.)
Else
DP[i][j] = DP[i][j – 1]
The complexity is O(N * M * M) per each test case, because there are N * M dp values to be calculated and each calculation needs O(M) time on average for checking DP[i-1][ k] for all k <= j.
Subtask – 3
The solution of subtask 2 can be improved - rather than checking DP[i - 1][ k] for all k <= j, we can maintain another dp array PM[1…N][1…M], where PM[i][j] stores minimum cost for making the subarray till the i’th element of the given array sorted such that a[i] <= j.
The values of array PM can be calculated as:
PM[i][1] = DP[i][1].
PM[i][j] = min(DP[i][j], PM[i][j - 1]) for j > 1.
The complexity is O(N * M) per each test case, because there are N * M dp values to be calculated for both arrays DP[][] and PM[][].
…