## Saturday, July 30, 2011

### SRM195

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

## Tutorials:

### Solution

The same with Div2 Level2.

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

## Friday, July 29, 2011

### SRM204

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

## Tutorials:

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

### 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:

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

## 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:

### Solution

Same to Div2 level 3;

### Solution

Same to Div2 level 2;

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

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

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