Google Code Jam (Qualification Round 2009): Welcome to Code Jam

URL

http://code.google.com/codejam/contest/dashboard?c=90101#s=p2

Problem

So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Input

The first line of input gives the number of test cases, N. The next N lines of input contain one test case each. Each test case is a single line of text, containing only lower-case letters and spaces. No line will start with a space, and no line will end with a space.

Output

For each test case, "Case #x: dddd", where x is the case number, and dddd is the last four digits of the answer. If the answer has fewer than 4 digits, please add zeroes at the front of your answer to make it exactly 4 digits long.

Limits

1 ≤ N ≤ 100

Small dataset

Each line will be no longer than 30 characters.

Large dataset

Each line will be no longer than 500 characters.

Sample

Input	Output
3 elcomew elcome to code jam wweellccoommee to code qps jam welcome to codejam	Case #1: 0001 Case #2: 0256 Case #3: 0000

Solution

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class WelcomeJam {
 
 private static final String str ="welcome to code jam";
 
 static String[] letter = new String[str.length()];

 public static void main(String[] args) throws IOException {
  
  
  for (int i=0; i<str.length();i++){
   letter[i]= str.substring(i,i+1);
  }
  BufferedReader r = new BufferedReader(new InputStreamReader(
    WelcomeJam.class.getResourceAsStream("/in")));
  String input = r.readLine();
  int n = Integer.valueOf(input);
  String[] inps = new String[n];
  for (int i=0;i<n;i++){
   inps[i]= r.readLine();
  }
  r.close();
  BufferedWriter w = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(new File("out"))));
  for (int i=0;i<n;i++){
   //System.out.println("String - "+i);
   String curr = inps[i];
   Map<String,TreeSet<Integer>> map = new HashMap<String,TreeSet<Integer>>();
   for (String s: letter){
    if (!map.containsKey(s)){
     map.put(s , new TreeSet<Integer>());
    }
   }
   for (int j=0;j<curr.length();j++){
    String s = curr.substring(j,j+1);
    if (map.containsKey(s)){
     map.get(s).add(j);
    }
   }
   long result =0;
   Set<Integer> set = map.get(letter[0]);
   for (Integer p:set){
    //System.out.println("Level 0 - "+p);
    result += calculate(0,p,map);
    result = result%10000;
   }
   result = result%10000;
   String out =null;
   if (result>=1000){
    out = String.valueOf(result);
   } else if (result>=100){
    out = "0"+result;
   } else if (result>=10){
    out = "00"+result;
   } else if (result>=1){
    out = "000"+result;
   } else {
    out ="0000";
   }
   w.write("Case #"+(i+1)+": "+out+"\n");
   w.flush();
  }
  w.close();
  
  
  
 }
 private static long calculate(int level,Integer position, Map<String,TreeSet<Integer>> map){
  long result=0;
  if (level == letter.length-1){
   //System.out.println("Encountered");
   result += 1;//(map.get(letter[level]).tailSet(position).size());
  } else {
   Set<Integer> set = map.get(letter[level+1]).tailSet(position);
   for (Integer p:set){
    //System.out.println("Level "+(level+1)+" - "+p);
    result = result+calculate(level+1,p,map);
   }
  }
  return result%10000;
 }

}

Google Code Jam (Qualification Round 2009): Alien Language

Reference

http://code.google.com/codejam/contest/dashboard?c=90101

Problem

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample

Input	Output
3 5 4 abc bca dac dbc cba (ab)(bc)(ca) abc (abc)(abc)(abc) (zyx)bc	Case #1: 2 Case #2: 1 Case #3: 3 Case #4: 0

Solution

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class AlienLanguage {

 /**
  * @param args
  * @throws IOException 
  */
 public static void main(String[] args) throws IOException {
  
  BufferedReader r = new BufferedReader (new InputStreamReader(AlienLanguage.class.getResourceAsStream("/in")));
  String input = r.readLine();
  String[] a = input.trim().split(" ");
  int l = Integer.valueOf(a[0]);
  int d = Integer.valueOf(a[1]);
  int n = Integer.valueOf(a[2]);
  String[] inps = new String[d];
  for (int i=0;i<d;i++){
   inps[i] = r.readLine();
  }
  String[] pats = new String[n];
  for (int i=0;i<n;i++){
   pats[i] = r.readLine();
   pats[i]=pats[i].replace('(', '[').replace(')', ']');
  }
  r.close();
  //System.out.println(Arrays.asList(inps));
  //System.out.println(Arrays.asList(pats));
  int[] result = new int[n];
  for (int i=0;i<n;i++){
   for (int j=0;j<d;j++){
    if (inps[j].matches(pats[i])){
     result[i]++;
    }
   }
  }
  BufferedWriter w = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(new File("out"))));
  for (int i=0;i<n;i++){
   w.write("Case #"+(i+1)+": "+result[i]+"\n");
  }
  w.close();

 }

}

