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:
Division Two - Level Three:
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 2011import 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%>
}
// Powered by [KawigiEdit] 2.0!
Division Two - Level Two:
Solution
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:
int numProcessors(int k, int overhead)
{
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;
}
};
Division Two - Level One:
Solution
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;
}
};
No comments :
Post a Comment