Help in Digjump code....

digjump
june
long
long-contest

#1

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!='

'-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*==arr[n-1])
> { count*=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*==arr[n-2])count*=2;
> }
> count[n-2]=1;
> for(i=n-3;i>=0;i–)
> {
> if(count*==0 && dig[arr*]!=-1)
> count*=count[dig[arr*]]+1;
> }
> if(count[0]!=0) {pf("%d
“,count[0]);exit(0);}
> for(i=n-3;i>=0;i–)
> { beg=1;least=SIZE;
> if(count*!=0) continue;
> temp=dig[arr*];
> 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*=small;
> if(dig[arr*]==-1 || count*<=count[dig[arr*]])dig[arr*]=i;
> }
>
> for(i=n-2;i>=0;i–)
> { beg=1;least=SIZE;
> count*=count[i+1]+1;
> if(i!=dig[arr*] && count*>count[dig[arr*]]+1)count*=count[dig[arr*]]+1;
> if(i!=0)
> {j=1;
> while(j<count* && 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*>least)count*=least;
> }
> pf(”%d
",count[0]);
> return 0;
> }