## Thursday, September 15, 2011

### SRM311

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 3.

### Solution

Alg from Editorial, if (i, j) needed to be changed, then change (i+1, j+1) cell. This is very smart, which could change the cell without changing some cell could not be changed later.

Dynamic Programming.

### Source Code:

//Mon Sep 12 16:03:37 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class MatrixTransforming
{
public int[][] mat;

public void push(int r, int c){
for(int i=r-1; i<=r+1; i++){
for(int j=c-1; j<=c+1; j++){
mat[i][j] ^= 1;
}
}
}
public int minPushes(String[] a, String[] b)
{
int N = a.length;
int M = a[0].length();
mat = new int[N][M];
for(int i=0; i<N; i++) for(int j=0; j<M; j++) mat[i][j] = a[i].charAt(j) - '0';
int ret = 0;
for(int i=0; i+2<N; i++){
for(int j=0; j+2<M; j++){
if(mat[i][j] != b[i].charAt(j)-'0'){
push(i+1, j+1);
ret++;
}
}
}
for(int i=0; i<N; i++) for(int j=0; j<M; j++)
if(mat[i][j] != b[i].charAt(j)-'0')
return -1;
return ret;
}

}
//Powered by [KawigiEdit] 2.0!

### Solution

dp[i]: The biggest number(String) by using i matches in total.
PS: dp = new String[55]; here every element in dp will be null, instead of empty value.

Dynamic Programming.

### Source Code:

//Thu Sep 15 21:42:11 CDT 2011
import java.util.Arrays;

public class MatchNumbersEasy {
public String[] dp;

public String maxNumber(int[] matches, int n) {
int N = matches.length;
dp = new String[55];
for (int i = 1; i <= n; i++)
dp[i] = "";
for (int i = 0; i < N; i++) {
dp[matches[i]] = Integer.toString(i);
}

for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i / 2; j++) {
String tmp = dp[j] + dp[i - j];
tmp = sortReversely(tmp);
if (tmp.length() > dp[i].length() && tmp.charAt(0) != '0')
dp[i] = tmp;
else if (tmp.length() == dp[i].length()
&& tmp.compareTo(dp[i]) > 0)
dp[i] = tmp;
}
}
if (dp[n].length() == 0 || dp[n].charAt(0) == '0')
return "0";
return dp[n];
}

public static String sortReversely(String s) {
char[] temp = s.toCharArray();
Arrays.sort(temp);
String ret = new String(temp);
ret = new StringBuffer(ret).reverse().toString();
return ret;
}

}
// Powered by [KawigiEdit] 2.0!

### Solution

Very straight forward.

### Source Code:

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

public class EscapeFromRectangle
{
public int shortest(int x, int y, int w, int h)
{
int a = Math.min(Math.abs(x-w), x);
int b = Math.min(Math.abs(y-h), y);
return Math.min(a, b);
}

}
//Powered by [KawigiEdit] 2.0!