### 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[][].