SRM509

Summary:

Result

        For this contest, I failed completely. First, I thought my 500 problem was challenged because of TLE, but it seems my code has more errors than I thought. Second, my programming background is still not good enough. I should type faster, more accuracy, and fewer lines.

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Div 2, Level 1

Div 2, Level 2

Div 2, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

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[0][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[27][27];
    int matchCost[27][27];
    int dp[55][55];
    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);
}

//Powered by [KawigiEdit] 2.0!

Division One - Level One:

Solution

Same as Div2, Lvl 2 problem.

Source Code:

Division Two - Level Three:

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[51][51][51];
    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[0].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%>
//Powered by [KawigiEdit] 2.0!

Division Two - Level Two:

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


//Powered by [KawigiEdit] 2.0!

Division Two - Level One:

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

//Powered by [KawigiEdit] 2.0!