yongpitt

/*WallGameDiv2*/

/*
Problem Statement
      
Rabbit and Eel are playing a board game. The game is played with a single token on a rectangular 
board that is divided into a grid of unit cells. Some cells contain a digit that represents the 
cost of placing the token onto that cell. Other cells contain the letter 'x' that represents a 
blocked cell. It is not allowed to place the token onto a blocked cell.

yongpitt

//DancingFoxes
/*
Problem Statement

Fox Ciel and Fox Jiro both went to spend an evening in the dancing room. Together, there are N 
foxes in the room. The foxes are numbered 0 through N-1. In particular, Ciel is fox 0 and Jiro is fox 1. 

You are given a String[] friendship that describes the initial friendship between the foxes in the room. 
More precisely, friendship contains N elements with N characters each. Character j of element i of friendship 
is 'Y' if foxes i and j are friends at the beginning of the evening, and 'N' otherwise. Note that friendship 

yongpitt

/*
KMP (Knuth–Morris–Pratt algorithm) is a nice algorithm for solving some string matching 
problems (match a pattern in a text).  CLRS book devotes a subsection for describing the 
KMP algorithm in detail. KMP leverages the longest prefix of P that is also a proper suffix 
of a string pattern to avoid redundent computations. The information is precomputed and 
represented in an  rray named prefix function, which indicates how much we should shift after 
have matched successfully at a particular shift s in the text.      
  
KMP is beautiful!  You are gonna understand it!
*/ 

yongpitt

/*This is a demonstration class for Suffix Tree data structure*/

/*
Before we move on, it's nice to learn from http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf
the basics about a suffix tree and what it does, as we have done with the Suffix Array data structure.
Don't get confused between the suffix tree data structure and other related structures. Recall that when
we learn suffix array we have a comparison among several data structures that are closely related to each
other:

       A high-level description on suffix array vs suffix tree:

yongpitt

/*This is a class for the Suffix Array Data structure with an example method to 
address the longest common substring of two strings problem using suffix array.
*/

/*  First let's learn what's a suffix array (refer to the programming pearls):

    We'll turn now to a powerful data structure and apply it to a small problem: given 
    an input file of text, find the longest duplicated substring of characters in it. 
    For instance, the longest repeated string in ``Ask not what your country can do for 
    you, but what you can do for your country'' is `` can do for you'', with `` your country'' 

yongpitt

/*Data structure: This is a simple implementation of a hash table*/
#include <iostream>
#include <string>
#include <vector>



#define DEFAULT_TABLESIZE 20897

//A more sophisiticated hash table use define various prime numers as potential table sizes.

yongpitt

/*Snapper Chain Solution (Google Code Jam Qualification Round 2010)*/
//For problem statement please go to: https://code.google.com/codejam/contest/433101/dashboard
//Easy problem. Done within 30 minutes and passed all tests.
void SnapperChain::PrintOnOff(ifstream &infile)
{
   int T, N, K;
   infile >> T;
   ofstream outfile("D:/tests/SnapperChain.out");
   for(int i=1; i<=T; i++){
      infile >> N >> K;

yongpitt

/*Theme Park Solution (Google Code Jam Qualification Round 2010)*/
//I coded this program in 1 and half hour and it took me another 30 minutes to debug and pass all the tests.
//For problem description and tests go to https://code.google.com/codejam/contest/dashboard?c=433101#s=p2
void ThemePark::PrintRevenue(ifstream &infile)
{
   int T, R, k, N;
   ofstream outfile("D:/tests/output.out");
   infile >> T;
   for(int i=1; i<=T; i++){
      infile >> R >> k >> N;

yongpitt

/*CTRL+A, CTRL+C, CTRL+V*/
/*Problem:
Imagine you have a special keyboard with the following keys:

A
Ctrl+A
Ctrl+C
Ctrl+V
where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” 
operations respectively.

yongpitt

/*Nuts in an Oasis*/
/*
Problem:
A pile of nuts is in an oasis, across a desert from a town. The pile contains ‘N’ kg of nuts, and the 
town is ‘D’ kilometers away from the pile.

The goal of this problem is to write a program that will compute ‘X’, the maximum amount of nuts that 
can be transported to the town.

The nuts are transported by a horse drawn cart that is initially next to the pile of nuts. The cart can