TopCoder: UserName

URL http://www.topcoder.com/stat?c=problem_statement&pm=2913&rd=5849 Problem Statement
	You are implementing the member registration system of an online dating site. When a new member signs up, it is possible that she initially chooses the same username as an existing member. The system must then inform the new member of the conflict and suggest a variant of the chosen name with a number attached to the end. If an existing member is named "FunkyMonkey", for example, and a new member wants the same username, the simplest suggestion the system can make is "FunkyMonkey1". If there is already a member by that name, the system must suggest "FunkyMonkey2", unless that variant is also taken. If all names from "FunkyMonkey1" through "FunkyMonkey9" are taken as well as the original "FunkyMonkey", the system moves on to consider "FunkyMonkey10", and so on. The goal is to use the smallest possible number in the variant. Note that each username consists of letters (the characters from 'a' to 'z' and from 'A' to 'Z') and numerals ('0' to '9'). You are given a String[], existingNames, containing all usernames that have already been registered in the system. You are also given a single String, newName, containing the username that a new member wants to use. In the event of a conflict, this member will accept the suggestion offered by your system in accordance with the principles above. Return a String containing the username finally assigned to the new member.
Definition
	Class: UserName Method: newMember Parameters: String[], String Returns: String Method signature: String newMember(String[] existingNames, String newName) (be sure your method is public)
Notes
-	The constraints rule out names that end in a number with a leading zero, such as "grokster006" and "bart0".
Constraints
-	existingNames contains between 1 and 50 elements, inclusive
-	each element of existingNames is between 1 and 50 characters long, inclusive
-	the only characters permitted in elements of existingNames are 'a' to 'z', 'A' to 'Z', and '0' to '9'
-	no element of existingNames ends in a number that has a leading zero
-	newName is between 1 and 50 characters long, inclusive
-	the only characters permitted in newName are 'a' to 'z' and 'A' to 'Z'
Examples
0)
	{"MasterOfDisaster", "DingBat", "Orpheus", "WolfMan", "MrKnowItAll"} "TygerTyger" Returns: "TygerTyger" "TygerTyger" is available.
1)
	{"MasterOfDisaster", "TygerTyger1", "DingBat", "Orpheus", "TygerTyger", "WolfMan", "MrKnowItAll"} "TygerTyger" Returns: "TygerTyger2" "TygerTyger" and "TygerTyger1" are taken.
2)
	{"TygerTyger2000", "TygerTyger1", "MasterDisaster", "DingBat", "Orpheus", "WolfMan", "MrKnowItAll"} "TygerTyger" Returns: "TygerTyger" There are higher-numbered variants of "TygerTyger", but the base name is available.
3)
	{"grokster2", "BrownEyedBoy", "Yoop", "BlueEyedGirl", "grokster", "Elemental", "NightShade", "Grokster1"} "grokster" Returns: "grokster1" Note that "Grokster1" is not the same as "grokster1".
4)
	{"Bart4", "Bart5", "Bart6", "Bart7", "Bart8", "Bart9", "Bart10", "Lisa", "Marge", "Homer", "Bart", "Bart1", "Bart2", "Bart3", "Bart11", "Bart12"} "Bart" Returns: "Bart13"

Solution

import java.util.*;
public class UserName{
 
 public String newMember(String[] existingNames, String newName){
  String regex = "^"+newName+"[0-9]*$";
  List<String> abc =new ArrayList<String>();
  List<Integer> xyz =new ArrayList<Integer>();
  for (String a: existingNames){
   if (a.matches(regex)) {
    abc.add(a);
    xyz.add(new Integer(a.replace(newName,"0")));
   }
  }
  if (abc.size()==0 || !abc.contains(newName)){
   return newName;
  }
  //Collections.sort(abc);
  Collections.sort(xyz);
  for (int i=0;i<xyz.size();i++){
   if (xyz.get(i)!=i){
    return newName+(i==0?"":i);
   }
  }
  return newName+(xyz.size());
 }
 
