SRM508

Summary:

I don't know how, this time I spent more time on level 1. One main reason could be critical: the problem statement is not that clear, so that takes me a lot of time to figure it out from the test cases. But I think my programming background is well defended from this contest. My BFS solution takes me a lot of time, but I didn't debug my code because of the my coding error. Just hope I could do better next time. At the same time, maybe my English Reading ability needs more practice.

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Div 2, Level 1

Div 2, Level 2

Div 2, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Source Code:

Division Two - Level Three:

Solution

Source Code:

Division Two - Level Two:

Solution

Source Code:

Division Two - Level One:

Solution

Source Code:

//Thu Jun  2 12:10:18 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

class CandyShop {
public:
    int countProbablePlaces(vector <int>, vector <int>, vector <int>);
};

int CandyShop::countProbablePlaces(vector <int> X, vector <int> Y, vector <int> R) {
    set<pair<int, int> > positions;
    deque<pair<pair<int, int>, int> > q;
    int N = X.size();
    int mmax = 0;
    set<pair<int, int> >::iterator it;
    for(int i=0; i<N; i++){
        set<pair<int, int> > tmp;
        q.clear();
        q.push_back(make_pair(make_pair(X[i], Y[i]), R[i]));
        tmp.insert(make_pair(X[i], Y[i]));
        while(!q.empty()){
            int x = q.front().first.first;
            int y = q.front().first.second;
            int r = q.front().second;
            q.pop_front();
            if(r <= 0) continue;
            for(int j=0; j<4; j++){
                int xx = x + dx[j];
                int yy = y + dy[j];
                int sz = tmp.size();
                tmp.insert(make_pair(xx, yy));
                if(tmp.size() != sz)
                    q.push_back(make_pair(make_pair(xx, yy), r-1));
            }
        }
        if(i==0)
            positions = tmp;
        else{
            set<pair<int,int> > res;
            for(it = tmp.begin(); it!=tmp.end(); it++){
                if(positions.count(*it))
                    res.insert(*it);
            }
            positions = res;
        }
    }
    return positions.size();
}

//Powered by [KawigiEdit] 2.0!