Просто по длине слова определяем,  какой у нас случай.
(Замена,  удаление или вставка).

Затем для каждой позиции пытаемся внести изменения и смотрим,  получается у нас выполнение условия или нет.

Удобно завести массив постфиксных сумм для того чтобы быстро пересчитать сумму позиций единиц.

Так как сумма всех элементов последовательности равна (S+N),  то сумма всех элементов последовательности,  в которой каждый элемент уменьшен на единицу,  равна просто N.

Тогда если мы найдём в такой последовательности с уменьшенными членами отрезок с максимальной суммой и сравним сумму на нем с числом N,  то мы узнаем ответ на задачу.

А именно,  если эта сумма превосходит N,  то ответ "NO".
В противном случае, ответ "YES".

Отрезок с максимальной суммой ищется за O(n)  методом кумулятивных сумм.

All the test cases given in this forum are working.But giving WA 1

my code is:
#include <stdio.h>
#include <string.h>
 int len[910][8110];
 int dig[910][8110];
 int num[110];

 int main(){
  int t,s1,s2,k,pt,i,j,l,temp;
  memset(len,0,sizeof(len));
  for(i=1;i<=900;i++){
      for(j=1;j<=8100;j++){
          for(k=1;k<=9;k++){
              if((i-k)<0||(j-k*k)<0)
                  break;
              else if((i-k)==0&&(j-k*k)==0){
                  len[i][j] = 1;
                  dig[i][j] = k;
              }
              else if(len[i-k][j-k*k]>0){
                  if(len[i-k][j-k*k]+1<len[i][j]||len[i][j]==0){
                      len[i][j] = len[i-k][j-k*k]+1;
                      dig[i][j] = k;
                  }
              }
              else
                  continue;
          }
      }
  }
  scanf("%d",&t);
  while(t--){
  scanf("%d %d",&s1,&s2);
  pt = 0;
  if(len[s1][s2]==0||len[s1][s2]>100)
      printf("No Solution");
  else{
        i=s1;
        j=s2;
      while((len[i][j]>=1)&&i>=1&&j>=1){
          l = dig[i][j];
          num[pt++] = l;
          i = i-l;
          l = l*l;
          j-=l;
      }
      for(i=0;i<pt;i++){
        for(j=i+1;j<pt;j++){
            if(num[i]>num[j]){
             temp=num[i];
             num[i]=num[j];
             num[j] = temp;
            }
        }
      }
      for(i=0;i<pt;i++)
          printf("%d",num[i]);
  }
  printf("\n");
  }
  return 0;
 }

To read IP address /subnet mask
I recommend you to use the following template


unsigned int read_mask(){
    unsigned int a, b, c, d;
    scanf("%u.%u.%u.%u", &a, &b, &c, &d);
    return (a<<24) + (b<<16) + (c<<8) + d;
}

You can just sort edges in non-increasing order and add them sequentially until there are two or more connectivity components...

who knows the Test2 ??

Edited by author 17.07.2017 19:41

It was hard to understand how to calculate the answer.

It is relatively easy to invent a correct solution when you know the expected time complexity.

Solve the task online,  read elements one by one.
So,  you have dp[i][j] = count of different j-inversions ending at element number j.

dp[i] [j] =sum (dp[p] [j-1]) for all p>i.

The answer is sum(dp[i] [k])  for all i=0...n-1.

As mentioned below,  an array of Fenwick trees is your friend.

x/0==0

re many times, there is nothing in problem description...

Rather easy problem

You can have an array deg[i][j] = count of adjacent unvisited cells for cell (i;j).

While doing DFS sort edges by non-decreasing deg[i+move. first] [j+move. second].

It calls an heuristic after some scientist whose name begins at W.

i got WA#6 when i use this  code

#include <iostream>
#include <cmath>
using namespace std;

long int n,m,y,p,q,r[999];

int main(){
    cin>>n>>m>>y;
    for (int i=0;i<m;i++){
        if (lround(pow(i,n)) % m==y){
            q++;
            r[q]=i;
        }
    }
    if (q==0){
        cout<<"-1";
    }
    else {
        for (int i=1;i<=q;i++){
            cout<<r[i]<<' ';
        }
    }
}


but when i use neighbored code which is already acc, and tested some test case between them, it give me same results. whats probably wrong in my code

by the way, the neighbored code is pascal language, but the point is, i just used that for test case.

Though without Aho-Corasick and without trie and without any optimizations simply DFS with used [i] [j]  and backtracking is fast

Wrong answer in test №17

http://ideone.com/06yGHW

Maybe someone could improve that solution and get AC with it.  Current status of that code is WA#8. I think it is quite boring and tedious to upgrade it to AC.  Maybe you can see how to upgrade it with small effort.

#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;
#define MAXN 100
#define MAXM 10
int ship[MAXN];
int row[MAXM];
int exi[MAXN];
int N, M;