 public static void main(String[] args){
  UserName un = new UserName();
  System.out.println(un.newMember(new String[]{"MasterOfDisaster", "DingBat", "Orpheus", "WolfMan", "MrKnowItAll"},"TygerTyger"));
  System.out.println(un.newMember(new String[]{"MasterOfDisaster", "TygerTyger1", "DingBat", "Orpheus", 
 "TygerTyger", "WolfMan", "MrKnowItAll"},"TygerTyger"));
  System.out.println(un.newMember(new String[]{"TygerTyger2000", "TygerTyger1", "MasterDisaster", "DingBat", "Orpheus", "WolfMan", "MrKnowItAll"},"TygerTyger"));
  System.out.println(un.newMember(new String[]{"grokster2", "BrownEyedBoy", "Yoop", "BlueEyedGirl", 
 "grokster", "Elemental", "NightShade", "Grokster1"},"grokster"));
  System.out.println(un.newMember(new String[]{"Bart4", "Bart5", "Bart6", "Bart7", "Bart8", "Bart9", "Bart10",
 "Lisa", "Marge", "Homer", "Bart", "Bart1", "Bart2", "Bart3",
 "Bart11", "Bart12"},"Bart"));
 }
}

TopCoder: MatchMaking

URL http://www.topcoder.com/stat?c=problem_statement&pm=2911&rd=5849 Problem Statement
	You are developing the matchmaking component of an online dating site. Prospective members must fill out a questionnaire consisting of binary questions such as Do you prefer to vacation (a) in the mountains or (b) at the seaside? and Would you rather travel (a) by plane or (b) by train? You are to match up men with women by maximizing the number of answers each couple has in common. A man and a woman have an answer in common whenever they give the same answer to the same question. Conflicts can easily arise due to numerical ties, but you will be able to resolve all such conflicts using the following procedure. Note that there will be equal numbers of men and women, with names being unique in each sex. Take the woman whose name comes earliest in lexicographic order, and consider the men with whom she has the greatest number of answers in common. Among these men, pick the one whose name comes earliest in lexicographic order. You have found the woman's best match. Remove this couple from the dating pool, and repeat the matching procedure until there are no more singles left. You are given a String[], namesWomen, containing the names of single women, and another String[], answersWomen, containing their answers. The kth element of answersWomen lists the answers of the woman whose name is the kth element of namesWomen. If there are n questions in the questionnaire, then every element of answersWomen consists of n characters, each of which is either 'a' or 'b'. The answers are always given in the fixed questionnaire order. You are similarly given the String[]s namesMen and answersMen for the single men. Lastly, you are given a String, queryWoman, containing the name of a woman. Return the name of the man to whom she is matched after you have formed all couples according to the above rules.
Definition
	Class: MatchMaking Method: makeMatch Parameters: String[], String[], String[], String[], String Returns: String Method signature: String makeMatch(String[] namesWomen, String[] answersWomen, String[] namesMen, String[] answersMen, String queryWoman) (be sure your method is public)
Notes
-	Lexicographic order is like dictionary order, with the difference that case matters. All uppercase letters take precedence over all lowercase letters. Thus, "boolean" comes before "boot"; "boo" comes before "boolean"; "Boot" comes before "boo"; "Zoo" comes before "boo".
Constraints
-	namesWomen contains between 1 and 50 elements, inclusive
-	if namesWomen consists of n elements, then answersWomen, namesMen, and answersMen consist of n elements each
-	each element of namesWomen and each element of namesMen is between 1 and 50 characters long, inclusive
-	the only characters that may appear in namesMen and namesWomen are 'a' to 'z' and 'A' to 'Z'
-	no two elements of namesWomen are alike
-	no two elements of namesMen are alike
-	the first element of answersWomen is between 1 and 50 characters long, inclusive
-	if the first element of answersWomen consists of m characters, then each element of answersWomen and of answersMen is m characters long
-	the only characters that may appear in answersWomen and answersMen are 'a' and 'b'
-	queryWoman is one of the Strings in namesWomen
Examples
0)
	{"Constance", "Bertha", "Alice"} {"aaba", "baab", "aaaa"} {"Chip", "Biff", "Abe"} {"bbaa", "baaa", "aaab"} "Bertha" Returns: "Biff" Alice has two answers in common with Chip and three answers in common with both Abe and Biff; Abe gets lexicographic preference. Bertha also has two answers in common with Chip and three answers in common with both Abe and Biff. Since Abe has already been matched to Alice, Bertha lands Biff.
