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

## Tutorials:

### Solution

Using dfs to find all possible elements for one set of two classes.

### Source Code:

//Fri Jun 10 01:27:14 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 Marketing {
public:
long long howMany(vector <string>);
bool dfs(int x, int);
bool grid;
int type;
int N;
};

bool Marketing::dfs(int x, int b){
if(type[x] >= 0) return type[x] == b;
type[x] = b;
for(int i=0; i<N; i++){
if(grid[x][i] && dfs(i, 1-b)==false)
return false;
}
return true;
}

long long Marketing::howMany(vector <string> compete) {
memset(grid, false, sizeof(grid));
memset(type, -1, sizeof(type));
N = compete.size();
for(int i=0; i<N; i++){
stringstream s(compete[i]);
int num;
while(s >> num){
grid[i][num] = true;
grid[num][i] = true;
}
}
long long ret = 1LL;
for(int i=0; i<N; i++){
if(type[i] < 0){
//          type[i] = 0;
ret <<= 1;
if(dfs(i, 0)==false) return -1;
}
}
return ret;
}

//<%:testing-code%>

### Bases Conversion:

Convert a number in base b (2 <= b <= 10) to a decimal number:
```int toDecimal(int n, int b)
{
int result=0;
int multiplier=1;

while(n>0)
{
result+=n%10*multiplier;
multiplier*=b;
n/=10;
}

return result;
}```
Convert a decimal to a number in base b (2 <= b <= 10):
```int fromDecimal(int n, int b)
{
int result=0;
int multiplier=1;

while(n>0)
{
result+=n%b*multiplier;
multiplier*=10;
n/=b;
}

return result;
}```

## GCD: Greatest Common Divisor:

```int GCD(int a, int b)
{
if (b==0) return a;
return GCD(b,a%b);
}

int LCM(int a, int b)
{
return b*a/GCD(a,b);
}
```
Euclid's algorithm can be used to solve linear Diophantine equations. These equations have integer coefficients and are of the form:
```ax + by = c
```

## Tutorials:

### Solution

This is probably the hardest Dynamic programming problem I have done by now.
1st, need to add extra "Empty" element to deal with "add" and "erase" operation. (changeCost[i][j])
2nd, use Floyd-Warshall algorithms to optimize the cost for each operation of changing from one state to another. (matchCost[i][j])
3rd, using dynamic programming implemented with recursive to find the minimum cost from 0 to the last element. (dp[length of the array - 1]).

PS: take care of the basic cases when you deal with recursive. Here, the length could be odd or even, and also when length is even, you should think more about it. The grey marked part is pretty important for this solution.

### Source Code:

//Wed Jun 15 17:02:55 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;

const int INF = 500000001;
const int EMPTY = 26;

class PalindromizationDiv1 {
public:
int changeCost;
int matchCost;
int dp;
string word;
int rec(int, int);
int getMinimumCost(string, vector <string>);
};

int PalindromizationDiv1::rec(int a, int b){
int &ret = dp[a][b];
if(ret != -1) return ret;
if(a == b){
ret = 0;
return ret;
}

int ca = word[a] - 'a';
int cb = word[b] - 'a';
if(a == b-1) return ret = min(matchCost[ca][cb], min(rec(a+1,b) + matchCost[ca][EMPTY], rec(a,b-1) + matchCost[cb][EMPTY]));

ret = INF;

int x, y;

x = matchCost[ca][cb];
y = rec(a+1, b-1);
if(x < ret - y) ret = min(INF, x + y);

x = min(matchCost[ca][EMPTY], matchCost[EMPTY][ca]);
y = rec(a+1, b);
if(x < ret - y) ret = min(INF, x + y);

x = min(matchCost[cb][EMPTY], matchCost[EMPTY][cb]);
y = rec(a, b-1);
if(x < ret - y) ret = min(INF, x + y);

return ret;
}

int PalindromizationDiv1::getMinimumCost(string w, vector <string> op) {
memset(dp, -1, sizeof(dp));
this->word = w;

for(int i=0; i<27; i++){
for(int j=0; j<27; j++){
changeCost[i][j] = INF;
matchCost[i][j] = INF;
}
}

for(int i=0; i<27; i++){
changeCost[i][i] = 0;
}

for(int i=0; i<op.size(); i++){
stringstream s(op[i]);
string str;
char ca, cb;
s >> str >> ca;
//      cout << str << "," << ca << endl;
if(str == "add") s >> changeCost[EMPTY][ca-'a'];
else if(str == "erase") s >> changeCost[ca-'a'][EMPTY];
else {
s >> cb;
s >> changeCost[ca-'a'][cb-'a'];
}
}

for(int k=0; k<27; k++){
for(int i=0; i<27; i++){
for(int j=0; j<27; j++){
int x = changeCost[i][k];
int y = changeCost[k][j];
int &z = changeCost[i][j];
if(x < z - y) z = min(INF, x+y);
}
}
}

//  for(int i=0; i<27; i++){
//      for(int j=0; j<27; j++){
//          cout << changeCost[i][j] << ", ";
//      }
//      cout << endl;
//  }

for(int i=0; i<27; i++){
for(int j=0; j<27; j++){
for(int k=0; k<27; k++){
int x = changeCost[i][k];
int y = changeCost[j][k];
int &z = matchCost[i][j];
if(x < z - y) z = min(INF, x+y);
}
}
}

//  for(int i=0; i<27; i++){
//      for(int j=0; j<27; j++){
//          cout << changeCost[i][j] << ", ";
//      }
//      cout << endl;
//  }

int N = word.size();
int x = rec(0, N-1);
//  for(int i=0; i<N; i++) {
//      for(int j=0; j<N; j++) cout << dp[i][j] << ", ";
//      cout << endl;
//  }
return ((x>=INF)? -1 : (int)x);
}

