## Thursday, September 22, 2011

### SRM411

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

### 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] != nullreturn 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 == -1continue;
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) != 0return -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;
}

}

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