1)
	{"Constance", "Bertha", "Alice"} {"aaba", "baab", "aaaa"} {"Chip", "Biff", "Abe"} {"bbaa", "baaa", "aaab"} "Constance" Returns: "Chip" We are dealing with the same names and answers as before. Constance is the last to go. Although she has two answers in common with Abe and Biff, they are both taken. She ends up with Chip, with whom she has only one answer in common.
2)
	{"Constance", "Alice", "Bertha", "Delilah", "Emily"} {"baabaa", "ababab", "aaabbb", "bababa", "baabba"} {"Ed", "Duff", "Chip", "Abe", "Biff"} {"aabaab", "babbab", "bbbaaa", "abbbba", "abaaba"} "Constance" Returns: "Duff"
3)
	{"Constance", "Alice", "Bertha", "Delilah", "Emily"} {"baabaa", "ababab", "aaabbb", "bababa", "baabba"} {"Ed", "Duff", "Chip", "Abe", "Biff"} {"aabaab", "babbab", "bbbaaa", "abbbba", "abaaba"} "Delilah" Returns: "Chip"
4)
	{"Constance", "Alice", "Bertha", "Delilah", "Emily"} {"baabaa", "ababab", "aaabbb", "bababa", "baabba"} {"Ed", "Duff", "Chip", "Abe", "Biff"} {"aabaab", "babbab", "bbbaaa", "abbbba", "abaaba"} "Emily" Returns: "Ed"
5)
	{"anne", "Zoe"} {"a", "a"} {"bob", "chuck"} {"a", "a"} "Zoe" Returns: "bob"
6)
	{"F", "M", "S", "h", "q", "g", "r", "N", "U", "x", "H", "P", "o", "E", "R", "z", "L", "m", "e", "u", "K", "A", "w", "Q", "O", "v", "j", "a", "t", "p", "C", "G", "k", "c", "V", "B", "D", "s", "n", "i", "f", "T", "I", "l", "d", "J", "y", "b"} {"abaabbbb", "bbaabbbb", "aaabaaab", "aabbaaaa", "baabbaab", "aaababba", "bbabbbbb", "bbbabbba", "aaabbbba", "aabbbaaa", "abbabaaa", "babbabbb", "aaaaabba", "aaaabbaa", "abbbabaa", "babababa", "abbaaaaa", "bbababba", "baaaaaba", "baaaaabb", "bbbbabba", "ababbaaa", "abbbabab", "baabbbaa", "bbbaabbb", "aababbab", "ababbabb", "abbaabba", "baabbabb", "aaabaaab", "aabbbaba", "aabaaabb", "abababba", "aabbaaaa", "aabbabaa", "bababaaa", "aabaaaab", "bbbbaabb", "baaababb", "abaabbab", "aabbbaaa", "baabbaba", "bbabbbaa", "aabbbbaa", "abbbaaab", "abababbb", "ababaaba", "bababaaa"} {"f", "C", "v", "g", "Q", "z", "n", "c", "B", "o", "M", "F", "u", "x", "I", "T", "K", "L", "E", "U", "w", "A", "d", "t", "e", "R", "D", "s", "p", "q", "m", "r", "H", "j", "J", "V", "l", "a", "k", "h", "G", "y", "i", "P", "O", "N", "b", "S"} {"bbbaabab", "bbabaabb", "ababbbbb", "bbbababb", "baababaa", "bbaaabab", "abbabbaa", "bbbabbbb", "aabbabab", "abbababa", "aababbbb", "bababaab", "aaababbb", "baabbaba", "abaaaaab", "bbaababa", "babaabab", "abbabbba", "ababbbab", "baabbbab", "babbaaab", "abbbbaba", "bbabbbba", "baaabaab", "ababbabb", "abbbaabb", "bbbbaabb", "bbbaaabb", "baabbaba", "bbabaaab", "aabbbaab", "abbbbabb", "bbaaaaba", "bbbababa", "abbaabba", "bababbbb", "aabaaabb", "babbabab", "baaaabaa", "ababbaba", "aaabaabb", "bbaaabaa", "baaaaabb", "bbaabaab", "bbababab", "aabaaaab", "aaaaabab", "aabbaaba"} "U" Returns: "x"
