SRM578

	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

This problem is pretty similar with DivTwo_LevelTwo problem, but the thing is different because the number of geese has to be even. So the problem is partitioned into two parts, group with even number of geese, and the group with odd number of geese. The answer would be #_of_way_in_even_group multiply #_of_way_in_odd_group.

For the even number group, it could be all dogs, or all geese, either. If we have x number of groups each has even number of elements, then we could make 2^x possible choices.

For the odd number group, it can't be saved until another odd number group popped up.So, we assume we have x number of odd groups, for the number of possible ways, we could choose any even number of groups from these x groups, So the answer for odd group would be The Sum of C(x, Even Number < x), so we need to calculate the sum of binomial coefficient.

For the calculation of binomial coefficient, I used the Dynamic programming again, which could save both time and precision.

For code,
1st, DFS makes each element in grids into some group, it returns the number of elements in that group.
2nd, binomial_coefficient returns the table of all coefficients will be need

Update:
Theorem: (n, 0) + (n, 2) + ... = (n, 1) + (n, 3) + ... = 2^(n - 1)

Proof: We know from binomial theorem:

(1 + x)^n = (n, 0)x^0 + (n, 1)x^1 + ... + (n, n)x^n

Putting x = 0 and -1, we get:

(n, 0) + (n, 1) + (n, 2) + (n, 3) ... = 2^n 
(n, 0) - (n, 1) + (n, 2) - (n, 3) ... = 0

By adding and subtracting (and dividing by 2) we get:

(n, 0) + (n, 2) + ... (n, n - 1) = 2^(n - 1)
(n, 1) + (n, 3) + ... (n, n) = 2^(n - 1)

This theorem could greatly improve the algorithm I used to calculate the number of possible ways to format groups with odd number of elements.

Source Code:

public class GooseInZooDivOne {
    private static final int MOD = 1000000007;
    private boolean[][] mark;

    public int count(String[] field, int dist) {
 int N = field.length;
 int M = field[0].length();
 mark = new boolean[N][M];
 long ret = 1;
 int cnt = 0;
 for (int i = 0; i < N; i++) {
     for (int j = 0; j < M; j++) {
  if (mark[i][j] || field[i].charAt(j) == '.')
      continue;
  int tmp = DFS(field, i, j, dist);
  if (tmp % 2 == 0 && tmp != 0)
      ret = (ret * 2) % MOD;
  else if (tmp % 2 == 1) {
      cnt++;
  }
     }
 }
 long sum = 0;
 long[][] table = binomial_coefficient(cnt);
 for (int i = 0; i <= cnt; i += 2)
     sum += table[cnt][i];
 sum %= MOD;
 System.out.println(cnt);
 return (int) ((ret * sum) % MOD) - 1;
    }

    public long[][] binomial_coefficient(int n) {
 long[][] table = new long[n + 1][n + 1];
 // Initialize the base case;
 for (int i = 0; i <= n; i++) {
     table[i][0] = 1;
     table[i][i] = 1;
 }

 for (int i = 1; i <= n; i++)
     for (int j = 1; j < i; j++) {
  table[i][j] = (table[i - 1][j] + table[i - 1][j - 1]) % MOD;
     }
 return table;
    }

    private int DFS(String[] field, int x, int y, int dist) {
 int N = field.length;
 int M = field[0].length();
 int cnt = 1;

 mark[x][y] = true;
 for (int i = 0; i < N; i++) {
     for (int j = 0; j < M; j++) {
  if (!mark[i][j] && field[i].charAt(j) != '.'
   && Math.abs(x - i) + Math.abs(y - j) <= dist)
      cnt += DFS(field, i, j, dist);
     }
 }
 return cnt;
    }
}
// Powered by [KawigiEdit] 2.0!

---

Sivision Two - Level Three:

Solution

Source Code:

import java.util.ArrayList;

public class WolfInZooDivTwo {
    private ArrayList<ArrayList<Integer>> checker;
    private long[][] mark;
    private int N;

    private static final int MOD = 1000000007;

    public int count(int N, String[] L, String[] R) {
 checker = new ArrayList<ArrayList<Integer>>();
 mark = new long[306][306];
 for (int i = 0; i <= 305; i++)
     for (int j = 0; j <= 305; j++)
  mark[i][j] = -1;
 this.N = N;
 for (int i = 0; i <= 305; i++)
     checker.add(new ArrayList<Integer>());
 String Left = "";
 String Right = "";
 for (int i = 0; i < L.length; i++)
     Left += L[i];
 for (int i = 0; i < R.length; i++)
     Right += R[i];
 // System.out.println(Left);
 // System.out.println(Right);
 String[] lline = Left.split("\\s+");
 String[] rline = Right.split("\\s+");
 // System.out.println(String.format("%d %d", lline.length,
 // rline.length));
 for (int j = 0; j < lline.length; j++) {
     int a = Integer.parseInt(lline[j]) + 1;
     int b = Integer.parseInt(rline[j]) + 1;
     // System.out.println(String.format("%d %d", a, b));
     checker.get(b).add(a);
 }
 return (int) solve(0, 1);
    }

    private long solve(int last, int current) {
 if (current > this.N)
     return 1;
 if (mark[last][current] != -1)
     return mark[last][current];
 boolean flag = true;
 mark[last][current] = 0;
 for (int i = 0; flag && i < checker.get(current).size(); i++) {
     int index = checker.get(current).get(i);
     if (index > last)
  flag = false;
 }
 if (flag)
     mark[last][current] = solve(last, current + 1);
 mark[last][current] += solve(current, current + 1);
 mark[last][current] %= MOD;
 return mark[last][current];
    }
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

Solution from editorial.

Source Code:

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

public class GooseInZooDivTwo
{
    private static final int MOD = 1000000007;

    private boolean[][] mark;
    private int N;
    private int M;

    public int count(String[] field, int dist) {
 N = field.length;
 M = field[0].length();
 mark = new boolean[N][M];
 int count = 0;
 for (int i = 0; i < N; i++) {
     for (int j = 0; j < M; j++) {
  if (mark[i][j])
      continue;
  if (field[i].charAt(j) == '.')
      continue;
  count++;
  DFS(field, i, j, dist);
     }
 }
 // System.out.println("Count: " + count);
 long ret = 1;
 for (int i = 0; i < count; i++) {
     ret *= 2;
     ret %= MOD;
 }
 return (int) (ret - 1);
    }

    private void DFS(String[] field, int x, int y, int dist) {
  mark[x][y] = true;
  for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
    if (!mark[i][j] && field[i].charAt(j) != '.' && Math.abs(x - i) + Math.abs(y - j) <= dist) {
        // System.out.println(String.format("Point: (%d, %d)", i,
        // j));
        DFS(field, i, j, dist);
    }
      }
  }
    }
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Ad-hoc.

Source Code:

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

public class DeerInZooDivTwo
{
 public int[] getminmax(int N, int K)
 {
  int[] ret = new int[2];
  ret[0] = Math.max(N - K, 0);
  ret[1] = N - (K+1) / 2;
  return ret;
 }
 
 
}
//Powered by [KawigiEdit] 2.0!