## Friday, July 29, 2011

### 2004 TCO Semifinal Round 1

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

## Tutorials:

### Solution

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;
}