×

# Help in Digjump code....

 0 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 > #include > #include > #include > #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 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=1+count[temp]; > if(i!=0) > {j=1; > while(j {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=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 { > 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; > }  asked 16 Jun '14, 19:08 3★s1g13 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,424
×477
×50
×50
×7

question asked: 16 Jun '14, 19:08

question was seen: 1,472 times

last updated: 16 Jun '14, 19:08