7)
	{"q", "M", "w", "y", "p", "N", "s", "r", "a", "H", "o", "n", "F", "m", "l", "b", "D", "j", "C", "u", "f", "I", "g", "L", "i", "x", "A", "G", "O", "k", "h", "d", "c", "E", "B", "v", "J", "z", "K", "e", "t"} {"aabbaaabb", "baabababb", "bbaababba", "bbbaaaaaa", "abaaaabaa", "bababbbab", "abbaabbaa", "aabababbb", "bababaaaa", "abbababaa", "aabbbbbba", "bbabbabab", "babaabbba", "babbabbbb", "baaabbbbb", "baaabaaaa", "aaabbaaab", "abbaabbbb", "abbabbbab", "bbaaaabba", "babbaaabb", "aabbabbab", "baaababba", "ababaabab", "bbbaabbab", "aaaabbabb", "babaaaaaa", "abbbbaaab", "aabaaabba", "bbbaaaaba", "bbbbbbaab", "aabbaaabb", "aabaabbab", "aababaaba", "bbabbbbab", "abbabaaab", "babaaabbb", "bababbaaa", "aabbaabaa", "baaabbabb", "bbbbbbbbb"} {"m", "k", "n", "q", "L", "E", "M", "l", "w", "x", "g", "e", "i", "z", "F", "r", "a", "h", "f", "D", "J", "K", "j", "v", "A", "t", "N", "y", "s", "c", "o", "p", "d", "b", "B", "G", "O", "I", "u", "C", "H"} {"bbaaabbba", "bbaaaaaab", "abaaababb", "baaaabbbb", "abbbababa", "baaaaaaaa", "aabbbbbab", "aaaaabbba", "baabababb", "babaaabab", "baaababaa", "bbbbaabba", "bbaabbabb", "bbaaababb", "abbabbaba", "aababaaab", "abbbbbbaa", "aabbaabaa", "bbbaabbba", "abbabbaba", "aaabbbaaa", "bbaabaaaa", "aabababbb", "abbbbabab", "baaabbbba", "bababbbba", "aababbaab", "bbaabbaab", "bbbaaabbb", "babbbbabb", "ababababb", "babaaabab", "bbaaaaaba", "aaaaabaaa", "abbaaabbb", "bbbbababb", "baabababb", "bbaabaaaa", "aaababbbb", "abbbbbbba", "bbaabbaaa"} "o" Returns: "C"

My Solution:

import java.util.*;
public class MatchMaking{
 
 public class Person implements Comparable {
  public String name;
  public String answer;
  
  public Person(String name, String answer){
   this.name=name;
   this.answer=answer;
  }
  
  public int compareTo(Object p){
   return this.name.compareTo(((Person)p).name);
  }
  
  public String toString(){
   return name+"="+answer;
  }
  
 };
 
 public String makeMatch(String[] namesWomen, String[] answersWomen, String[] namesMen, String[] answersMen, String queryWoman){
  List<Person> man = new ArrayList<Person>();
  List<Person> woman = new ArrayList<Person>();
  for (int i=0;i<namesWomen.length;i++){
   man.add(new Person(namesMen[i],answersMen[i]));
   woman.add(new Person(namesWomen[i],answersWomen[i]));
  }
  Collections.sort(man);
  Collections.sort(woman);
  //System.out.println(man);
  //System.out.println(woman);
  while (woman.size()!=0){
   Person w = woman.get(0);
   Person m = man.get(0);
   int match =0;
   for (int i=0;i<man.size();i++){
    Person p = man.get(i);
    int mix = matchAnswer(w.answer,p.answer);
    if (match<mix) {
     match=mix;
     m=p;
    }
   }
   if (w.name.equals(queryWoman)){
    return m.name;
   } else {
    man.remove(m);
    woman.remove(w);
   }
  }
  return null;
 }
 
 public int matchAnswer(String a, String b){
  int count=0;
  for (int i=0;i<a.length();i++){
   if (a.charAt(i)==b.charAt(i)) count++;
  }
  return count;
 }
 
