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!

Google Code Jam - Africa Qualification 2010 - Reverse Words

Problem Links:

Google Code Jam.

Problem:

Problem Reverse Words

Given a list of space separated words, reverse the order of the words. Each line of text contains L letters and W words. A line will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words.

Input

The first line of input gives the number of cases, N.
N test cases follow. For each test case there will a line of letters and space characters indicating a list of space separated words. Spaces will not appear at the start or end of a line.

Output

For each test case, output one line containing "Case #x: " followed by the list of words in reverse order.

Limits

Small dataset

N = 5
1 ≤ L ≤ 25

Large dataset

N = 100
1 ≤ L ≤ 1000

Sample

Input	Output
3 this is a test foobar all your base	Case #1: test a is this Case #2: foobar Case #3: base your all

Solution:

Ad-hoc.

Source Code:

/**
 * 
 */
package com.googlecodejam.yr2010.africa.qualification;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;

/**
 * @author antonio081014
 * @time May 3, 2013, 11:26:59 PM
 */
public class B {
 public static void main(String[] args) throws Exception {
  B main = new B();
  main.run();
  System.exit(0);
 }

 private void run() throws Exception {
  BufferedReader in = new BufferedReader(new FileReader("input.in"));
  PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
  int T = Integer.parseInt(in.readLine());
  for (int t = 1; t <= T; t++) {
   out.write("Case #" + t + ": ");
   String Value = in.readLine();
   out.write(solve(Value) + "\n");
  }
  in.close();
  out.close();
 }

 private String solve(String value) {
  String[] words = value.split("\\s");
  int N = words.length;
  String ret = "";
  for (int i = N - 1; i > 0; i--)
   ret += words[i] + " ";
  ret += words[0];
  return ret;
 }
}

Google Code Jam - Africa Qualification 2010 - Store Credit

Problem Links:

Google Code Jam.

Problem:

Problem Store Credit

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

Input

The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:

• One line containing the value C, the amount of credit you have at the store.
• One line containing the value I, the number of items in the store.
• One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
• Each test case will have exactly one solution.

Output

For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Limits

5 ≤ C ≤ 1000
1 ≤ P ≤ 1000

Small dataset

N = 10
3 ≤ I ≤ 100

Large dataset

N = 50
3 ≤ I ≤ 2000

Sample

Input	Output
3 100 3 5 75 25 200 7 150 24 79 50 88 345 3 8 8 2 1 9 4 4 56 90 3	Case #1: 2 3 Case #2: 1 4 Case #3: 4 5

Solution:

Ad-hoc.

Source Code:

/**
 * 
 */
package com.googlecodejam.yr2010.africa.qualification;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;

/**
 * @author antonio081014
 * @time May 3, 2013, 9:46:01 PM
 */
public class A {

 public static void main(String[] args) throws Exception {
  A main = new A();
  main.run();
  System.exit(0);
 }

 private void run() throws Exception {
  BufferedReader in = new BufferedReader(new FileReader("input.in"));
  PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
  int T = Integer.parseInt(in.readLine());
  for (int t = 1; t <= T; t++) {
   out.write("Case #" + t + ": ");
   int Value = Integer.parseInt(in.readLine());
   int N = Integer.parseInt(in.readLine());
   int[] board = new int[N];
   String[] str = in.readLine().split("\\s");
   for (int i = 0; i < N; i++)
    board[i] = Integer.parseInt(str[i]);
   out.write(solve(board, Value) + "\n");
  }
  in.close();
  out.close();
 }

 private String solve(int[] board, int value) {
  for (int i = 0; i < board.length; i++) {
   for (int j = i + 1; j < board.length; j++) {
    if (board[i] + board[j] == value) {
     return String.format("%d %d", i + 1, j + 1);
    }
   }
  }
  return null;
 }
}

Google Code Jam - Round1 A 2013 - Manage your Energy

Problem Link:

Manage your Energy

Problem:

Problem Manage your Energy

You've got a very busy calendar today, full of important stuff to do. You worked hard to prepare and make sure all the activities don't overlap. Now it's morning, and you're worried that despite all of your enthusiasm, you won't have the energy to do all of this with full engagement.

You will have to manage your energy carefully. You start the day full of energy - E joulesof energy, to be precise. You know you can't go below zero joules, or you will drop from exhaustion. You can spend any non-negative, integer number of joules on each activity (you can spend zero, if you feel lazy), and after each activity you will regain R joules of energy. No matter how lazy you are, however, you cannot have more than E joules of energy at any time; any extra energy you would regain past that point is wasted.

Now, some things (like solving Code Jam problems) are more important than others. For the ith activity, you have a value v_i that expresses how important this activity is to you. The gain you get from each activity is the value of the activity, multiplied by the amount of energy you spent on the activity (in joules). You want to manage your energy so that your total gain will be as large as possible.

