# CARLOS - Editorial

Author: Jakub Safin
Tester: Sergey Kulik

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.

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 = -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:

1. If a[i] >= setValue[i – 1], then setValue[i] = a[i] and call i+1th character with the same cost.
2. 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);
}
}
``````

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.

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] = DP[i].
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[][].

### AUTHOR’S AND TESTER’S SOLUTIONS:

7 Likes

Nice Question 2 Likes

How did my solution for this http://www.codechef.com/viewsolution/6713353 didn’t pass? It’s also O(N * M). Am I wrongly interpreting the complexity?

i was not able to think about fast solution to this problem.

can someone suggest me how i can improve my thinking towards such problem.

is it something i can read and get insight of , like some concepts . or is it just my thinking is not upto the level and i need more practice.?

It may be something in Java, I only know a code that’s syntactically equivalent to one in C++ can be as much as 10x slower in Java.

I’m not very sure about complexity in Java. BTW test 2 of subtask 3 only had maxtests, I think.

1 Like

In case you wonder where the name CARLOS came from:

What does a programmer usually expect when seeing the term “inversion”? Situations with i < j and A[i] > A[j]. Well surprise, it’s something completely different (and pretty much unrelated to the solution). And the usual meme associated with puns (jokes based on wordplay) is See more on Know Your Meme.

4 Likes

Learn dynamic programming, I guess. It’s a concept that’s fairly specific to programming (computing more stuff and utilising it efficiently).

1 Like

Sir can u please suggest some good links/resources of dynamic programming tutorials and/or examples!

2 Likes

thank you You have written - “Else DP[i][j] = DP[i][j – 1]”.
But it should be “Else DP[i][j] = DP[i - 1][j]”.

Correction being (i-1) rather than (j-1). No?

The problem is quite hard. What is the thought process of you guys? Learning dp makes you think this way ?? Can any of you please provide us (the bad programmers) with the kind of idea that occurred when you solved the problem ?

2 Likes

observing that dp[i][j] only depends on ith and (i-1)th row, we can reduce states (which indirectly helps reduce time too)

@xellos0 Ur reasoning for choosing the problem name is even better than the problem itself! Impressive!!! http://www.codechef.com/viewsolution/6708360

Hi @xellos0 can you provide any tricky test case?

I think the time limit was too tight… Also my O(n*m) solution in c++ didn’t pass…

http://www.codechef.com/viewsolution/6724066

When xellos creates a problem, it must include a meme! I was waiting for this 1 Like

i thought till recursion but didnt got the dp equation but its sure once there is a exponential complexity algo then there is either a dp optimisation or divide and conquer .
How u all thing dp equation I mean the procedure…
i have studied lot of standard dp problems but still cannot implement if the questions is not related to the standard question how to improve thinking… plz help… i suffer in every competition… plz any guidance…

The same solution of mine didn’t pass with O(N*M) complexity it is too tight without any need ,there must be some space for one or more iteration . only second subtask of 3rd task is failing.@Author can you please explain is it some optimization pending from Algorithms or its just tight limits
http://www.codechef.com/viewsolution/6768831

My solution takes 0.86 seconds on that test and I didn’t even try to optimise it. It wasn’t too small, definitely not for DP and a long contest.

It contains maxtests; btw my solution takes 0.86s on that test. The time limit isn’t too tight.