Binomial Coefficient

Problem:

The number of ways to choose m items from n items can be presented as (n, m),
which is n! / ((n-m)! * m!), if you calculate directly by factoring it, it either will take you tons of time to compute it, or it may cause arithmetic overflow.

Solution:

So there is an easy and more secure way to calculate it.

(n, m) = (n-1, m-1) + (n-1, m).

This can be explains as :

Consider whether the n th element appears in one of the (n, m) subsets of m elements. If so, we can complete the subset by picking m−1 other items from the other n −  1. If not, we must pick all m items from the remaining n −  1.

Source Code:

/**
 * Copyright (C) 2012 Antonio081014
 */

/**
 * This is a demonstration of how to calculate binomial coefficient with dynamic
 * programming.
 * 
 * @author antonio081014
 * @time: Dec 5, 2012, 3:17:27 PM
 */
public class BinomialCoefficient {

    public static void main(String[] args) {
 BinomialCoefficient main = new BinomialCoefficient();
 main.run();
    }

    public void run() {
 System.out.println(binomial_coefficient(10, 2));
    }

    /**
     * Compute binomial_coefficient, choose m from n.
     * 
     * @param n
     *            The total number of items could be selected.
     * @param The
     *            number of item to select.
     * @return binomial coefficient.
     */
    public long binomial_coefficient(int n, int m) {
 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];
     }
 return table[n][m];
    }

}

Next Permutation in Java

Problem:

Generate the next permutation of the current array.

Solution:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.

Ref. wiki link.

Source Code:

/**
 * 
 */

/**
 * @author antonio081014
 * @time: Oct 27, 2012, 10:13:11 AM
 */
public class Solution {

    /**
     * @param args
     */
    public static void main(String[] args) {
 Solution main = new Solution();
 int[] array = { 1, 2, 3, 4, 5 };
 main.print(array);
 main.next_permutation(array);
 main.print(array);
 main.next_permutation(array);
 main.print(array);
 main.next_permutation(array);
 main.print(array);
 System.exit(0);
    }

    public void print(int[] array) {
 for (int tmp : array) {
     System.out.print(" " + tmp);
 }
 System.out.println();
    }

    public void next_permutation(int[] array) {
 int i, j;
 // Find the largest index k such that a[k] < a[k + 1]. If no such index
 // exists, the permutation is the last permutation.
 for (i = array.length - 2; i >= 0; i--) {
     if (array[i] < array[i + 1])
  break;
 }
 if (i < 0) {
     System.out.println("End");
     return;
 }

 // Find the largest index l such that a[k] < a[l]. Since k + 1 is such
 // an index, l is well defined and satisfies k < l.
 for (j = array.length - 1; j > i; j--) {
     if (array[j] > array[i])
  break;
 }

 // Swap a[k] with a[l].
 swap(array, i++, j);

 // Reverse the sequence from a[k + 1] up to and including the final
 // element a[n].
 for (j = array.length - 1; j > i; i++, j--) {
     swap(array, i, j);
 }
    }

    public void swap(int[] array, int x, int y) {
 array[x] ^= array[y];
 array[y] ^= array[x];
 array[x] ^= array[y];
    }
}

Codechef: CodeWars 2012

Oct 24, 2012

A. Rainy Egypt          Solution.
B. Alice and Bob       Solution.

C. Rat Maze                Solution.
D. Chef Ash                Solution.

Tutorial

Problem 1:

Solution:

Source Code:

UVa_00156_Ananagrams.java

Problem Links:

UVa156,

Problem:

Ananagrams

Most crossword puzzle fans are used to anagrams--groups of words with the same letters in different orders--for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams, an example is QUIZ.

Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE.

Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be ``rearranged'' at all. The dictionary will contain no more than 1000 words.

Input

Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus tIeD and EdiT are anagrams. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram.

Sample input

ladder came tape soon leader acme RIDE lone Dreis peat
 ScAlE orb  eye  Rides dealer  NotE derail LaCeS  drIed
noel dire Disk mace Rob dries
#

Sample output

Disk
NotE
derail
drIed
eye
ladder
soon