 public static void main(String[] args){
  MatchMaking mm = new MatchMaking();
  System.out.println(
  mm.makeMatch(new String[] {"Constance", "Bertha", "Alice"},
  new String[] {"aaba", "baab", "aaaa"},
  new String[] {"Chip", "Biff", "Abe"},
  new String[] {"bbaa", "baaa", "aaab"},
  "Bertha")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"Constance", "Bertha", "Alice"},
  new String[] {"aaba", "baab", "aaaa"},
  new String[] {"Chip", "Biff", "Abe"},
  new String[] {"bbaa", "baaa", "aaab"},
  "Constance")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"Constance", "Alice", "Bertha", "Delilah", "Emily"},
  new String[] {"baabaa", "ababab", "aaabbb", "bababa", "baabba"},
  new String[] {"Ed", "Duff", "Chip", "Abe", "Biff"},
  new String[] {"aabaab", "babbab", "bbbaaa", "abbbba", "abaaba"},
  "Constance")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"Constance", "Alice", "Bertha", "Delilah", "Emily"},
  new String[] {"baabaa", "ababab", "aaabbb", "bababa", "baabba"},
  new String[] {"Ed", "Duff", "Chip", "Abe", "Biff"},
  new String[] {"aabaab", "babbab", "bbbaaa", "abbbba", "abaaba"},
  "Delilah")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"Constance", "Alice", "Bertha", "Delilah", "Emily"},
  new String[] {"baabaa", "ababab", "aaabbb", "bababa", "baabba"},
  new String[] {"Ed", "Duff", "Chip", "Abe", "Biff"},
  new String[] {"aabaab", "babbab", "bbbaaa", "abbbba", "abaaba"},
  "Emily")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"anne", "Zoe"},
  new String[] {"a", "a"},
  new String[] {"bob", "chuck"},
  new String[] {"a", "a"},
  "Zoe")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"F", "M", "S", "h", "q", "g", "r", "N", "U", "x", "H", "P",
 "o", "E", "R", "z", "L", "m", "e", "u", "K", "A", "w", "Q",
 "O", "v", "j", "a", "t", "p", "C", "G", "k", "c", "V", "B",
 "D", "s", "n", "i", "f", "T", "I", "l", "d", "J", "y", "b"},
  new String[] {"abaabbbb", "bbaabbbb", "aaabaaab", "aabbaaaa", "baabbaab",
 "aaababba", "bbabbbbb", "bbbabbba", "aaabbbba", "aabbbaaa",
 "abbabaaa", "babbabbb", "aaaaabba", "aaaabbaa", "abbbabaa",
 "babababa", "abbaaaaa", "bbababba", "baaaaaba", "baaaaabb",
 "bbbbabba", "ababbaaa", "abbbabab", "baabbbaa", "bbbaabbb",
 "aababbab", "ababbabb", "abbaabba", "baabbabb", "aaabaaab",
 "aabbbaba", "aabaaabb", "abababba", "aabbaaaa", "aabbabaa",
 "bababaaa", "aabaaaab", "bbbbaabb", "baaababb", "abaabbab",
 "aabbbaaa", "baabbaba", "bbabbbaa", "aabbbbaa", "abbbaaab",
 "abababbb", "ababaaba", "bababaaa"},
  new String[] {"f", "C", "v", "g", "Q", "z", "n", "c", "B", "o", "M", "F",
 "u", "x", "I", "T", "K", "L", "E", "U", "w", "A", "d", "t",
 "e", "R", "D", "s", "p", "q", "m", "r", "H", "j", "J", "V",
 "l", "a", "k", "h", "G", "y", "i", "P", "O", "N", "b", "S"},
  new String[] {"bbbaabab", "bbabaabb", "ababbbbb", "bbbababb", "baababaa",
 "bbaaabab", "abbabbaa", "bbbabbbb", "aabbabab", "abbababa",
 "aababbbb", "bababaab", "aaababbb", "baabbaba", "abaaaaab",
 "bbaababa", "babaabab", "abbabbba", "ababbbab", "baabbbab",
 "babbaaab", "abbbbaba", "bbabbbba", "baaabaab", "ababbabb",
 "abbbaabb", "bbbbaabb", "bbbaaabb", "baabbaba", "bbabaaab",
 "aabbbaab", "abbbbabb", "bbaaaaba", "bbbababa", "abbaabba",
 "bababbbb", "aabaaabb", "babbabab", "baaaabaa", "ababbaba",
 "aaabaabb", "bbaaabaa", "baaaaabb", "bbaabaab", "bbababab",
 "aabaaaab", "aaaaabab", "aabbaaba"},
  "U")
  );
  
  System.out.println(
  mm.makeMatch(new String[] {"q", "M", "w", "y", "p", "N", "s", "r", "a", "H", "o", "n",
 "F", "m", "l", "b", "D", "j", "C", "u", "f", "I", "g", "L",
 "i", "x", "A", "G", "O", "k", "h", "d", "c", "E", "B", "v",
 "J", "z", "K", "e", "t"},
  new String[] {"aabbaaabb", "baabababb", "bbaababba", "bbbaaaaaa", "abaaaabaa",
 "bababbbab", "abbaabbaa", "aabababbb", "bababaaaa", "abbababaa",
 "aabbbbbba", "bbabbabab", "babaabbba", "babbabbbb", "baaabbbbb",
 "baaabaaaa", "aaabbaaab", "abbaabbbb", "abbabbbab", "bbaaaabba",
 "babbaaabb", "aabbabbab", "baaababba", "ababaabab", "bbbaabbab",
 "aaaabbabb", "babaaaaaa", "abbbbaaab", "aabaaabba", "bbbaaaaba",
 "bbbbbbaab", "aabbaaabb", "aabaabbab", "aababaaba", "bbabbbbab",
 "abbabaaab", "babaaabbb", "bababbaaa", "aabbaabaa", "baaabbabb",
 "bbbbbbbbb"},
  new String[] {"m", "k", "n", "q", "L", "E", "M", "l", "w", "x", "g", "e",
 "i", "z", "F", "r", "a", "h", "f", "D", "J", "K", "j", "v",
 "A", "t", "N", "y", "s", "c", "o", "p", "d", "b", "B", "G",
 "O", "I", "u", "C", "H"},
  new String[] {"bbaaabbba", "bbaaaaaab", "abaaababb", "baaaabbbb", "abbbababa",
 "baaaaaaaa", "aabbbbbab", "aaaaabbba", "baabababb", "babaaabab",
 "baaababaa", "bbbbaabba", "bbaabbabb", "bbaaababb", "abbabbaba",
 "aababaaab", "abbbbbbaa", "aabbaabaa", "bbbaabbba", "abbabbaba",
 "aaabbbaaa", "bbaabaaaa", "aabababbb", "abbbbabab", "baaabbbba",
 "bababbbba", "aababbaab", "bbaabbaab", "bbbaaabbb", "babbbbabb",
 "ababababb", "babaaabab", "bbaaaaaba", "aaaaabaaa", "abbaaabbb",
 "bbbbababb", "baabababb", "bbaabaaaa", "aaababbbb", "abbbbbbba",
 "bbaabbaaa"},
  "o")
  );
 }
}

