Cer's blog

By Cer, 11 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; }

Full text and comments »

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

By Cer, 11 years ago, In English

I'm learning segment tree data structure and I've learned the (Build, update, query) functions,and I'm trying to make an update on an interval using lazy propagation algorithm but I can't find the correct implementation of it.

Would you please provide me with the correct code of lazy propagation algorithm for these two problem :

1- we have an array of integers and there are two queries :

a- get the sum of a specific range from the array

b- modify a specific range in the array by adding a number to all elements in this range

2- we have an array of integers and there are two queries :

a- get the minimum number of a specific range from the array

b- modify a specific range in the array by adding a number to all elements in this range

I just need an "update" function on a range. Thanks.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By Cer, 11 years ago, In English

I want to start learning geometry from the starter level and there are a lot of books about it but I can't decide which are the best for competitions like ones on Codeforces and ACM so, what are the most recommended books for that ? and thanks .

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By Cer, 11 years ago, In English

I'm trying to learn a new data structure called "Binary Indexed Tree" and I have read the tutorial on TopCoder, it was really good but I can't understand the main purpose of this data structure, and when do we have to use it ? If someone has a better tutorial, I would be thankful for him, and provide me with some problems to practice please .

Full text and comments »

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