My logic involves searching for n-1 and n-2 elements in the array, making their jump counts 1 and 3 respectively. Then i start from n-1 and using dp, i check for i+1th, least jump count of same digit uptil now, and moving towards 0 to find lowest… While this i keep updating the jump counts of each digit and keep storing the lowest jump count in dig… After updating, i recheck the array for lack of upgradation…if found it is rectified…finally count[0] printed…
I have been working on this code for 3 days, checking all possible cases and jump cunts at all positions,all are answered correctly, but still the code shows WA on submission. Even after 15 WA i have not been able to recover over the bug … Somebody plz help me find the bug in the program
> #define TYPE int
> #define SIZE 100000
> #define sf scanf
> #define pf printf
> #include <stdio.h>
> #include<math.h>
> #include<string.h>
> #include<stdlib.h>
> #define gc getchar_unlocked
> //code from here
> int main(void) {
> TYPE count[SIZE]={0},n,temp,beg=1,least=SIZE,i=0,j=1,small=0,dig[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};int
> arr[SIZE]={0};char c=0;
> //for string input
> do
> {c=gc()-'0';
> arr[i++]=c;
> }while(c!='\n'-48 && c!=EOF-48);
> arr[--i]=0; n=i;
>
> //to initialize
> dig[arr[n-1]]=n-1;if(dig[arr[n-2]]==-1)dig[arr[n-2]]=n-2;
> if(dig[arr[n-3]]==-1)dig[arr[n-3]]=n-3;
> count[n-3]=2;
>
> for(i=n-3;i>=0;i--)
> {
> if(arr[i]==arr[n-1])
> { count[i]=1;
> if(i-1>=0 && arr[i-1]!=arr[n-1]){count[i-1]=2;
> if(dig[arr[i-1]]==-1)dig[arr[i-1]]=i-1;}
>
> if(i+1<n-2 && arr[i+1]!=arr[n-1]){count[i+1]=2;
> if(dig[arr[i+1]]==-1)dig[arr[i+1]]=i+1;}
> }
> else if(arr[i]==arr[n-2])count[i]=2;
> }
> count[n-2]=1;
> for(i=n-3;i>=0;i--)
> {
> if(count[i]==0 && dig[arr[i]]!=-1)
> count[i]=count[dig[arr[i]]]+1;
> }
> if(count[0]!=0) {pf("%d\n",count[0]);exit(0);}
> for(i=n-3;i>=0;i--)
> { beg=1;least=SIZE;
> if(count[i]!=0) continue;
> temp=dig[arr[i]];
> small=1+count[i+1];
> if(temp>i && 1+count[temp]<small)
> small=1+count[temp];
> if(i!=0)
> {j=1;
> while(j<small && beg<=i)
> {temp=dig[arr[i-beg]];
> if(count[i-beg]!=0){least=count[i-beg]+j;
> break;}
> if(temp>i)
> {
> if(j+count[temp]+1<least)
> {least=j+count[temp]+1;
> }
> }
> if(arr[i-beg]==arr[i-beg+1] && arr[i-beg+1]==arr[i-beg+2]);else j++;
> beg++;
> }
>
> }if(small>least)small=least;
> count[i]=small;
> if(dig[arr[i]]==-1 || count[i]<=count[dig[arr[i]]])dig[arr[i]]=i;
> }
>
> for(i=n-2;i>=0;i--)
> { beg=1;least=SIZE;
> count[i]=count[i+1]+1;
> if(i!=dig[arr[i]] && count[i]>count[dig[arr[i]]]+1)count[i]=count[dig[arr[i]]]+1;
> if(i!=0)
> {j=1;
> while(j<count[i] && beg<=i)
> {
> if(count[i-beg]<5){if(least>count[i-beg]+j)least=count[i-beg]+j;
> break;}
> if(i-beg!=dig[arr[i-beg]] && least>count[dig[arr[i-beg]]]+j+1)
> least=count[dig[arr[i-beg]]]+j+1;
> else if(i-beg==dig[arr[i-beg]] && least>count[dig[arr[i-beg]]]+j)
> least=count[dig[arr[i-beg]]]+j;
>
> if(i-beg!=0)
> {
> if(arr[i-beg]!=arr[i-beg-1])j++;
> else if((count[dig[arr[i-beg]]]==count[i-beg]||count[dig[arr[i-beg]]]==count[i-beg-1]))
> j++;
> }
>
> beg++;
> }
> }
> if(count[i]>least)count[i]=least;
> }
> pf("%d\n",count[0]);
> return 0;
> }