Solution:

Sort.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

 public void run() throws Exception {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String str = "";
  String line = null;
  while ((line = br.readLine()) != null && line.compareTo("#") != 0) {
   str += line + " "; //make sure words are separated.
  }
  String[] list = str.split("[\\s]+");
  Arrays.sort(list);
  for (int i = 0; i < list.length; i++) {
   boolean found = false;
   for (int j = 0; j < list.length; j++) {
    if (i != j) {
     if (checkAIsRelativeAnanagram2B(list[i], list[j])) {
      found = true;
      break;
     }
    }
   }
   if (!found)
    System.out.println(list[i]);
  }
 }

 public boolean checkAIsRelativeAnanagram2B(String a, String b) {
  if (a.length() != b.length())
   return false;

  char[] charA = a.toLowerCase().toCharArray();
  char[] charB = b.toLowerCase().toCharArray();
  Arrays.sort(charA);
  Arrays.sort(charB);
  for (int i = 0; i < charA.length; i++)
   if (charA[i] != charB[i])
    return false;
  return true;
 }
}

UVa_10474_Where_is_the_Marble.java

Problem Links:

UVa10474,

Problem:

Where is the Marble?

Raju and Meena love to play with Marbles. They have got a lot of marbles with numbers written on them. At the beginning, Raju would place the marbles one after another in ascending order of the numbers written on them. Then Meena would ask Raju to find the first marble with a certain number. She would count 1...2...3. Raju gets one point for correct answer, and Meena gets the point if Raju fails. After some fixed number of trials the game ends and the player with maximum points wins. Today it's your chance to play as Raju. Being the smart kid, you'd be taking the favor of a computer. But don't underestimate Meena, she had written a program to keep track how much time you're taking to give all the answers. So now you have to write a program, which will help you in your role as Raju.

Input 

There can be multiple test cases. Total no of test cases is less than 65. Each test case consists begins with 2 integers: N the number of marbles and Q the number of queries Mina would make. The next N lines would contain the numbers written on the N marbles. These marble numbers will not come in any particular order. Following Q lines will have Q queries. Be assured, none of the input numbers are greater than 10000 and none of them are negative.
Input is terminated by a test case where N = 0 and Q = 0.

Output 

For each test case output the serial number of the case.
For each of the queries, print one line of output. The format of this line will depend upon whether or not the query number is written upon any of the marbles. The two different formats are described below:

• `x found at y', if the first marble with number x was found at position y. Positions are numbered 1, 2,..., N.
• `x not found', if the marble with number x is not present.

Look at the output for sample input for details.

Sample Input 

4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0

Sample Output 

CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3

Solution:

Sort the array, then use the binary search to find the lower bound of the search key.
The condition statement is the key part here.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

 public void run() throws Exception {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  int N = 0;
  int M = 0;
  int ncase = 0;
  do {
   ncase++;
   String[] line = br.readLine().split("\\s");
   N = Integer.parseInt(line[0]);
   M = Integer.parseInt(line[1]);
   if (M + N == 0) {
    break;
   }
   System.out.println("CASE# " + ncase + ":");
   int[] array = new int[N];
   for (int i = 0; i < N; i++)
    array[i] = Integer.parseInt(br.readLine());
   Arrays.sort(array);
   for (int i = 0; i < M; i++) {
    int x = Integer.parseInt(br.readLine());
    int pos = binary_search(x, array);
    if (pos < 0)
     System.out.println("" + x + " not found");
    else
     System.out.println("" + x + " found at " + (pos + 1));
   }
  } while (true);
 }

 /**
  * This function uses binary search to find the lower bound of the key x in
  * the sorted array;
  * 
  * For upper bound, the condition needs to be updated.
  * */
 public int binary_search(int x, int[] array) {
  int low = 0;
  int high = array.length - 1;
  while (low < high) {
   int mid = (low + high) / 2;
   if (array[mid] < x)
    low = mid + 1;
   else
    high = mid;
  }
  if (low == high && array[low] == x)
   return low;
  return -1;
 }
}

