Google CodeJam 2010 : "Rope Intranet" Problem with solution

Problem

A company is located in two very tall buildings. The company intranet connecting the buildings consists of many wires, each connecting a window on the first building to a window on the second building.
You are looking at those buildings from the side, so that one of the buildings is to the left and one is to the right. The windows on the left building are seen as points on its right wall, and the windows on the right building are seen as points on its left wall. Wires are straight segments connecting a window on the left building to a window on the right building.

You've noticed that no two wires share an endpoint (in other words, there's at most one wire going out of each window). However, from your viewpoint, some of the wires intersect midway. You've also noticed that exactly two wires meet at each intersection point.
On the above picture, the intersection points are the black circles, while the windows are the white circles.
How many intersection points do you see?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing an integer N, denoting the number of wires you see.
The next N lines each describe one wire with two integers A_i and B_i. These describe the windows that this wire connects: A_i is the height of the window on the left building, and B_iis the height of the window on the right building.

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 number of intersection points you see.

Limits

1 ≤ T ≤ 15.
1 ≤ A_i ≤ 10⁴.
1 ≤ B_i ≤ 10⁴.
Within each test case, all A_i are different.
Within each test case, all B_i are different.
No three wires intersect at the same point.

Small dataset

1 ≤ N ≤ 2.

Large dataset

1 ≤ N ≤ 1000.

Sample

Input	Output
2 3 1 10 5 5 7 7 2 1 1 2 2	Case #1: 2 Case #2: 0

Solution

This is one of the simpler problems that I was able to solve in the Codejam round. Following is the source code.

private long solve(int[] a, int[] b) {
  
  PointMesh p = new PointMesh();
  
  for(int i=0;i<a.length;i++){
   p.add(a[i], b[i]);
  }
  
  return p.intersects;
 }

 class PointMesh{
  long intersects;
  List<Line2D> lineList = new ArrayList<Line2D>();
  Line2D line1 = new Line2D.Double();
  Line2D r = new Line2D.Double();  
  
  void add(int a,int b){
   Point2D p1 = new Point2D.Double(0, a);
   Point2D p2 = new Point2D.Double(10, b);
   Line2D newLine = new Line2D.Double(p1,p2);
   
   for(Line2D eachLine:lineList){
    if(eachLine.intersectsLine(newLine))
     intersects++;
   lineList.add(newLine);
  }
 }

Complete source code : here
Practice inputs : here

Cheers!!
Bragaadeesh.

Google CodeJam 2010 : "File Fix-it" Problem with solution

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.
A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:

/home/gcj/finals

This refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.
To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)
The next M lines each give the path of one directory that you want to create.
Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

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 number of mkdir you need.

Limits

1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.

Small dataset

0 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

0 ≤ N ≤ 100.
1 ≤ M ≤ 100.

Sample

Input	Output
3 0 2 /home/gcj/finals /home/gcj/quals 2 1 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b

Solution

To attack this problem we can use the famous TRIE data structure. We have already seen enough about this data structure in steps and this becomes so handy in this particular problem.
A TRIE data structure simply stores the data that becomes easy for retrieval. But lets not bother about the retrieval part in this particular problem. We will simply increase our counter whenever we add a new folder to the existing directory structure. The place where we optimize this problem involves in its running time.  Whenever we see a new directory structure, we simply pass through it in the length times instead which is linear in time jargons. The solution is given below.

private int solve(String[] already, String[] fresh) {
  Trie trieDSA = new Trie();
  
  for(int i=0;i<already.length;i++){
   trieDSA.insert(already[i],false);
  }
  
  for(int i=0;i<fresh.length;i++){
   trieDSA.insert(fresh[i], true);
  }
  
  return trieDSA.counter;
 }

So clean, isnt it? The TRIE and the Node classes are given below. Remember, please go through my TRIE data structure introduction for few minutes, its definitely a knowledgeable one! Trust me :)

class Node {
 String currentPath;
 boolean marker; 
 Collection<Node> child;
 
 public Node(String path){
  child = new HashSet<Node>();
  marker = false;
  currentPath = path;
 }
 
 public Node subNode(String path){
  if(child!=null){
   for(Node eachChild:child){
    if(eachChild.currentPath.equals(path)){
     return eachChild;
    }
   }
  }
  return null;
 }
}

class Trie{
 private Node root;
 
 public int counter = 0;

 public Trie(){
  root = new Node("");
 }

 public void insert(String pathArray, boolean shouldTrack){
  Node current = root; 
  
  String[] paths = pathArray.substring(1).split("\\/");
  
  if(paths.length==0){
   //DO NOTHING
   current.marker=true;
  }
   
   
  for(int i=0;i<paths.length;i++){
   Node child = current.subNode(paths[i]);
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(paths[i]));
    current = current.subNode(paths[i]);
    if(shouldTrack){
     counter++;
    }
   }
   // Set marker to indicate end of the word
   if(i==paths.length-1)
    current.marker = true;
  } 
 }
}

Complete source code : here
Sample Input : here

Cheers!!
Bragaadeesh.

Google CodeJam 2010 : Theme Park with Solution

Guys,