TopCoder: ContiguousCacheEasy Problem

Problem Statement
	In order to make their newest microcontroller as cheap as possible, the ACME Widget Company designed it with a very simple cache. The processor is connected to a slow memory system that contains n bytes, numbered 0 to n - 1. The cache holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1. When a program reads a byte, the cache controller executes the following algorithm: Find a new range of k bytes which contains the requested byte, such that the difference between the old and new base addresses is minimized. Note that if the requested byte was already in the cache, then the base address will not change. Update the cache to the new range by reading from the memory system any bytes that are in the new range but not the old range, and discarding any bytes that were in the old range but not the new range. Return the requested byte to the program. To analyze the performance of a program, you wish to know how many bytes are read from the memory system. The numbers of the bytes that the program reads are given in addresses, in the order that they are read. When the program starts, the base address is 0.
Definition
	Class: ContiguousCacheEasy Method: bytesRead Parameters: int, int, int[] Returns: int Method signature: int bytesRead(int n, int k, int[] addresses) (be sure your method is public)
Constraints
-	n will be between 1 and 1,000,000, inclusive.
-	k will be between 1 and n, inclusive.
-	addresses will contain between 1 and 50 elements, inclusive.
-	Each element of addresses will be between 0 and n-1, inclusive.
Examples
0)
	100 5 {6, 0, 3, 20, 22, 16} Returns: 13 When the program starts, the cache holds 0-4 (all ranges are inclusive). Accessing 6 updates the range to hold 2-6, reading two bytes. Accessing 0 resets the range to 0-4, reading another two bytes. Accessing 3 has no effect, since it is already cached. Accessing 20 and then 22 causes another seven bytes to be read, and the cache to hold 18-22. Finally, accessing 16 updates the cache to hold 16-20 (the closest range to 18-22 containing 16), for another two bytes.
