LOC JULY SCHAR Need Help

general
,
1

I passed all test cases except one(TLE).

int main() {

int t;scanf("%d",&t);
while(t--){
   char s[100000];
  scanf("%s",s);
    int len=strlen(s);
  //  cout<<len<<endl;
 //   for(int i=0;i<100000;i++)if(s[i]-'a'>=0 && s[i]-'a'<=25)len++;else break;
    
    int cost[len];
    for(int i=0;i<len;i++)cost[i]=1000000000;
    cost[0]=0;
    vector <int> g[26];
    for(int i=0;i<len;i++)g[s[i]-'a'].pb(i);
    
    for(int i=0;i<len-1;i++){
        g[s[i]-'a'].erase(g[s[i]-'a'].begin());
        for(auto it=0;it<g[s[i]-'a'].size();it++)if(cost[g[s[i]-'a'][it]]>cost[i])cost[g[s[i]-'a'][it]]=cost[i];
        int temp=abs(s[i+1]-s[i]);
        if(cost[i+1]>cost[i]+temp)cost[i+1]=cost[i]+temp;
    }
    printf("%d\n",cost[len-1]);
}
return 0;

}

2

I dont think we can see your code because LoC solutions not being public. Can you somehow share your code?

3

I have edited question.

4

It seems obviously TLE to me :confused:

Take a look at the nested for-loops you used. I think that makes your code O(N^2). Doesn’t it? In case I am wrong, can you explain further what you have tried to do?

5

I know it has to be TLE. I am not asking about how can I optimize my code. I want to know how to solve it efficiently.

6

A more elegant way of what you tried to do is like this-

       int arr[26],i,j;
	   for(i=0;i<26;i++)arr[i]=1000000;

	   int dp[n];
	   dp[0]=0;
	   arr[s[0]-'a']=0;
	   for(i=1;i<n;i++)
	   {
	       dp[i]=min(arr[s[i]-'a'],dp[i-1]+abs(s[i]-s[i-1]));
	       arr[s[i]-'a']=min(arr[s[i]-'a'],dp[i]);
	   }
	   //for(i=0;i<n;i++)cout<<dp[i]<<" ";cout<<endl;
	   cout<<dp[n-1]<<endl;

arr is serving the purpose of, minimum cost of reaching at letter i if we use jumps in between.

4 Likes
7

Ohk, I thought you wanted to know why your code is wrong.

8

I didnt include comments because i thought we both are on same both in terms of thinking. Do you need comments as well?

9

No comments needed. Vow!!! I just had to use dp. Thanks.

10

You did use dp, its just that you could have done better. Wish you best :slight_smile:

1 Like
11

Nice solution @vijju123 :slight_smile:
I guess you have used shortest path algo in some way (denoted by arr[]).

12

Thanks dear :slight_smile: . Yes, I used arr for that. Its just visualization. Take it as, we are at some character ‘ch’ present at index i, we can reach it in two ways, either by jumping from previous char, or jumping to this char directly from same-character checkpost. Jumping from previous same-char checkpost is already stored in arr[s[i]-‘a’], and cost to reach here from previous element is in dp[i].

For this case, imagine that we are filling a general index i , then proceed for start and end of table.

The best thing is synergy, dp[i] helps in determining arr, while arr helps in finding dp[i].

13

@vijju123 I have a doubt what if there is no check point of that character but it gives the smallest path i.e. acdefb.
So here a to b is shortest path Right?. But the algorithm is looking for check points which does not exist. So it will go for a-f i.e 5 then f-b that is 4. Because arr[b-‘a’] is 1000000. Can you please explain how the algo will handle this.

14

In the question we are starting from a, and have to reach b. We cannot reach b before we reach f, since jumping isnt possible and as given in Q, we have to go linearly from a to c, then d,e,f and finally b. Answer is same in both cases.

15

I interpreted the question in wrong way. Need to develop patience to read the question carefully. Lesson learned:)

1 Like
16

A very similar problem to this one is DIGJUMP. Maybe its editorial will help you much more :slight_smile: