CARLOS - Editorial

PROBLEM LINK:

Practice
Contest

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:

  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);
    }
}

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

AUTHORā€™S AND TESTERā€™S SOLUTIONS:

Authorā€™s solution
Testerā€™s solution

7 Likes

Nice Question :slight_smile:

2 Likes

How did my solution for this CodeChef: Practical coding for everyone 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.?

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

alt text

See more on Know Your Meme.

4 Likes

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

2 Likes

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

@xellos0 Ur reasoning for choosing the problem name is even better than the problem itself! Impressive!!! :slight_smile:

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

Hi @xellos0 can you provide any tricky test case?

i thought till recursion but didnt got the dp equation :frowning: ā€¦
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

what is the problem with my solution.
I just got 78 points and my complexity is O(n*m);

My code : in C

#include <stdio.h>
int t, m, n, k, a , b,j ,l,i;
long long dp[200001][201];
long long min[200001][201];
int x[200000];
int parent[201], rank[201];
int connect[201][201];
int fin[201];
int find(int x)
{
if(parent[x]!=x)
parent[x] = find(parent[x]);
return parent[x];
}
void Union(int x, int y)
{
int xRoot = find(x);
int yRoot = find(y);
if(xRoot == yRoot)
return;
if(rank[xRoot]<rank[yRoot]){
parent[xRoot] = yRoot;
}
else if(rank[yRoot]<rank[xRoot]){
parent[yRoot] = xRoot;
}
else{
parent[yRoot] = xRoot;
rank[xRoot] = rank[xRoot] + 1;
}
}
int main() {
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%d %d %d",&m,&k,&n);
for(j = 0; j < m; j++){
parent[j] = j;
rank[j] = 0;
}
for(j=0;j<k;j++){
scanf("%d %d",&a,&b);
Union(a-1,b-1);
}
for(j=1;j<=m;j++){
fin[j] = find(j-1);
}
for(j=1;j<=m;j++){
for(l=1;l<=m;l++){
if(fin[j]==fin[l])
connect[j][l] = 1;
else
connect[j][l] = 0;
}
}
for(j=0;j<n;j++){
scanf("%d",&x[j]);
}
for(j=1;j<=m;j++){
if(x[0]!=j){
if(connect[x[0]][j]==1)
dp[1][j] = 1;
else
dp[1][j] = 1000000;
}
else
dp[1][j] = 0;
if(j>1){
if(dp[1][j]<min[1][j-1])
min[1][j] = dp[1][j];
else
min[1][j] = min[1][j-1];
}
else
min[1][1] = dp[1][1];
}
for( j=2;j<=n;j++){
for(l=1;l<=m;l++){
if(x[j-1]!=l){
if(connect[x[j-1]][l]==1)
dp[j][l] = min[j-1][l] + 1;
else
dp[j][l] = 1000000;
}
else
dp[j][l] = min[j-1][l];
if(l>1){
if(dp[j][l]<min[j][l-1])
min[j][l] = dp[j][l];
else
min[j][l] = min[j][l-1];
}
else
min[j][1] = dp[j][1];
}
}
if(min[n][m]>=1000000)
printf("-1\n");
else
printf("%lld\n",min[n][m]);
}
return 0;
}

I used a very different approach and got AC in 0.72 seconds. My time complexity is probably O(m+k+n*log(n)) (Iā€™m not sure, Iā€™m a newbie).

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

I first found out all the connected components in the graph of letters using DFS. I numbered them and made a lookup table which mapped each node to its connected component number. Also, for each connected component I stored a list of all nodes in that connected component.

For eg.
If the edges are
1 2
1 4
3 6
5 6
Then, the connected components will be
G1{1,2,4} and G2{3,5,6}
And the lookup table will be [1,1,2,1,2,2]

Then in the given word, I checked which connected component that letter lies in. When we transform it, it can only change to one of the letters of that connected component. I found out what are the min and max values which that elem can take after transformation (by finding the smallest and largest elem in the list of nodes in that connected component).

So if the word is [1, 2, 5, 4, 3, 6], it can be seen as
[1-G1(1,4), 2-G1(1,4), 5-G2(3,6), 4-G1(1,4), 3-G2(3,6), 6-G2(3,6)]

For the array to be sorted, the min value which a[i] can take should be more that the min value a[i+1] can take. So, I moved from left to right in the array and updated the min values of all elems in this way. Similarly I moved from right to left and updated the max values of all elems in the array.

So the array will now become
[1-G1(1,2), 2-G1(1,2), 5-G2(3,3), 4-G1(4,4), 3-G2(5,6), 6-G2(5,6)]

Now the original number in the array will either fall between min and max value for that element, or it wonā€™t. For eg, the first element 1 will fall in the range [1,2] but the third element 5 wonā€™t fall in the range [3,3]. So if it doesnā€™t lie in this range, it definitely needs to be transformed to another number which belongs to this range. So, 5 will be transformed to 3. Similarly, the 5th element 3 will be transformed to either 5 or 6.

But we canā€™t say anything about the number which is already in this range. If we change the first elem from 1 to 2, then [2,2,3,4,5,6] will be a possible solution. If we donā€™t, then [1,2,3,4,5,6] will be a possible solution. Let us call all numbers which lie in their min-max range ā€˜liersā€™.

To minimize the number of transformations, we must maximize the numbers which will not change among all the liers. To do that, find the Longest Increasing Subsequence (LIS) of the liers. The number of elements in the LIS is the number of elements in the array which will not change. Hence, the number of transformations is the size of the array minus the size of the LIS.

In my example, the liers are [1,2,4,6]. The size of LIS([1,2,4,6]) is 4. Hence the number of transformations is 2.

3 Likes

In the editorial given what is SET_value array actually stores . Can you explain the above editorial with an example.

Terima kasih dan salam kenal.
codechef Link

code Link

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

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

1 Like

thank you :slight_smile:

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