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 :)

How is that possible that SASUKE UCHIHA got compilation error??
http://imgur.com/BB0osSN

#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define INF (1e9+7)
#define forn(i,z,n) for( auto (i) = (z); (i) < (n); ++i)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

struct node {
    int key;
    node *left, *right, *parent;
    node(int q, node *x, node *y, node *p)  {
        key = q;
        left = x;
        right = y; parent = p;
    }
};
node *tree  = NULL, *f = NULL;
void add_n( node *j, node *&z)  {
    if( z == NULL)  {
        z = new node(j->key,NULL,NULL,NULL);
        return ;
    }
    if( z->key >= j->key)  {
        if( z->left)  {
            add_n(j, z->left);
        }
        else  {
            z->left = j;
            j->parent = z;
        }
    }
    else  {
        if( z->right)  {
            add_n(j,z->right);
        }
        else  {
            j->parent = z;
            z->right = j;
        }
    }
}
void show( node *x)  {
    if( x != NULL)  {
        show(x->left);
        cout << x->key << ' ';
        show(x->right);
    }
    else return ;
}
node *find_min( node *root)  {
    if( root->left != NULL)  {
        return find_min(root->left);
    }
    else  {
        return root;
    }

}
void delete_n(node *root, int val )  {
    if( root == NULL)  return ;
    else if( val < root->key)  delete_n( root->left, val);
    else if( val > root->key) delete_n(root->right, val);
    else  {
        if( root->left == NULL && root->right ==NULL)  {
            //delete root;
            root = NULL;
        }
        else if( root->left == NULL)  {
            root->right->parent = root->parent;
            root = root->right;
            //delete root->right;
            root->right = NULL;
        }
        else if( root->right == NULL)  {
            root->left->parent = root->parent;
            root = root->left;
            //delete root->left;
            root->left = NULL;
        }
        else  {
            node *temp = find_min( root->right);
            temp->parent = root->parent;
            root = temp;
            delete_n( root->right, temp->key);
        }
    }
    return ;
}
void post( node *x)  {
    if( x != NULL)  {
        post(x->right);
        post(x->left);
        cout << x->key << ' ';
    }
}
void show_parents( node *z)  {
    if(z != NULL)  {
        show_parents(z->left);
        show_parents(z->right);
        if( z->parent != NULL)
            cout << z->key << ' ' <<  (z->parent->key) << endl;
    }
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector <int> v;
    forn(i,0, n)  {
        int x;
        cin >> x;
        v.pb(x);
    }
    for(int i = 0; i <n; ++i)  {
        node *help = new node(v[i], NULL, NULL,NULL);
        add_n( help, tree);
    }
    show(tree);                              // в невозрастающем порядке
    delete_n(tree, 3);
    cout << endl;
    show(tree);
    return 0;
}

#include<iostream>
#include<string>
using namespace std;
int main ()
{
    string s;
    cin>>s;
    int max=0,i=0,index=0,a=0,p=0;
    for (i=0; i<s.size()-5; i++)
    {
    if(s[i]>'a' && s[i]<='z')
    p--;
    if(s[i]=='S')
    p+=2;
    if(s[i+1]=='a')
     p+=2;
    if(s[i+1]>='A' && s[i+1]<='Z')
     p--;
    if(s[i+2]=='n')
    p+=2;
    if(s[i+2]>='A' && s[i+2]<='Z')
    p--;
    if(s[i+3]=='d')
    p+=2;
    if(s[i+3]>='A' && s[i+3]<='Z')
    p--;
    if(s[i+4]=='r')
    p+=2;
    if(s[i+4]>='A' && s[i+4]<='Z')
    p--;
    if(s[i+5]=='o')
    p+=2;
    if(s[i+5]>='A' && s[i+5]<='Z')
     p--;
        if (p>max)
        {
            max=p;
            index=i;
        }
        p=0;
            }
    i=index;
    if (s[i]!='S' && s[i]>='A' && s[i]<='Z' || s[i]=='s')
    a+=5;
    else if (s[i]!='S' && s[i]>='a' && s[i]<='z')
    a+=10;
    if (s[i+1]!='a' && s[i+1]>='a' && s[i+1]<='z' || s[i+1]=='A')
    a+=5;
    else if (s[i+1]!='a' && s[i+1]>='A' && s[i+1]<='Z')
    a+=10;
    if (s[i+2]!='n' && s[i+2]>='a' && s[i+2]<='z' || s[i+2]=='N')
    a+=5;
    else if (s[i+2]!='n' && s[i+2]>='A' && s[i+2]<='Z')
    a+=10;
    if (s[i+3]!='d' && s[i+3]>='a' && s[i+3]<='z' || s[i+3]=='D')
    a+=5;
    else if (s[i+3]!='d' && s[i+3]>='A' && s[i+3]<='Z')
    a+=10;
    if (s[i+4]!='r' && s[i+4]>='a' && s[i+4]<='z' || s[i+4]=='R')
    a+=5;
    else if (s[i+4]!='r' && s[i+4]>='A' && s[i+4]<='Z')
    a+=10;
    if (s[i+5]!='o' && s[i+5]>='a' && s[i+5]<='z' || s[i+5]=='O')
    a+=5;
    else if (s[i+5]!='o' && s[i+5]>='A' && s[i+5]<='Z')
    a+=10;
    cout<<a<<endl;
    return 0;
}

Edited by author 30.12.2014 18:40

Edited by author 03.01.2015 17:13

Edited by author 03.01.2015 17:13

1)Look at my solution 7450309 (Runtime error (non-zero exit code) on test 23)) and 7450312(AC). Why i got Runtime error (non-zero exit code) on test 23?
  In first solution i have nmax=123456 and in second 223456. What is range of n?

2)Look on problem 1974. In forum i wrote test when my AC solution get wrong answer(I can write more tests where my old AC solution falls)

I have solved it by reduction to a graph exploration task.
Each vertex consists of three parameters (i, j, pr).
Where i, j denote number of card at the top of each pile and pr denotes previous state.  pr is also a "used"  array.  So,  if pr[N] [N] =none,  then impossible.  Otherwise  just recover answer using pr.  You can also have in your state additional parameter diff denotes difference between red and black cards.  I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively.  There is an edge iff difference at the next step would be not greater than one (abs) ,  obviously.

//I have correct in the IDE, what's wrong?

import java.io.IOException;
import java.util.Scanner;

public class VasyaCare{
    public static void main(String[] args) throws IOException {
    VasyaCare vasya_care = new VasyaCare();
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    try{                               // Check
            if(n < 10){
        double[] b = vasya_care.setScore(n);
        double median = vasya_care.getMedian(b);
        if(median==3){
            System.out.println("None");
        }
        else if(median==5){
            System.out.println("Named");
        }
        else if(median >= 4.5){
            System.out.println("High");
        }
        else if(median < 4.5){
            System.out.println("Common");
        }
        }
        else throw new IOException("Please, type number from 1 to 10!");
    }
    catch(Exception e){e = new IOException();}
    }


    double getMedian(double[] b{          // calculate median score of exam
    int sum = 0;
    for(int i = 0; i < b.length; i++){
        sum = (int) (sum + b[i]);
    }
    return (double)sum/b.length;
    }

    double[] setScore(int n){            // forming list scores
    Scanner scn = new Scanner(System.in);
    double[] b = new double[n];{
        for(int j = 0; j < n; j++){
            int m = scn.nextInt();
            if(m<3 || m > 5){
                System.out.println("Type score from 3 to 5: ");
                j--;
            }
            else if (m>=3 && m<=5){
                b[j] = m;
            }
        }
    }
    return b;
    }
}

// Thank you for your attention!