Cer's blog

By Cer, 10 years ago, In English

I am trying to solve Flag on Spoj and it is the same problem on CodeForces Flag2 and I got it accepted on codeforces but I'm getting Wrong answer on spoj in run id 10 . There is just one difference between spoj and codeforces that is in spoj we don't have to print the flag after making it standard . What could the problem be ? here is my code :

include

include

include

using namespace std;

struct cell { int i , j; int dp_val; };

int arr[501][501]; int n,m; int dp[501][26][26];

vector < cell > v;

int get1(int row,int a,int b) { int res = 0; for (int i=0;i<m;i++) { if (i % 2 == 0) { if (arr[row][i] != a) res++; } else { if (arr[row][i] != b) res++; } } return res; }

bool compare(cell a,cell b) { if ( a.dp_val < b.dp_val ) return 1;

if (a.dp_val == b.dp_val)
    if ( a.i < b.i )
       return 1;

if (a.dp_val == b.dp_val)
    if ( a.i == b.i )
       return (a.j < b.j) ;

return 0; }

int main() { //freopen("m.in","r",stdin); scanf("%d %d",&n,&m); char c; scanf("%c",&c);

for (int i=0;i<n;i++)
{
    for (int j=0;j<m;j++)
    {
       scanf("%c",&c);
       arr[i][j] = int(c) - int('a');
    }
    //if (i < n-1)
       scanf("%c",&c);
}

cell ccc;
int res = 1000000;
for (int i=0;i<26;i++)
    for (int j=0;j<26;j++)
    {
       ccc.i = i;    ccc.j = j;

       if (i == j)
          ccc.dp_val = 1000000;
       else
        ccc.dp_val = dp[0][i][j] = get1(0,i,j);
       v.push_back(ccc);
       res = min(res,ccc.dp_val);
    }

if (n > 1)
    res = 1000000;

for (int r=1;r<n;r++)
{
    sort(v.begin(),v.end(),compare);
    for (int i=0;i<26;i++)
       for (int j=0;j<26;j++)
       {
         if (i == j)  
         {
          dp[r][i][j] = 1000000;
          continue;
         }         
         int d = get1(r,i,j);

         int minv = 1000000;

         for (int k=0;k<v.size();k++)
          if (v[k].i != i && v[k].j != j && v[k].i != v[k].j)
          {
              minv = v[k].dp_val;
              break;
          }


         dp[r][i][j] = minv + d;

         if (r == n-1)
          res = min(res , minv + d);
       }

       if (r < n-1)
         for (int i=0;i<26;i++)
          for (int j=0;j<26;j++)
          {
              v[i*26 + j].i = i;
              v[i*26 + j].j = j;
              v[i*26 + j].dp_val = dp[r][i][j];
          }
    }

printf("%d\n",res);

return 0; }

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

PS: I don't know what the problem but the first three lines of my code are including the libraries : iostream , algorithm , vector

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Leave an empty line between the first paragraph and the code

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      .. and put your code between 5 tildas like that:

      text
      
      Five ~
      code
      Five ~
      
      text