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:

---