InterviewStreet: Equation.

Problem Links:

InterviewStreet:EQUATION.

Problem:

EQUATIONS (45 points)

Find the no of positive integral solutions for the equations (1/x) + (1/y) = 1/N! (read 1 by n factorial) Print a single integer which is the no of positive integral solutions modulo 1000007.

Input:
N
Output:
Number of positive integral solutions for (x,y) modulo 1000007
Constraints:
1 <= N <= 10^6
Sample Input00:
1
Sample Output00:
1

Sample Input01:

32327

Sample Output 01:

656502

Sample Input02:

40921

Sample Output 02:

686720

Solution:

No of solutions for the equation XY=N! is
(e₁+1)(e₂+1)………..(e_n+1)
where e₁,e₂…e_n are multiplicities of Prime Numbers below N.

For Ex: XY=4!
No of primes below 4= {2,3}
4!= 24= 2³*3¹
where 3 and 1 are prime multiplicities of 24.
so applying the formula (3+1)*(1+1)=8 (no of factors of 24={1,2,3,4,6,8,12,24}.

Now the equation 1⁄x+1⁄y= N! can be transformed into
(x-N!)(y-N!)=N!²
Hence No. of solutions of the above equation is
(2e₁+1)(2e₂+1)………..(2e_n+1)

Hence to solve the problem:
1) First find out the primes less than N
2) Find the prime multiplicities
3) Apply the formula.

For step two, it's not easy to have a fast solution. Compare with two methods I provided here, I still don't know how the second one could work, while the first one is definitely too slow.

Updated: This LINK greatly explains why the second method is also right.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Solution {

 private static final int MOD = 1000007;

 private boolean[] isPrime;
 private int[] multiplier;
 private List<Integer> prime;

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

 public void run() throws Exception {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  int N = Integer.parseInt(br.readLine());
  isPrime = new boolean[N + 1];
  multiplier = new int[N + 1];
  prime = new ArrayList<Integer>();
  generatePrime(N);
  // for (int i = 0; i <= N; i++)
  // System.out.println("" + i + ", " + isPrime[i]);
  generateMultiplier(N);

  long sum = 1L;
  for (int i = 1; i <= N; i++)
   if (multiplier[i] != 0) {
    sum *= (long) (2 * multiplier[i] + 1) % MOD;
    sum %= MOD;
   }
  System.out.println(sum);
 }

 public void generatePrime(int N) {
  for (int i = 2; i <= N; i++)
   if (isPrime[i] == false) {
    prime.add(i);
    for (int j = 2; j * i <= N; j++)
     isPrime[i * j] = true;
   }
 }

 public void generateMultiplier(int N) {
  // int left = 1;
  // for (int i = 1; i <= N; i++) {
  // left *= i;
  // for (int j : prime) {
  // while (left % j == 0) {
  // multiplier[j]++;
  // left /= j;
  // }
  // if (left < j) // It helps prune and save the time.
  // break;
  // }
  // }
  for (int j : prime) {
   int cpy = N;
   int e = 0;
   while (cpy != 0) {
    e += cpy / j;
    cpy /= j;
   }
   multiplier[j] = e;
  }
 }

 public boolean check(int x, int N) {

  return true;
 }

}

UVa_465_Overflow.java

Problem Links:

UVa465,

Problem:

Overflow

Write a program that reads an expression consisting of two non-negative integer and an operator. Determine if either integer or the result of the expression is too large to be represented as a ``normal'' signed integer (type integer if you are working Pascal, type int if you are working in C).

Input

An unspecified number of lines. Each line will contain an integer, one of the two operators + or *, and another integer.

Output

For each line of input, print the input followed by 0-3 lines containing as many of these three messages as are appropriate: ``first number too big'', ``second number too big'', ``result too big''.

Sample Input

300 + 3
9999999999999999999999 + 11

Sample Output

300 + 3
9999999999999999999999 + 11
first number too big
result too big

---