This is one of the three problems asked in the 2010 Edition of Google Codejam Qualification Round. The question is quite interesting and simple to solve and I did solve. But the problem here is the running time. If not a proper strategy is followed, then the running time of the algorithm will be more and eventually you cannot submit the answer in time for large data set. Lets look at the problem.

Problem

Roller coasters are so much fun! It seems like everybody who visits the theme park wants to ride the roller coaster. Some people go alone; other people go in groups, and don't want to board the roller coaster unless they can all go together. And everyone who rides the roller coaster wants to ride again. A ride costs 1 Euro per person; your job is to figure out how much money the roller coaster will make today.
The roller coaster can hold k people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run R times in a day.
For example, suppose R=4, k=6, and there are four groups of people with sizes: 1, 4, 2, 1. The first time the roller coaster goes, the first two groups [1, 4] will ride, leaving an empty seat (the group of 2 won't fit, and the group of 1 can't go ahead of them). Then they'll go to the back of the queue, which now looks like 2, 1, 1, 4. The second time, the coaster will hold 4 people: [2, 1, 1]. Now the queue looks like 4, 2, 1, 1. The third time, it will hold 6 people: [4, 2]. Now the queue looks like [1, 1, 4, 2]. Finally, it will hold 6 people: [1, 1, 4]. The roller coaster has made a total of 21 Euros!

 

Input

The first line of the input gives the number of test cases, T. T test cases follow, with each test case consisting of two lines. The first line contains three space-separated integers: R, k and N. The second line contains N space-separated integers g_i, each of which is the size of a group that wants to ride. g₀ is the size of the first group, g₁ is the size of the second group, etc.

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 number of Euros made by the roller coaster.

Limits

1 ≤ T ≤ 50.
g_i ≤ k.

Small dataset

1 ≤ R ≤ 1000.
1 ≤ k ≤ 100.
1 ≤ N ≤ 10.
1 ≤ g_i ≤ 10.

Large dataset

1 ≤ R ≤ 10⁸.
1 ≤ k ≤ 10⁹.
1 ≤ N ≤ 1000.
1 ≤ g_i ≤ 10⁷.

Sample

Input	Output
3 4 6 4 1 4 2 1 100 10 1 1 5 5 10 2 4 2 3 4 2 1 2 1 3	Case #1: 21 Case #2: 100 Case #3: 20

Solution

The solution for this problem may look simple and if we follow the problem as is, its pretty straight-forward. So, here is the solution that I initially arrived at,

private int solve(int R, int k, int[] groups){
  
  int moneyMade = 0;
  LinkedList<Integer> groupsQueue = new LinkedList<Integer>();
  
  for(int i=0;i<groups.length;i++){
   groupsQueue.add(groups[i]);
  }
  
  while(R>0){
   //calculate the people that can fit in
   int eachSum = 0;
   int i;
   for(i=0;i<groups.length;i++){
    eachSum+=groupsQueue.get(i);
    if(eachSum>k){
     eachSum-=groupsQueue.get(i);
     break;
    }
   }
   moneyMade+=eachSum;
   //alterQueue
   for(int j=0;j<i;j++){
    groupsQueue.add(groupsQueue.poll());
   }
   R--;
  }
  
  return moneyMade;
 }

If you look at the above solution, I have followed the problem by the word. But turned out this cannot take the large data input set simply because of the amount of time it takes to run. The mole in the above solution is that I calculate the eachSum everytime for all R iterations. The large dataset is having R upto 10^8 and Group to be 10^7. So the runtime in worst case will be 10^16 which even the fastest computers invented these days struggle to solve in small time.

So, I had to attack my problem in a different manner. All Google CodeJam problems dont have any space criterion, so its wise to make use of it. So, what would be ideal here is to precalculate the sum and extent for each group before hand. This would take a max of 10^3 * 10^3 = 10^6 iterations. The results are stored in a separate array for faster recovery.

Then iterate through the entire R once and finish the problem in constant time. The matured code is given below.

private long solve(long R, long k, long[] groups){
  int len = groups.length;
  long[] sums = new long[len];
  int[] span = new int[len];
  //irrespective of R, calculate and keep the extent and sum in separate arrays
  for(int x=0;x<len;x++){//Maximum 1000 runs
   int sum = 0; int extent=0;
   for(int y=x;;y++){
    if(sum+groups[y%len]>k || len==extent){
     break;
    }
    extent++;
    sum+=groups[y%len];
   }
   sums[x] = sum;
   span[x] = extent;
  }
  long totalSum = 0;
  int i = 0;
  for(int r=0;r<R;r++){
   totalSum += sums[i];
   i+=span[i];
   i=i%len;
  }
  return totalSum;
 }

Files you may need.
1. Input file - Small dataset
2. Input file - Large dataset
3. Output file - Small dataset
4. Output file - Large dataset
5. Complete Source code in Java

Cheers!,
Bragaadeesh.

Google CodeJam : Alien Language Problem with Solution

This is the problem asked in 2009 Google Codejam's qualification round. Lets get into business straightaway.

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
   
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Output
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

The solution for this problem is relatively simple compared to the other codejam problems that we are going to solve in the future. The solution is implemented in Perl language. It uses the regex pattern matching method.

Input file of large dataset : Download
Output file of large dataset : Download

Cheers!
Bragaadeesh