int cmp(const void* a, const void* b);
void divid(int m);
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0; i<N; i++)
        scanf("%d", &(ship[i]));
    for(int i=0; i<M; i++)
        scanf("%d", &(row[i]));

    for(int i=0; i<N; i++)
        exi[i] = 1;

    qsort(ship, N, sizeof(int), cmp);
    divid(M);

    return 0;
}

int cmp(const void* a, const void* b)
{
    int* x = (int*)a;
    int* y = (int*)b;
    return *y - *x;
}

void divid(int m)
{
    if(m > 1)
        divid(m-1);

    stack<int> s;
    int tot = row[m-1];
    int hav = 0;
    int i = 0;
    for(;;){
        while(i<N && (!exi[i] || ship[i]>(tot-hav))) i++;
        if(i >= N){
            for(;;){
                i = s.top();
                s.pop();
                hav -= ship[i];
                exi[i] = 1;
                i++;
                if(i < N)
                    break;
            }
            continue;
        }
        s.push(i);
        hav +=  ship[i];
        exi[i] = 0;
        i++;
        if(hav == tot){
            int sh_ind;
            int siz = s.size();
            printf("%d\n", siz);
            while(!s.empty()){
                sh_ind = s.top();
                s.pop();
                printf("%d ", ship[sh_ind]);
            }
            printf("\n");
            return;
        }
    }
}

####################################################
I used recursion alg. And I know there is error in this code because I didn't deal with the situation I called "data confliction" such as "5 = 2+3".But how to IMPROVE it ???

email:1813484947@qq.com



Edited by author 15.07.2017 20:00

Edited by author 16.07.2017 15:23

Pozhaluysta, kto-nibud', dayte mne hot' kakie testy k zadache 1070! A to vse testi, kotoriye u menya yest' moya programma prohodit, no na teste #1 dayot nepravil'niy otvet!
I obyasnite, pochemu mozhet byt' test:
"12.00 15.00
01.02 03.07
Answer: 0" ?

#include <iostream>

int main()
{
  int N;
  std:: cin >> N;
  /* dynamic memory allocation */
  int ** p = new int * [N];
  for (int i = 0; i < N; i++)
    p[i] = new int [N];

  /* initialize upper triangle matrix */
  p[0][N-1] = 1;
  int m, n;
  int ct = 1, value = 2, iter = 1, row = 0, column = N - 2;
  while (ct <= N - 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter++; ct++;
    column--;
  }

  /* initialize the lower triangle matrix */
  row = 1; column = 0, iter = N - 2;
  while (ct > 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter--; ct--;
    row++;
  }

  /* display matrix */
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
      std::cout << p[i][j] << " ";
    std::cout << std::endl;
  }

  /* release memory */
  for (int i = 0; i < N; i++)
    delete[] p[i];
  delete[] p;

  return 0;
}

first i get acces violation in my code. and then i search what it acces violation, and then i remake my code, then submit again. still get WA #4, before i reamke the code it says Accces Violation in test #4. Can anybody help me?

This is my code.

#include <iostream>
using namespace std;

int n,ar[10000],p;

int main(){
    cin>>n;
    for (int i=1;i<=n*n;i++){
        cin>>p;
        ar[p]=p;
    }
    for (int i=1;i<=n*n;i++){cout<<ar[i]<<' ';}
}

Edited by author 15.07.2017 10:58

tried all mentioned test cases .all correct. still WA on #12.
using surfix array.any idea?

code here:

#include <cstdio>
#include <cstring>
int const N=220000;
int st[256], rank[2*N], rank1[2*N], count[N], tmp[N];
char a[N], b[N], s[N], max1;
int sa[N], height[N], si;
int main(){
    memset(st, 0, sizeof st);
    memset(rank, 0, sizeof rank);
    memset(rank1, 0, sizeof rank1);
    scanf("%s", b);
    int n1=strlen(b);
    for(int i=1; i<=n1; ++i)a[i]=b[i-1];
    for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i];
    a[0]=' ';
    a[n1+1]='#';
    int n=2*n1+1;
    a[n+1]='&';
    for(int i=1; i<=n; ++i)st[a[i]]=1;
    for(int i=1; i<=255; ++i)st[i]+=st[i-1];
    for(int i=1; i<=n; ++i)rank[i]=st[a[i]];

    int k=0;
    for(int p=1; k!=n; p+=p){
        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i+p]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;

        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];

        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for(int i=2; i<=n; ++i){
            if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k;
            rank[sa[i]]=k;
        }
    }
    k=0;
    for(int i=1; i<=n; ++i){
        if(rank[i]==1){
            k=0;
        }else{
            --k;
            if(k<0)k=0;
            while(a[i+k]==a[sa[rank[i]-1]+k])++k;
        }
        height[rank[i]]=k;
    }

    int max=-1;
    for(int i=2; i<=n; ++i){
        int p=sa[i];
        int q=sa[i-1];
        if((p-1)/n1 != (q-1)/n1){
            if(p+q+height[i]==n+2){
                if(height[i]>max){
                    max=height[i];
                    si=p;
                }
            }
        }
    }
    for(int i=si; i<si+max; ++i)printf("%c", a[i]);
    return 0;
}

THX :)