## Sunday, October 2, 2011

### SRM197

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 - Level 2.

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

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

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