SRM197

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

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2 - Level 2.

Source Code:

---

Sivision Two - Level Three:

Solution

This problem is a nice chance to practice my dynamic programming skill. The dp[i][j] represents the minimum number of plus should be used by using first i digits with the sum j.
dp[i] [j] = min{dp[i][j], dp[k-1][j - tmpSum]}, which tmpSum is the number represented by the digits from k to i.
BTW, I saw lots of people using recursive solution with memorization.

Source Code:

//Sun Oct  2 14:38:54 PDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class QuickSums {
    public int minSums(String numbers, int sum) {
        int N = numbers.length();
        long[][] dp = new long[N][sum + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= sum; j++) {
                dp[i][j] = Long.MAX_VALUE - 1;
            }
        }
        for (int i = 0; i < N; i++) {
            long tmp = Long.parseLong(numbers.substring(0, i + 1));
            if (tmp <= sum)
                dp[i][(int) tmp] = 0;
            else
                break;
        }
        // for (int i = 0; i < N; i++) {
        // for (int j = 0; j <= sum; j++) {
        // System.out.print(dp[i][j]);
        // System.out.print(", ");
        // }
        // System.out.println();
        // }
        // System.out.println();
        for (int i = 0; i < N; i++) {
            for (int k = 1; k <= i; k++) {
                long tmp = Long.parseLong(numbers.substring(k, i + 1));
                if (tmp > sum)
                    continue;
                for (int j = 0; j <= sum; j++) {
                    if (j >= tmp)
                        dp[i][j] = Math.min(dp[i][j],
                                dp[k - 1][j - (int) tmp] + 1);
                }
            }
        }
        // for (int i = 0; i < N; i++) {
        // for (int j = 0; j <= sum; j++) {
        // System.out.print(dp[i][j]);
        // System.out.print(", ");
        // }
        // System.out.println();
        // }
        if (dp[N - 1][sum] == Long.MAX_VALUE - 1)
            return -1;
        return (int) dp[N - 1][sum];
    }
    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

Source Code:

//Fri Jun  3 10:02:38 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;

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

class GeneralChess {
public:
    vector <string> attackPositions(vector <string>);
    vector<pair<int, int> > pos;
};

vector <string> GeneralChess::attackPositions(vector <string> p) {
    stringstream s(p[0]);
    int x, y;
    char c;
    s >> x >> c >> y;
    for(int i=0; i<8; i++){
        pos.push_back(make_pair(x+dx[i], y+dy[i]));
    }
    for(int j=1; j<p.size(); j++){
        stringstream ss(p[j]);
        ss >> x >> c >> y;
//      cout << "Positions: " << x << ", " << y << endl;
        vector<pair<int, int> > tmp;
        for(int i=0; i<8; i++){
            tmp.push_back(make_pair(x+dx[i], y+dy[i]));
        }
        vector<pair<int, int> > tmpset;
        for(int i=0; i<pos.size(); i++){
            for(int k=0; k<tmp.size(); k++)
                if(pos[i].first == tmp[k].first && pos[i].second == tmp[k].second)
                    tmpset.push_back(pos[i]);
        }
        pos = tmpset;
    }
    sort(pos.begin(), pos.end());
    vector<string> res;
    for(int i=0; i<pos.size(); i++){
        stringstream str;
        str << pos[i].first << "," << pos[i].second;
        res.push_back(str.str());
    }
    return res;
}
<%:testing-code%>
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

//2009/08/11 15:38:11
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

class GardenHose
{
public:
    int countDead(int n, int rowDist, int colDist, int hoseDist)
    {
        int deadPlants = 0;
        for (int row=0; row<n; row++)
        {
            for (int col=0; col<n; col++)
            {
                // Try watering from ends of row.
                if ((row+1)*rowDist <= hoseDist) continue;
                if ((n-row)*rowDist <= hoseDist) continue;

                //Try watering from ends of column.
                if ((col+1)*colDist <= hoseDist) continue;
                if ((n-col)*colDist <= hoseDist) continue;
                deadPlants++;
            }
        }
        return deadPlants;
        //return max(n-2*(hose/row), 0) * max(n-2*(hose/col), 0);
    }
};