SRM195

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 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:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Follow the tutorials from TC, and use greedy algorithms to implement.

Source Code:

//Sat Jul 30 17:46:03 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;

class FanFailure {
public:
    vector <int> getRange(vector <int>, int);
};

vector <int> FanFailure::getRange(vector <int> cap, int minC) {
    int N = cap.size();
    sort(cap.begin(), cap.end());
    vector<int> ret(2, 0);
    ret[0] = 0;
    ret[1] = N;
   
    for(int i=0; i<=N; i++){
        int sum1 = 0;
        int sum2 = 0;
        for(int j=0; j<N; j++) if(j>=i) sum1 += cap[j];
        for(int j=0; j<N; j++) if(j<N-i) sum2 += cap[j];
        if(sum1 >= minC) ret[0] = max(ret[0], i);
        if(sum2 < minC) ret[1] = min(ret[1], i-1);
    }
    return ret;
}


//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

SRM204

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Follow the tutorials from TC, and source code of SnapDragon.

Source Code:

//Fri Jul 29 21:37:31 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;

class WorldPeace {
public:
    long long numGroups(int, vector <int>);
};

long long WorldPeace::numGroups(int k, vector <int> c) {
    long long hi = 10000000000000000LL;
    long long lo = 0LL;
    while(hi > lo){
        long long mid = (hi + lo + 1) / 2;
        long long sum = 0LL;
        for(int i=0; i<c.size(); i++){
            sum += c[i]<mid ? c[i]:mid;
        }
        if(sum < mid * k) hi = mid-1;
        else lo = mid;
    }
    return hi;
}


//Powered by [KawigiEdit] 2.0!

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Source Code:

---

Division Two - Level One:

Solution

Source Code:

//2009/08/13 18:26:45
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class Medici
{
public:
    int winner(vector <int> fame, vector <int> fortune, vector <int> secrets)
    {
        int ret = -1;
        int mmax = -1;
        bool ties = false;
        for(int i=0; i<fame.size(); i++)
        {
            int mmin = min(fame[i], min(fortune[i], secrets[i]));
            if(mmin > mmax)
            {
                mmax = mmin;
                ties = false;
                ret = i;
            }
            else if(mmin == mmax) ties = true;
        }
        if(ties) ret = -1;
        return ret;
    }
};

2004 TCO Semifinal Round 1

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Follow the tutorial on TC, link;

The most brilliant part I like is Building the frequency matrix, and using the symmetric property to simplify the problem.

Source Code:

//Fri Jul 29 12:30:28 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;

class BioScore {
public:
    vector<double> v;
    double maxAvg(vector <string>);
    int mapset(char a, char b){
        if(a=='A' && b=='A') return 0;
        if(a=='C' && b=='C') return 1;
        if(a=='G' && b=='G') return 2;
        if(a=='T' && b=='T') return 3;
        if((a=='A' && b=='C') || (a=='C' && b=='A')) return 4;
        if((a=='A' && b=='G') || (a=='G' && b=='A')) return 5;
        if((a=='A' && b=='T') || (a=='T' && b=='A')) return 6;
        if((a=='G' && b=='C') || (a=='C' && b=='G')) return 7;
        if((a=='T' && b=='C') || (a=='C' && b=='T')) return 8;
        if((a=='T' && b=='G') || (a=='G' && b=='T')) return 9;
    }
    void count(vector <string> kset){
        for(int i=0; i<kset.size(); i++){
            for(int j=i+1; j<kset.size(); j++){
                for(int k=0; k<kset[i].size(); k++){
                    v[mapset(kset[i][k], kset[j][k])]+=1.0;
                }
            }
        }
    }
    double score(vector<double> a, vector<double> b){
        double ret = 0.0;
        for(int i=0; i<a.size(); i++)
            ret += a[i]*b[i];
        return ret;
    }
};

