TopCoder SRM 498 – DIV 1 Level 2

The solution of the problem is as follows.

#define MP     make_pair
typedef long long   LL;

int xx[]={-1,-1,0,1,1,1,0,-1};
int yy[]={0,-1,-1,-1,0,1,1,1};

vector<int> res;

void bfs(vector<vector<int> >&v, int n, int m, int x, int y){
    queue<pair<int, pair<int,int> > > q;
    q.push(MP(1, MP(x, y)));
    while(!q.empty()){
        int val = q.front().first;
        x = q.front().second.first;
        y = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0) continue;
        if(x >= n || y >= m) continue;
        if(v[x][y]) continue;
        v[x][y] = val;
        res[val]++;
        for(int k=0; k<8;k++)
            q.push(MP(val+1, MP(x+xx[k], y+yy[k])));
    }
}

void bfs1(vector<vector<int> >&v, int n, int m, int x, int y){
    vector<vector<pair<int,pair<int,int> > > > mark(202);
    vector<vector<bool> > vis(n, vector<bool>(m, 0));
    queue<pair<int, pair<int,int> > > q;
    q.push(MP(1, MP(x, y)));
    while(!q.empty()){
        int val = q.front().first;
        x = q.front().second.first;
        y = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0) continue;
        if(x >= n || y >= m) continue;
        if(vis[x][y]) continue;
        vis[x][y] = true;
        mark[val].PB(MP(v[x][y], MP(x,y)));
        for(int k=0; k<8 ;k++)
            q.push(MP(val+1, MP(x+xx[k], y+yy[k])));
    }
    int it = 1;
    for(int i=1; i<202 ;i++){
        map<int,int> mapa;
        for(int j=0; j<mark[i].size();j++){
            int val = mark[i][j].first;
            x = mark[i][j].second.first;
            y = mark[i][j].second.second;
            if(mapa.find(val) == mapa.end()) mapa[val] = it++;
            v[x][y] = mapa[val];
        }
    }
}

LL fact(int x){
    LL r=1;
    for(LL i=2; i<=LL(x) ;i++)
        r = (r*i)%1000000009LL;
    return r;
}

class FoxStones{
    public:
    int getCount(int n, int m, vector<int> sx, vector<int> sy) {
        vector<vector<int> > v(n, vector<int>(m, 0));
        res = vector<int> (201, 0);
        bfs(v, n, m, sx[0]-1, sy[0]-1);
        for(int i=1; i            bfs1(v, n, m, sx[i]-1, sy[i]-1);
        vector<int> sol(40002, 0);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                sol[v[i][j]]++;
        LL r = 1LL;
        for(int i=0;i<sol.size();i++)
            if(sol[i])
                r = (r*fact(sol[i]))%1000000009LL;
        return r;
    }
};

TopCoder SRM 498 – DIV 1 Level 1

This problem is more simple but the implementation should be carefully.

Solution O(n):
1) get the first ascending sequence
2) get the first descending sequence
3) get the number with no difference
4) get the second ascending sequence
5) get the second ascending sequence

class FoxSequence{
    public:
    string isValid(vector<int> seq) {
        int n = seq.S;
        if(n < 5) return "NO";
//1) get the first ascending sequence
        int dif = seq[1]-seq[0], it = 1;
        if(dif<=0) return "NO";
        while(it<n-3 && seq[it]-seq[it-1] == dif) it++;
//2) get the first descending sequence
        dif = seq[it]-seq[it-1];
        if(dif>=0) return "NO";
        while(it<n-2 && seq[it]-seq[it-1] == dif) it++;
//3) get the number with no difference
        while(it<n-2 && seq[it] == seq[it-1]) it++;
//4) get the second ascending sequence
        dif = seq[it]-seq[it-1];
        if(dif<=0) return "NO";
        while(it<n-1 && seq[it]-seq[it-1] == dif) it++;
//5) get the second ascending sequence
        dif = seq[it]-seq[it-1];
        if(dif>=0) return "NO";
        while(it<n && seq[it]-seq[it-1] == dif) it++;
        if(it != n) return "NO";
        return "YES";
    }
};