Doom Bakes Cakes Wrong Solution (practice->easy)

general
, , , ,
1

Hi guys. I am working on the practice problem Doom Bakes Cakes in easy section. Here is the link http://www.codechef.com/problems/CAKEDOOM. I used a simple and obvious strategy to solve the problem. Considered given cases along with the other cases given on editorial page of the problem on forum and they are giving the correct output. Can anyone help. Thanks in advance.

My Algorithm:

  1. First taking the no. of test cases.
  2. then using a loop, taking the given partial arrangement in a string.
  3. Now, using another nested loop, to check character by character whether its a number or ‘?’.
    3.1 If its a number checked for its neighbors that they are same or not. If same printed “NO” and loop is breaked to go for the next arrangement. Otherwise, the loop continued.
    3.2 If its a ‘?’, then starting from 0 to k-1 that which digit should be optimum to place by comparing it with neighboring digits.
  4. In this way, if all the changes are made and no impossibility encountered, printed the new arrangement.

Here is my source code:

#include <stdio.h>
#include <string.h>
int main(){
  char string[101];
  int test,k,i,j,chk,len;  // chk = to keep check whether new combination is possible or not
  scanf("%d", &test);
  while(test--){
    scanf("%d", &k);
    scanf("%s", string);
    len = strlen(string);
    chk = 1;
    for(i=0;i<len;i++){
      if(string[i]=='?'){
	if(i==0){
	  for(j=0;j<k;j++)
	    if(string[1]-48!=j && string[len-1]-48!=j){
	      string[0] = j + 48;
	      break;
	    }
	    else if(j==k-1){ 
	      printf("NO\n");
	      chk = 0;
	      break;
	    }
	}

	else if(i==len-1){
	  for(j=0;j<k;j++)
	    if(string[0]-48!=j && string[len-2]-48!=j){
	      string[len-1] = j + 48;
	      break;
	    }
	    else if(j==k-1){
	      printf("NO\n");
	      chk = 0;
	      break;
	    }
	}
      
	else{
	  for(j=0;j<k;j++)
	    if(string[i+1]-48!=j && string[i-1]-48!=j){
	      string[i] = j + 48;
	      break;
	    }
	    else if (j==k-1){
	      printf("NO\n");
	      chk = 0;
	      break;
	    }
	}
      }

      else{
	if(i==0){
	  if(string[1]==string[0] || string[len-1]==string[0]){
	    chk = 0;
	    printf("NO\n");
	    break;
	  }
	}

	else if(i==len-1){
	  if(string[0]==string[len-1] || string[len-2]==string[len-1]){
	    chk = 0;
	    printf("NO\n");
	    break;
	  }
	}
	else{
	  if(string[i+1]==string[i] || string[i-1]==string[i]){
	    chk = 0;
	    printf("NO\n");
	    break;
	  }
	}
      }
      
      if(!chk)
	break;
    }
    if(chk)
      printf("%s\n",string);
  }
  return 0;
}