SRM311

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

Source Code:

---

Sivision Two - Level Three:

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!

---

Division Two - Level Two:

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!

---

Division Two - Level One:

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!