## Monday, October 3, 2011

### SRM165

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

Here, using recursive with memorization to implement it. One thing I learned here is the compareTo function do compare the difference bits by bits first, then compare the length of the string. So I need to compare the length first here. Also, the base case for recursive solution is pretty important, take more care of that is very neccessary.

### Source Code:

//Mon Oct  3 00:08:09 PDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ShortPalindromes {

public String[][] dp;
public String str;

public String shortest(String base) {
str = base;
dp = new String[str.length() + 1][str.length() + 1];
return solve(0, str.length());
}

public String solve(int left, int right) {
if (left + 1 >= right)
return str.substring(left, right);
if (dp[left][right] != null)
return dp[left][right];
if (str.charAt(left) == str.charAt(right - 1))
return dp[left][right] = str.charAt(left)
+ solve(left + 1, right - 1) + str.charAt(left);
String s1 = str.charAt(left) + solve(left + 1, right)
+ str.charAt(left);
String s2 = str.charAt(right - 1) + solve(left, right - 1)
+ str.charAt(right - 1);
if (s1.length() < s2.length())
return dp[left][right] = s1;
else if (s1.length() > s2.length())
return dp[left][right] = s2;
else if (s1.compareTo(s2) < 0)
return dp[left][right] = s1;
else
return dp[left][right] = s2;
}

// <%:testing-code%>
}

### Source Code:

//2009/09/01 23:52:40
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class ParallelSpeedup
{
public:
{
long long mmin = -1;
int idx = -1;
for (int i=1; i<=k; i++)
{
long long temp = (long long) overhead * i * (i-1) / 2 + (k + i-1) / i;
cout << temp << endl;
if (mmin > temp || mmin == -1)
{
mmin = temp;
idx = i;
}
}
return idx;
}
};

### Source Code:

//2009/08/09 15:45:29
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

class BritishCoins
{
public:
vector <int> coins(int pence)
{
vector<int> ret;
ret.clear();
int pound = pence / 12 / 20;
pence %= 12*20;
ret.push_back(pound);
int shilling = pence / 12;
pence %= 12;
ret.push_back(shilling);
ret.push_back(pence);
return ret;
}
};