### Solution

Same as Div2, Lvl 2 problem.

### Solution

This is a obvious BFS problem, the problem like this one will ask you the fewest steps or moves to reach some goal or point. No other tech required here.
grid[x][y][k], means the moves used to reach point(x, y) with k choices could be made left.
PS:
For this problem, the details cost me a lot of time. Minor spell errors killed my time to submit this one. Also, take care of the range of each dimension for your DP storage, which could resulted with error.

### Source Code:

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

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

class NumberLabyrinthDiv2 {
public:
int getMinimumNumberOfMoves(vector <string>, int, int, int, int, int);
bool checkBound(int x, int y);
int grid;
int M;
int N;
};

int NumberLabyrinthDiv2::getMinimumNumberOfMoves(vector <string> board, int r1, int c1, int r2, int c2, int K) {
M = board.size();
N = board.size();
memset(grid, -1, sizeof(grid));

deque<pair<pair<int, int>, int> > q;
q.push_back(make_pair(make_pair(r1, c1), K));
grid[r1][c1][K] = 0;
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int k = q.front().second;
q.pop_front();
if(r2 == x && c2 == y) continue;
if(board[x][y] == '.' ){
if(k>0)
for(int i=0; i<4; i++){
for(int j=1; j<=9; j++){
int xx = x + dx[i] * j;
int yy = y + dy[i] * j;
if(checkBound(xx, yy) && grid[xx][yy][k-1] == -1){
grid[xx][yy][k-1] = grid[x][y][k] + 1; //j;
q.push_back(make_pair(make_pair(xx, yy), k-1));
}
}
}
}
else{
int j = board[x][y] - '0';
if(j > 0)
for(int i=0; i<4; i++){
int xx = x + dx[i] * j;
int yy = y + dy[i] * j;
if(checkBound(xx, yy) && grid[xx][yy][k] == -1){
grid[xx][yy][k] = grid[x][y][k] + 1; //(board[x][y] - '0');
q.push_back(make_pair(make_pair(xx, yy), k));
}
}
}
}
int ret = -1;
for(int i=0; i<=K; i++){
if( grid[r2][c2][i]!=-1){
if(ret == -1 || grid[r2][c2][i] < ret){
ret = grid[r2][c2][i];
}
}
}
return ret;
}

bool NumberLabyrinthDiv2::checkBound(int x, int y){
return x>=0 && x<M && y>=0 && y<N;
}

//<%:testing-code%>

### Solution

Actually this is a math problem, the rem after divide by 9 is the rem of the sum of digits divide by 9, which means number % 9 == sumOfDigits(number) % 9, where sumOfDigits is the function to calculate the sum of each digits for a integer. Another property for this problem is each digit could be chosen 2^N-1 times, where N is the length of the string formatted integer, since each digit could be chosen or not chosen. Third, type conversion is also important, 1&lt&ltN is very different from 1LL&lt&ltN, the second one could convert the number to long long integer even if N is greater than 32. My code is challenged by this error.

### Source Code:

#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 LuckyRemainder {
public:
int getLuckyRemainder(string);
};

int LuckyRemainder::getLuckyRemainder(string x) {
int N = x.size();
long long sum = 0LL;
for(int j=0; j<N; j++){
sum += (1LL<<N-1) * (x[j] - '0');
sum %= 9;
}
return sum;
}

### Solution

Palindrome problems are always my favorites. For this problem, iterate from the smallest i until you find the number from subtraction is a palindrome number;
PS: another way to check the palindrome property is to check the reverse string's equality with the original one.

### Source Code:

#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 PalindromizationDiv2 {
public:
int getMinimumCost(int);
bool isP(string);
};

int PalindromizationDiv2::getMinimumCost(int X) {
for(int i = 0; ; i++){
stringstream s1;
stringstream s2;
s1 << (X+i);
s2 << (X-i);
if(isP(s1.str())){
return i;
}
if(X-i >=0 && isP(s2.str())){
return i;
}
}
return 0;
}

bool PalindromizationDiv2::isP(string s){
int i, j;
for(i=0, j=s.size()-1; i<j; i++, j--){
if(s[i] != s[j])
return false;
}
return true;
}