SRM507:

Summary:
2011-05-28:

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

The same with Div2-Level2.

Source Code:

Division Two - Level Three:

Solution

Source Code:

Division Two - Level Two:

Solution

Source Code:

//Sat May 28 11:07:51 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class CubeStickers {
public:
    string isPossible(vector<string> sticker) {
        set<string> s(sticker.begin(), sticker.end());
        colors = vector<string> (s.begin(), s.end());
        if (s.size() < 3)
            return "NO";
        for (int i = 0; i < sticker.size(); i++) {
            mp[sticker[i]]++;
        }
        int faces = 6;
        for (int i = 0; i < colors.size(); i++) {
            if (mp[colors[i]] >= 2)
                faces -= 2;
            else
                faces--;
        }
        return faces > 0 ? "NO" : "YES";
    }
    map<string, int> mp;
    vector<string> colors;
};

Division Two - Level One:

Solution

Source Code:

//Sat May 28 10:50:51 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class CubeAnts {
public:
    int getMinimumSteps(vector<int> pos) {
        int N = pos.size();
        int mmax = 0;
        for (int i = 0; i < N; i++) {
            mmax = max(mmax, getStep(pos[i]));
        }
        return mmax;
    }
    int getStep(int p) {
        switch (p) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 2;
        case 3:
            return 1;
        case 4:
            return 1;
        case 5:
            return 2;
        case 6:
            return 3;
        case 7:
            return 2;
        default:
            return 0;
        }
    }
};

TCO11 Qualification Round 3

Date: 2011-05-25.

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Brute-force, but need to sort the elements wisely first.

Source Code:

//Tue May 24 20:07:48 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class Coins {
public:
    int need;
    int give;
    Coins(int n, int g) {
        this->need = n;
        this->give = g;
    }
    static bool cmp(const Coins &A, const Coins &B) {
        if (abs(A.need - A.give) < abs(B.need - B.give))
            return true;
        else if ((abs(A.need - A.give) == abs(B.need - B.give)) && A.need
                < B.need)
            return true;
        //      if (A.need < B.need)
        //          return true;
        //      if (A.need == B.need && A.give > B.give)
        //          return true;
        return false;
    }
};

class CoinMachinesGame {
public:
    int maxGames(int coins, vector<int> need, vector<int> give) {
        int N = need.size();
        vector<Coins> v;
        for (int i = 0; i < N; i++)
            v.push_back(Coins(need[i], give[i]));
        sort(v.begin(), v.end(), Coins::cmp);
        int count = 0;
        while (coins > 0 && v.size() > 0) {
            if (coins >= v[0].need) {
                int M = coins / v[0].need;
                count += M;
                coins -= (v[0].need - v[0].give) * M;
                //              cout << v[0].need << endl;
            } else
                v.erase(v.begin());
        }
        return count;
    }
};

Division One - Level One:

Solution

Brute-force.

Source Code:

//Tue May 24 20:01:07 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class AllButOneDivisor {
public:
    int getMinimum(vector<int> divisors) {
        sort(divisors.begin(), divisors.end());
        int K = divisors.size();
        long long product = 1;
        for (int i = 0; i < K; i++)
            product *= divisors[i];
        for (int i = divisors[K - 2]; i<=product; i++) {
            int count = 0;
            for (int j = 0; j < K; j++)
                if (i % divisors[j] == 0)
                    count++;
            if (count == K - 1)
                return i;
        }
        return -1;
    }
};

SRM207

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

BFS.

• A table is given.
• The knight can jump from one cell to some of its neighbors.
• The cost of passing from a cell to another is always 1 (just one jump).
• You need to find the minimum number of steps (jumps).

Source Code:

//Fri May 20 16:03:23 CDT 2011
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

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

class CaptureThemAll {
private:
    int grid[8][8];
public:
    int fastKnight(string knight, string rook, string queen) {
        int k2r = bfs(knight, rook);
        int k2q = bfs(knight, queen);
        int r2q = bfs(rook, queen);
        cout << k2r << ", " << k2q << ", " << r2q << endl;
        return min(k2r, k2q) + r2q;
    }

