Блог пользователя Cer

Автор Cer, 11 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор Cer, 11 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

Автор Cer, 11 лет назад, По-английски

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 .

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор Cer, 11 лет назад, По-английски

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 .

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится