You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in Digjump code....

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

asked 16 Jun '14, 19:08

s1g13's gravatar image

3★s1g13
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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