    int bfs(string a, string b) {
        int x1 = a[0] - 'a';
        int y1 = a[1] - '1';
        int x2 = b[0] - 'a';
        int y2 = b[1] - '1';
//      cout << "String b:" << x2 << ", " << y2 << endl;
        init(-1);
        grid[x1][y1] = 0;
        queue<pair<int, int> > q;
        q.push(make_pair(x1, y1));
        while (q.empty() == false) {
            x1 = q.front().first;
            y1 = q.front().second;
            q.pop();
            for (int i = 0; i < 8; i++) {
                int xx = x1 + dx[i];
                int yy = y1 + dy[i];
                if (checkBound(xx, yy) && grid[xx][yy] == -1) {
//                  cout << xx << ", " << yy << endl;
                    q.push(make_pair(xx, yy));
                    grid[xx][yy] = grid[x1][y1] + 1;
                    if (xx == x2 && yy == y2)
                        return grid[xx][yy];
                }
            }
        }
        return grid[x2][y2];
    }

    bool checkBound(int x, int y) {
        if (x < 0 || x >= 8)
            return false;
        if (y < 0 || y >= 8)
            return false;
        return true;
    }

    void init(int k) {
        memset(grid, k, sizeof(grid));
    }
};

Division Two - Level Two:

Solution

Source Code:

Division Two - Level One:

Solution

Source Code:

//2009/08/13 19:21:15
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class TransportCounting
{
public:
    int countBuses(int speed, vector <int> positions, vector <int> velocities, int time)
    {
        int count = 0;
        int ours = speed * time;
        for(int i=0; i<positions.size(); i++)
        {
            if(positions[i] == 0)
            {
                count ++;
                continue;
            }
            else if(positions[i] + time * velocities[i] <= ours) count ++;
        }
        return count;
    }
};

SRM233

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

Breadth First Search (BFS).
Problem hints:

• Words can be considered as states. There are at most 26^4 different words composed of 4 letters (thus a linear complexity will run in allowed time).
• There are some ways to pass from one state to another.
• The cost of passing from a state to another is always 1 (i.e. a single button click).
• You need to find the minimum number of steps required to reach the end state from start state.

Source Code:

//Thu May 19 11:12:55 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

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

class State {
public:
    int a;
    int b;
    int c;
    int d;
    State(string s) {
        this->a = s[0] - 'a';
        this->b = s[1] - 'a';
        this->c = s[2] - 'a';
        this->d = s[3] - 'a';
    }
    State(int aa, int bb, int cc, int dd) {
        this->a = aa;
        this->b = bb;
        this->c = cc;
        this->d = dd;
    }
    bool equals(State s) {
        return this->a == s.a && this->b == s.b && this->c == s.c && this->d
                == s.d;
    }
};

class SmartWordToy {

private:
    bool forbiden[26][26][26][26];
    int cost[26][26][26][26];
public:
    int minPresses(string start, string finish, vector<string> forbid) {
        init(forbid);
        //      if (forbiden[start[0] - 'a'][start[1] - 'a'][start[2] - 'a'][start[3]
        //              - 'a'])
        //          return -1;
        State st(start);
        cost[start[0] - 'a'][start[1] - 'a'][start[2] - 'a'][start[3] - 'a']
                = 0;
        queue<State> q;
        q.push(st);
        while (!q.empty()) {
            int a = q.front().a;
            int b = q.front().b;
            int c = q.front().c;
            int d = q.front().d;
            int dist = cost[a][b][c][d];
            q.pop();
            for (int i = 0; i < 8; i++) {
                int x = (a + dx[i] + 26) % 26;
                int y = (b + dy[i] + 26) % 26;
                int z = (c + dz[i] + 26) % 26;
                int w = (d + dw[i] + 26) % 26;
                State tmpST(x, y, z, w);
                if (forbiden[x][y][z][w] || cost[x][y][z][w] != -1)
                    continue;
                cost[x][y][z][w] = dist + 1;
                q.push(tmpST);
            }
        }
        return cost[finish[0] - 'a'][finish[1] - 'a'][finish[2] - 'a'][finish[3]
                - 'a'];
    }

