SRM411

	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 - 600 pts.

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Dynamic Programming, The most amazing part of this solution is use length of the string as the variable here, since how to cut the string into pieces is the most difficult problem from the start. The idea from tomek's solution is very brilliant and inspiring.

Source Code:

//
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SentenceDecomposition
{
    public final static int mmax = 1000000000;
    public Integer dp[];
    public String str;
    public String[] list;

    public int decompose(String sentence, String[] validWords)
    {
        str = sentence;
        list = validWords;
        dp = new Integer[str.length() + 1];
        int ret = solve(str.length());
        return ret==mmax? -1 : ret;
    }

    public int solve(int len){
        if(dp[len] != null) return dp[len];
        dp[len] = mmax;
        if(len == 0){
            return dp[len] = 0;
        }
        for(String s: list){
            int len2 = s.length();
            if(len2 > len) continue;
            int cost = match(s, str.substring(len-len2, len));
            if(cost == -1) continue;
            dp[len] = Math.min(dp[len], cost + solve(len-len2));
        }
        return dp[len];
    }

    public int match(String a, String b){
        String c = sorted(a);
        String d = sorted(b);
        if(c.compareTo(d) != 0) return -1;
        int ret = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i))
                ret++;
        }
        return ret;
    }

    public String sorted(String a){
        char[] content = a.toCharArray();
        Arrays.sort(content);
        String ret = new String(content);
        return ret;
    }
  
  
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

//2009/08/29 02:07:24
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <math.h>
#include <sstream>
#include <algorithm>

using namespace std;

class MaximumScoredNumber
{
public:
    int getNumber(int lowerBound, int upperBound)
    {
        int mmax = -1;
        int ret = -1;
        for(int i=upperBound; i>=lowerBound; i--)
        {
            if(mmax < score(i) || mmax == -1)
            {
                mmax = score(i);
                ret = i;
            }
        }
        return ret;
    }
    int score(int n)
    {
        int ret = 0;
        for (int i=0; i*i<=n/2; i++)
            if (issquare(n - i*i))
                ret++;
        return ret;
    }
    bool issquare(int n)
    {
        int a = (int) sqrt(n);
        if (a * a == n) return true;
        return false;
    }
};