CARLOS - Editorial

editorial
, , , , ,
21

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

22

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
23

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

24

Terima kasih dan salam kenal.
codechef Link

code Link