    void init(vector<string> f) {
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                for (int p = 0; p < 26; p++) {
                    for (int q = 0; q < 26; q++) {
                        forbiden[i][j][p][q] = false;
                        cost[i][j][p][q] = -1;
                    }
                }
            }
        }
        for (int i = 0; i < (int) f.size(); i++) {
            vector<string> tmp = split(f[i]);
            for (int a = 0; a < (int) tmp[0].size(); a++) {
                for (int b = 0; b < (int) tmp[1].size(); b++) {
                    for (int c = 0; c < (int) tmp[2].size(); c++) {
                        for (int d = 0; d < (int) tmp[3].size(); d++) {
                            forbiden[tmp[0][a] - 'a'][tmp[1][b] - 'a'][tmp[2][c]
                                    - 'a'][tmp[3][d] - 'a'] = true;

                        }
                    }
                }
            }
        }
    }

    vector<string> split(string s) {
        vector<string> ret;
        stringstream ss(s);
        while (ss >> s) {
            ret.push_back(s);
        }
        return ret;
    }
};

Division One - Level One:

Solution

Same with Div2, Level2.

Source Code:

Division Two - Level Three:

Solution

Source Code:

Division Two - Level Two:

Solution

All cuts / C(N,2).

Source Code:

//SRM233Div2_500;
//SRM233DIV1_250;
//2009/10/23 16:28:28
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class PipeCuts
{
public:
    double probability(vector <int> weldLocations, int L)
    {
        int count = 0;
        sort(weldLocations.begin(), weldLocations.end());
        for(int i=0; i<weldLocations.size(); i++)
        {
            for(int j=i+1; j<weldLocations.size(); j++)
                if((weldLocations[j]-weldLocations[i]>L) || weldLocations[i]>L || (100-weldLocations[j])>L)
                    count ++;
        }
        return 2.0 * count / ((weldLocations.size()-1) * weldLocations.size());
    }
};

Division Two - Level One:

Solution

Source Code:

//2009/08/15 18:43:18
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class JustifyText
{
public:
    vector <string> format(vector <string> text)
    {
        int sz = 0;
        vector<string> ret;
        for(int i=0; i<text.size(); i++) sz = max((int)text[i].size(), sz);
        for(int i=0; i<text.size(); i++)
        {
            string s(sz-text[i].size(), ' ');
            ret.push_back(s+text[i]);
        }
        return ret;
    }
};

TCO11 Qualification Round 2

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Ad-hoc;

Source Code:

//Thu May 19 05:37:47 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class BlackWhiteMagic {
public:
    int count(string creatures) {
        int ret = 0;
        for (int i = 0; i < creatures.size(); i++) {
            if (creatures[i] == 'B') {
                int found = creatures.find_last_of('W');
//              cout << found << endl;
                if (found >= 0 && found > i) {
                    ret++;
                    creatures[i] = 'W';
                    creatures[found] = 'B';
                }
            }
        }
        return ret;
    }
};

SRM506

Summary:
Don't know how to solve level three, also the programming speed is too slow.
My rate has been improved, also I am a green man now... Happy.

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

Same to the Div2, Level Two.

Source Code:

Division Two - Level Three:

Solution

Source Code:

Division Two - Level Two:

Solution

Sort, find any combination of part of array, the sum would no less than the other part. Just go through each element, then check it. PS: 1st, add the one if they are the same. 2nd, add the one if it's less than the upgraded element.

Source Code:

//Wed May 11 19:58:39 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class SlimeXSlimesCity {
public:
    int merge(vector<int> population) {
        int N = population.size();
        long long sum = 0;
        for (int i = 0; i < N; i++) {
            v.push_back(make_pair(population[i], i));
            sum += population[i];
        }
        sort(v.begin(), v.end());
        int count = 0;
        for (int i = 0; i < N; i++) {
            int p;
            for (p = 0; p < N; p++) {
                if (v[p].second == i)
                    break;
            }
            long long tmp = 0;
            for (int k = 0; k < N; k++) {
                if (tmp >= v[k].first || v[k].first <= v[p].first)
                    tmp += v[k].first;
                else
                    break;
            }
            if (tmp * 2 >= sum)
                count++;
        }
        return count;
    }
private:
    vector<pair<int, int> > v;
};

Division Two - Level One:

Solution

Only operations are stay the same or increase some amount of number. Thus, sort the array, then sum all the difference between the maximum and each element.

Source Code:

//Wed May 11 19:58:39 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class SlimeXSlimeRancher2 {
public:
    int train(vector<int> attributes) {
        sort(attributes.begin(), attributes.end());
        int sum = 0;
        for(int i=0; i<attributes.size(); i++)
            sum += attributes[attributes.size()-1] - attributes[i];
        return sum;
    }
};