Source Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
 public static void main(String[] args) throws IOException {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line;
  while ((line = br.readLine()) != null) {
   String text[] = line.split(" ");
   BigInteger a = new BigInteger(text[0]);
   BigInteger b = new BigInteger(text[2]);
   BigInteger sum;
   if (text[1].equals("+"))
    sum = a.add(b);
   else
    sum = a.multiply(b);
   // BigInteger Max = new BigInteger("2147483647");
   BigInteger Max = new BigInteger(Integer.toString(Integer.MAX_VALUE));
   System.out.println(line);
   if (a.compareTo(Max) > 0)
    System.out.println("first number too big");
   if (b.compareTo(Max) > 0)
    System.out.println("second number too big");
   if (sum.compareTo(Max) > 0)
    System.out.println("result too big");
  }
 }
}

10115 - Automatic Editing

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
String[] find, replaceBy;
int i, caseNum;
while ((line = in.readLine()) != null) {
caseNum = Integer.parseInt(line);

if (caseNum == 0) {
System.exit(0);
}

find = new String[caseNum];
replaceBy = new String[caseNum];

for (i = 0; i < caseNum; i++) {
find[i] = line = in.readLine();
replaceBy[i] = line = in.readLine();
}

line = in.readLine();

for (i = 0; i < caseNum; i++) {
while (line.indexOf(find[i]) >= 0) {
line = line.replaceFirst(find[i], replaceBy[i]);
}
}

System.out.println(line);
}
}
}

Constructing All Subsets

This article is pretty similar with the previous one, which using backtracking tech to generate all of the subsets of the given set.

Result of the test case:

{  }
{  a }
{  c }
{  c a }
{  b }
{  b a }
{  b c }
{  b c a }
{  d }
{  d a }
{  d c }
{  d c a }
{  d b }
{  d b a }
{  d b c }
{  d b c a }
*************************
{  }
{  d }
{  c }
{  c d }
{  b }
{  b d }
{  b c }
{  b c d }
{  a }
{  a d }
{  a c }
{  a c d }
{  a b }
{  a b d }
{  a b c }
{  a b c d }

/**
 * @author antonio081014
 * @time: Oct 9, 2012, 5:44:20 PM
 */
public class SubSets {

 /**
  * @param args
  */
 public static void main(String[] args) {
  SubSets main = new SubSets();
  String[] s = { "d", "b", "c", "a" };
  main.subset(s);
  System.out.println("*************************");
  main.subset(new String[] { "a", "b", "c", "d" });
 }

 public void subset(String[] s) {
  int[] a = new int[s.length];
  backtrack(a, 0, s);
 }

 /*
  * The first k-1 indices is stored in a, here we need to choose the kth
  * element;
  */
 public void backtrack(int[] a, int k, String[] s) {
  // if we reach the end;
  if (is_a_solution(a, k, s)) {
   // print(a, k);
   process_solution(a, k, s);
   return;
  }

  int[] candidates = construct_candidates(a, k, s);
  // k = k + 1;
  for (int i = 0; i < candidates.length; i++) {
   a[k] = candidates[i];
   // make_move(a,k,s);
   // int[] tmp = Arrays.copyOf(a, s.length);
   backtrack(a, k + 1, s);
   // unmake_move(a,k,s);
   // a = Arrays.copyOf(tmp, s.length);

   // check if finished;
  }
 }

 public int[] construct_candidates(int[] a, int k, String[] s) {
  // Only two possibility exists;
  int[] ret = { 0, 1 };
  return ret;
 }

 /*
  * Process the permutation, which is the array of the indices;
  */
 public void process_solution(int[] a, int k, String[] s) {
  System.out.print("{ ");
  for (int i = 0; i < s.length; i++) {
   if (a[i] == 1) {
    System.out.print(" ");
    System.out.print(s[i]);
   }
  }
  System.out.println(" }");
 }

 public boolean is_a_solution(int[] a, int k, String[] s) {
  // Reach the limit, which there is no element here;
  int n = s.length;
  return k == n;
 }

 // Check the permutation indices;
 public void print(int[] a, int k) {
  for (int i = 0; i < k; i++, System.out.print(" "))
   System.out.print(a[i]);
  System.out.println();
 }
}