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.
Sir can u please suggest some good links/resources of dynamic programming tutorials and/or examples!
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 ?
@xellos0 Ur reasoning for choosing the problem name is even better than the problem itself! Impressive!!! 
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
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.
In the editorial given what is SET_value array actually stores . Can you explain the above editorial with an example.
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.
Learn dynamic programming, I guess. It’s a concept that’s fairly specific to programming (computing more stuff and utilising it efficiently).
thank you
observing that dp[i][j] only depends on ith and (i-1)th row, we can reduce states (which indirectly helps reduce time too)
I think the time limit was too tight… Also my O(n*m) solution in c++ didn’t pass…
When xellos creates a problem, it must include a meme! I was waiting for this 
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.