SRM165

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