Note that you cannot reorder the activities in your calendar. You just have to manage your energy as well as you can with the calendar you have.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described by two lines. The first contains three integers: E, the maximum (and initial) amount of energy, R, the amount you regain after each activity, and N, the number of activities planned for the day. The second line contains N integers v_i, describing the values of the activities you have planned for today.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum gain you can achieve by managing your energy that day.

Limits

1 ≤ T ≤ 100.

Small dataset

1 ≤ E ≤ 5.
1 ≤ R ≤ 5.
1 ≤ N ≤ 10.
1 ≤ v_i ≤ 10.

Large dataset

1 ≤ E ≤ 10⁷.
1 ≤ R ≤ 10⁷.
1 ≤ N ≤ 10⁴.
1 ≤ v_i ≤ 10⁷.

Sample

Input	Output
3 5 2 2 2 1 5 2 2 1 2 3 3 4 4 1 3 5	Case #1: 12 Case #2: 12 Case #3: 39

In the first case, we can spend all 5 joules of our energy on the first activity (for a gain of 10), regain 2 and spend them on the second activity. In the second case, we spend 2 joules on the first activity, regain them, and spend 5 on the second. In the third case, our regain rate is equal to the maximum energy, meaning we always recover all energy after each activity - so we can spend full 3 joules on each activity.

Solution:

We need to decide the energy we should spend at every task, to decide we will first get the number of tasks after which we can get back the full energy, i.e.n = upper(E/R). Now we see if a task with higher value exists in the next n tasks, if not then we spend all energy in the current task else if we get a task with higher value at position "next", then we should try to maximize the energy for this task (represents as x), since we hope at next, the energy could be E, So, the energy we can spend at the current task
x = current energy + energy gaining while moving  – E. This is like current part + energy we could get in the future - the energy we hope to reach at position "next". Then, there are three possible x,
1st, x <= 0, that means at position "next", we could not have E to spend, so we will spend nothing at current position;
2nd, x > current energy, this is a good news, but the reality tells us we could spend energy more than we actually have at current.
3rd, 0 < x <= current energy, we could spend x energy here now.
This solution is partially from PuzzlersWorld.com. I just elaborate more about it a little bit.

Source Code:

/**
 * 
 */
package com.googlecodejam.yr2013.round1A;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.math.BigInteger;

/**
 * @author antonio081014
 * @time Apr 28, 2013, 2:28:09 PM
 */
public class B {
 BigInteger two = new BigInteger("2");

 public static void main(String[] args) throws Exception {
  B main = new B();
  main.run();
  System.exit(0);
 }

 private void run() throws Exception {
  BufferedReader in = new BufferedReader(new FileReader("input.in"));
  PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
  int T = Integer.parseInt(in.readLine());
  for (int t = 1; t <= T; t++) {
   out.write("Case #" + t + ": ");
   String[] lines = in.readLine().split("\\s");
   long E = Long.parseLong(lines[0]);
   long R = Long.parseLong(lines[1]);
   int N = Integer.parseInt(lines[2]);
   lines = in.readLine().split("\\s");
   long[] array = new long[N];
   for (int i = 0; i < N; i++) {
    array[i] = Long.parseLong(lines[i]);
   }
   String ret = solve(E, R, array);
   out.write(ret + "\n");
  }
  in.close();
  out.close();
 }

 /**
  * Solving each case;
  * */
 private String solve(long E, long R, long[] array) {
  int N = array.length;
  long current = E;
  // This is tricky.
  if (R > E)
   R = E;
  BigInteger total = new BigInteger("0");
  long n = (E + R - 1) / R;
  for (int i = 0; i < N; i++) {
   int next = nextMax(array, i, n);
   // System.out.println(next);
   // When current position holds the max value;
   if (next == -1) {
    total = total.add(new BigInteger(Long.toString(array[i]))
      .multiply(new BigInteger(Long.toString(current))));
    current = R;
   } else {
    // the next position holds the max value, so current position
    // might need to save some energy for the next position.

    // Energy could be consumed at ith;
    long x = current + (next - i) * R - E;
    if (x < 0)
     x = 0;
    if (x > current)
     x = current;
    total = total.add(new BigInteger(Long.toString(array[i]))
      .multiply(new BigInteger(Long.toString(x))));
    current = Math.min(current - x + R, E);
   }
   // System.out.println("Total: " + total.toString());
  }
  return total.toString();
 }

 /**
  * Finding the first position which holds an equal or greater value than the
  * current position, ranges from current+1 to current +n;
  * 
  * @return -1, if current position holds the maximum value. <br/>
  *         i, if ith value is the first value equal or greater than the
  *         current value.
  * */
 private int nextMax(long[] array, int current, long n) {
  for (int i = current + 1; i < array.length && i < current + 1 + n; i++) {
   if (array[i] >= array[current])
    return i;
  }
  return -1;
 }

}