1)
	100 1 {0, 4, 6, 6, 4, 10} Returns: 4 When the cache only holds one byte, every access causes a read, except where the cache already held the correct byte.
2)
	1000 999 {0, 4, 123, 987, 999, 500, 0} Returns: 2 In this case, all but one byte is cached.

Solution:

public class ContiguousCacheEasy{
 public int bytesRead(int n, int k, int[] addresses){
  int reads=0;
  int base=0;
  for (int i=0;i<addresses.length;i++){
   System.out.println("base="+base+",reads="+reads);
   if (base<=addresses[i] && addresses[i]<base+k){
    continue;
   }
   if (base+k<=addresses[i]){
    int newbase=addresses[i]-k+1;
    reads+=(newbase-base>k?k:newbase-base);
    base=newbase;
   } else {
    int newbase=addresses[i];
    reads+=(base-newbase>k?k:base-newbase);
    base=newbase;
   }
  }
  return reads;
 }
 public static void main(String[] args){
  ContiguousCacheEasy cc = new ContiguousCacheEasy();
  System.out.println(cc.bytesRead(100,5,new int[]{6, 0, 3, 20, 22, 16}));
  System.out.println(cc.bytesRead(100,1,new int[]{0, 4, 6, 6, 4, 10}));
  System.out.println(cc.bytesRead(1000,999,new int[]{0, 4, 123, 987, 999, 500, 0}));
 }
}

TopCoder Problem: ZigZag

URL http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

Problem Statement A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order. Definition Class: ZigZag Method: longestZigZag Parameters: int[] Returns: int Method signature: int longestZigZag(int[] sequence) (be sure your method is public) Constraints - sequence contains between 1 and 50 elements, inclusive. - Each element of sequence is between 1 and 1000, inclusive. Examples 0) { 1, 7, 4, 9, 2, 5 } Returns: 6 The entire sequence is a zig-zag sequence. 1) { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 } Returns: 7 There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8. 2) { 44 } Returns: 1 3) { 1, 2, 3, 4, 5, 6, 7, 8, 9 } Returns: 2 4) { 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 } Returns: 8 5) { 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 249, 22, 176, 279, 23, 22, 617, 462, 459, 244 } Returns: 36

My Solution

public class ZigZag{
 public int longestZigZag(int[] sequence) {
  if (sequence.length==1) return 1;
  if (sequence.length==2) return 2;
  int[] diff = new int[sequence.length-1];
  
  for (int i=1;i<sequence.length;i++){
   diff[i-1]=sequence[i]-sequence[i-1];
  }
  int sign=sign(diff[0]);
  int count=0;
  if (sign!=0)
   count=1;
  for (int i=1;i<diff.length;i++){
   int nextsign=sign(diff[i]);
   if (sign*nextsign==-1){
    sign=nextsign;
    count++;
   }
  }
  return count+1;
 }
 
 public int sign(int a){
  if (a==0) return 0;
  return a/Math.abs(a);
 }
 public static void main(String[] args){
  ZigZag z = new ZigZag();
  System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 }));
  System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }));
  System.out.println(z.longestZigZag(new int[] { 44 }));
  System.out.println(z.longestZigZag(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9 }));
  System.out.println(z.longestZigZag(new int[] {70, 55, 13, 2, 99, 2, 80, 80, 80, 
   80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 }));
  System.out.println(z.longestZigZag(new int[] {374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
   600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
   67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
   477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
   249, 22, 176, 279, 23, 22, 617, 462, 459, 244}));
  System.out.println(z.longestZigZag(new int[] {3, 3, 3, 3, 3}));
  System.out.println(z.longestZigZag(new int[] {396, 549, 22, 819, 611, 972, 730, 638, 978, 342, 
   566, 514, 752, 871, 911, 172, 488, 542, 482, 974, 210, 474, 66, 387, 1, 872, 799, 262, 567, 
   113, 578, 308, 813, 515, 716, 905, 434, 101, 632, 450, 74, 254, 1000, 780, 633, 496, 513, 
   772, 925, 746}));
   
 }
}

Java Tricks: Converting a number from one base to another

Converting a number int n from base b(<20) to base 10

Integer.parseInt(""+n,b);

Converting a number int n from base 10 to base 2, 8 or 16

Integer.toBinaryString(n);
Integer.toOctalString(n);
Integer.toHexString(n);