double BioScore::maxAvg(vector <string> knownSet) {
    v.resize(10);
    count(knownSet);
    int N = knownSet.size();
    sort(v.begin(), v.begin()+4);
    reverse(v.begin(), v.begin()+4);
    sort(v.begin()+4, v.end());
    reverse(v.begin()+4, v.end());
    double ret = -10000;
    vector<double> s(10, 0.0);
    for(s[0]=1.0; s[0]<=10.0; s[0]+=1.0){
        for(s[1]=1.0; s[1]<=10.0; s[1]+=1.0){
            for(s[2]=1.0; s[2]<=10.0; s[2]+=1.0){
                for(s[3]=1.0; s[3]<=10.0; s[3]+=1.0){
                    if((int)(s[0] + s[1] + s[2] + s[3]) % 2 == 0){
                        s[4] = 10.0;
                        s[5] = 10.0;
                        s[6] = 10.0 - (s[0] + s[1] + s[2] + s[3]) / 2;
                        s[7] = -10.0;
                        s[8] = -10.0;
                        s[9] = -10.0;
                    
                        ret = max(ret, score(v, s));
                    }
                }
            }
        }
    }
    ret /= (double)(N*(N-1)/2);
    return ret;
}

//Powered by [KawigiEdit] 2.0!

---

Division One - Level One:

Solution

Source Code:

---

SRM511

Summary:

The main problem I met is I don't have any experience on game problems. I need more math knowledge and practice more.

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Same to Div2 level 3;

Source Code:

Division One - Level One:

Solution

Same to Div2 level 2;

Source Code:

Division Two - Level Three:

Solution

Source Code:

//Wed Jul  6 15:05:39 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 <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class FiveHundredEleven {
public:
    string theWinner(vector <int>);
    int N;
    vector<int> c;
    int visited[512][51];

    int winning(int mem, int played){
        if(mem==511) return 1;
        if(played==N) return 0;
        int &ret = visited[mem][played];
        if(ret != -1) return ret;
        int cnt = 0;
        for(int i=0; i<N; i++)
            if((mem | c[i]) == mem)
                cnt++;
        if(cnt > played && !winning(mem, played+1)) return ret = 1;
        for(int i=0; i<N; i++){
            if((mem | c[i]) != mem && !winning(mem|c[i], played+1))
                return ret = 1;
        }
        return ret = 0;
    }
};

string FiveHundredEleven::theWinner(vector <int> cards) {
    N = cards.size();
    c = cards;
    memset(visited, -1, sizeof(visited));
    if(winning(0, 0)) return "Fox Ciel";
    return "Toastman";
}


//Powered by [KawigiEdit] 2.0!

Division Two - Level Two:

Solution

Source Code:

//Sat Jul  2 20:32:01 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;

class Zoo {
public:
    long long theCount(vector <int>);
    map<int, int> mp;
};

long long Zoo::theCount(vector <int> ans) {
    int N = ans.size();
    sort(ans.begin(), ans.end());
    for(int i=0; i<N; i++){
        mp[ans[i]]++;
        if(mp[ans[i]] > 2) return 0;
    }
    for(int i=0; i<=40; i++){
        if(mp[i] < mp[i+1]) return 0;
    }
    int ones = 0;
    int twos = 0;
    for(int i=0; i<=40; i++){
        if(mp[i]==1) ones++;
        else if(mp[i]==2) twos++;
    }
    long long ret = 1;
    for(int i=0; i<twos; i++) ret *= 2;
    if(ones > 0) ret *= 2;
    return ret;
}

//Powered by [KawigiEdit] 2.0!

Division Two - Level One:

Solution

Source Code:

//Sat Jul  2 16:43:23 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;

class GameOfLifeDivTwo {
public:
    string theSimulation(string, int);
};

string GameOfLifeDivTwo::theSimulation(string init, int T) {
    int N = init.size();
    for(int i=0; i<T; i++){
        string tmp = "";
        for(int j=0; j<N; j++){
            int p = (j-1+N)%N;
            int q = (j+1)%N;
            int sum = (init[p]-'0')+(init[q]-'0')+(init[j]-'0');
            if(sum >=2)
                tmp+="1";
            else
                tmp +="0";
        }
        init = tmp;
    }
    return init;
}


//Powered by [KawigiEdit] 2.0!