UVa_00457_Linear_Cellular_Automata.java

Problem Links:

uva00457,

Problem:

Linear Cellular Automata

A biologist is experimenting with DNA modification of bacterial colonies being grown in a linear array of culture dishes. By changing the DNA, he is able ``program" the bacteria to respond to the population density of the neighboring dishes. Population is measured on a four point scale (from 0 to 3). The DNA information is represented as an array DNA, indexed from 0 to 9, of population density values and is interpreted as follows:

• In any given culture dish, let K be the sum of that culture dish's density and the densities of the dish immediately to the left and the dish immediately to the right. Then, by the next day, that dish will have a population density of DNA[K].
• The dish at the far left of the line is considered to have a left neighbor with population density 0.
• The dish at the far right of the line is considered to have a right neighbor with population density 0.

Now, clearly, some DNA programs cause all the bacteria to die off (e.g., [0,0,0,0,0,0,0,0,0,0]). Others result in immediate population explosions (e.g., [3,3,3,3,3,3,3,3,3,3]). The biologist is interested in how some of the less obvious intermediate DNA programs might behave.

Write a program to simulate the culture growth in a line of 40 dishes, assuming that dish 20 starts with a population density of 1 and all other dishes start with a population density of 0.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

For each input set your program will read in the DNA program (10 integer values) on one line.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

For each input set it should print the densities of the 40 dishes for each of the next 50 days. Each day's printout should occupy one line of 40 characters. Each dish is represented by a single character on that line. Zero population densities are to be printed as the character ` '. Population density 1 will be printed as the character `.'. Population density 2 will be printed as the character `x'. Population density 3 will be printed as the character `W'.

Sample Input

1



1 2 0 1 3 3 2 3 0


0

Sample Output

bbbbbbbbbbbbbbbbbbb.bbbbbbbbbbbbbbbbbbbb


bbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbb


bbbbbbbbbbbbbbbb.bb.bb.bbbbbbbbbbbbbbbbb


bbbbbbbbbbbbbbbbb.xbx.bbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbb.........bbbbbbbbbbbbbbbb


bbbbbbbbbbbb...xxxbbbxxx...bbbbbbbbbbbbb

bbbbbbbbbbbbbb.xbbbbbbbx.bbbbbbbbbbbbbbb
bbbbbbbbbbbbb.bbxbbbbbxbb.bbbbbbbbbbbbbb
bbbbbbbbbbb.xb.WW.xbx.WW.bx.bbbbbbbbbbbb


bbbbbbbbbb.bbb.xxWb.bWxx.bbb.bbbbbbbbbbb

Note: Whe show only the first ten lines of output (the total number of lines must be 50) and the spaces have been replaced with the character "b" for ease of reading. The actual output file will use the ASCII-space character, not "b".

---

Solution:

Simple simulation.

Source Code:

import java.util.Scanner;

/**

 * @author antonio081014

 * @since Oct 27, 2011, 4:19:36 PM

 */

class Main {

    /**

     * @param args

     */

    public static void main(String[] args) throws Exception {

        // TODO Auto-generated method stub

        Scanner sc = new Scanner(System.in);

        final char[] den = { ' ', '.', 'x', 'W' };

        int[] DNA = new int[10];

        int[] current, next;

        int tests = sc.nextInt();

        int i, j, k;

        for (int test = 0; test < tests; test++) {

            for (i = 0; i < 10; i++) {

                DNA[i] = sc.nextInt();

            }

            current = new int[40];

            current[19] = 1;

            for (i = 0; i < 50; i++) {

                next = new int[40];

                for (j = 0; j < 40; j++) {

                    System.out.print(den[current[j]]);

                }

                System.out.println();

                for (j = 1; j < 39; j++) {

                    k = current[j] + current[j - 1] + current[j + 1];

                    next[j] = DNA[k];

                }

                next[0] = DNA[current[0] + current[1]];

                next[39] = DNA[current[38] + current[39]];

                current = next.clone();

            }

            if (test < tests - 1) {

                System.out.println();

            }

        }

    }

}

SRM522

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

SRM522

Tutorials:

I don't think this match worthies me 2+ hours working on that. The problems are kind of easy and too tricky. It's more like a game. Nothing really technical there.

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class CorrectMultiplicationTwo {
    public int getMinimum(int a, int b, int c) {
        int mmin = Integer.MAX_VALUE;
        for (int i = 1; i <= 3000000; i++) {
            for (int j = 1; i * j <= 3000000; j++) {
                mmin = Math.min(mmin, Math.abs(i - a) + Math.abs(j - b)
                        + Math.abs(c - i * j));
            }
        }
        return mmin;
    }
    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class RowAndManyCoins {
    public String getWinner(String cells) {
        if (cells.startsWith("A") || cells.endsWith("A"))
            return "Alice";
        return "Bob";
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class PointErasingTwo {
    public int getMaximum(int[] y) {
        int mmax = 0;
        for (int i = 0; i < y.length - 1; i++) {
            for (int j = i + 1; j < y.length; j++) {
                int ymin = Math.min(y[i], y[j]);
                int ymax = Math.max(y[i], y[j]);
                int tmp = 0;
                for (int p = 0; p < y.length; p++) {
                    if (p > i && p < j && y[p] > ymin && y[p] < ymax)
                        tmp++;
                    mmax = Math.max(mmax, tmp);
                }
            }
        }
        return mmax;
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

Interview Problem: Unique characters in a string.

Problem

Implement an algorithm to determine if a string has all unique characters.

---

Solution 1:

Using a boolean array to track the occurrence of each possible character in ASCII set. Initially every value in that array is false, until the corresponding character value appears. If that character value appears again, then if the corresponding value in array is already true, return false.
Time: O(n), n is the length of string.
Space: O(n), the array named mask.

Source Code:

/**
 * @author antonio081014
 * @since Oct 23, 2011, 5:34:50 PM
 */
public class Interview {

    // Assume every character in string is in ASCII.
    public boolean uniqueChars(String s) {
        boolean[] mask = new boolean[256];
        for (int i = 0; i < s.length(); i++) {
            if (mask[s.charAt(i)])
                return false;
            mask[s.charAt(i)] = true;
        }
        return true;
    }
}

---

Solution 2:

Here using the sorting algorithm to sort the string first, then compare every pair of neighboring characters to see if they are the same.  The main time consuming are sorting array + neighborhood comparisions. But based on the document I searched online, the sorting function in Java uses merge sort or quicksort, which depends on the data type, also for efficiency, it would switch to insertion sort when fewer than seven array elements are being sorted. So, in general,
Time: O(nlgn), n is the length of string.
Space: O(n)

Source Code:

import java.util.Arrays;
import java.util.Collections;

/**
 * @author antonio081014
 * @since Oct 23, 2011, 5:34:50 PM
 */
class Interview {

    // Assume every character in string is in ASCII.
    public boolean uniqueChars(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == chars[i + 1])
                return false;
        }
        return true;
    }
}

---

Updated Problem:

What if not use additional data structure?

Solution:

For this solution, the condition is very limited. Here I use a mask to keep the occurrence of characters with corresponding bits. E.g. 'a' occurrence will be stored at bit 0, while 'c' occurrence will be stored at bit 2. So, if mask is 4, that means 'c' has appeared before, and only 'c' has appreared. But the cons of this approach is its limited the input string could only contain continuous and easy handling characters, while the length of these characters could not be larger than log2(MAX_INT or MAX_LONG). Here, the integer value is 32-bit, so we could have this approach.

Source Code:

/**
 * @author antonio081014
 * @since Oct 23, 2011, 5:34:50 PM
 */
class Interview {

    // Assume every character in string is between a to z.
    public boolean uniqueChars(String s) {
        int mask = 0;
        for (int i = 0; i < s.length(); i++) {
            int tmp = s.charAt(i) - 'a';
            if ((mask & (1 << tmp)) > 0)
                return false;
            mask |= (1 << tmp);
        }
        return true;
    }
}

---

If you have any suggestion, improvement or error for my solution, please leave me a comment.

UVa_00400_Unix_ls.java

Problem Links:

uva00400,

Problem:

Unix ls

The computer company you work for is introducing a brand new computer line and is developing a new Unix-like operating system to be introduced along with the new computer. Your assignment is to write the formatter for the ls function.

Your program will eventually read input from a pipe (although for now your program will read from the input file). Input to your program will consist of a list of (F) filenames that you will sort (ascending based on the ASCII character values) and format into (C) columns based on the length (L) of the longest filename. Filenames will be between 1 and 60 (inclusive) characters in length and will be formatted into left-justified columns. The rightmost column will be the width of the longest filename and all other columns will be the width of the longest filename plus 2. There will be as many columns as will fit in 60 characters. Your program should use as few rows (R) as possible with rows being filled to capacity from left to right.

Input

The input file will contain an indefinite number of lists of filenames. Each list will begin with a line containing a single integer (  ). There will then be N lines each containing one left-justified filename and the entire line's contents (between 1 and 60 characters) are considered to be part of the filename. Allowable characters are alphanumeric (a to z, A to Z, and 0 to 9) and from the following set { ._- } (not including the curly braces). There will be no illegal characters in any of the filenames and no line will be completely empty.
Immediately following the last filename will be the N for the next set or the end of file. You should read and format all sets in the input file.

Output

For each set of filenames you should print a line of exactly 60 dashes (-) followed by the formatted columns of filenames. The sorted filenames 1 to R will be listed down column 1; filenames R+1 to 2R listed down column 2; etc.

Sample Input

10
tiny
2short4me
very_long_file_name
shorter
size-1
size2
size3
much_longer_name
12345678.123
mid_size_name
12
Weaser
Alfalfa
Stimey
Buckwheat
Porky
Joe
Darla
Cotton
Butch
Froggy
Mrs_Crabapple
P.D.
19
Mr._French
Jody
Buffy
Sissy
Keith
Danny
Lori
Chris
Shirley
Marsha
Jan
Cindy
Carol
Mike
Greg
Peter
Bobby
Alice
Ruben

Sample Output

------------------------------------------------------------
12345678.123         size-1               
2short4me            size2                
mid_size_name        size3                
much_longer_name     tiny                 
shorter              very_long_file_name  
------------------------------------------------------------
Alfalfa        Cotton         Joe            Porky          
Buckwheat      Darla          Mrs_Crabapple  Stimey         
Butch          Froggy         P.D.           Weaser         
------------------------------------------------------------
Alice       Chris       Jan         Marsha      Ruben       
Bobby       Cindy       Jody        Mike        Shirley     
Buffy       Danny       Keith       Mr._French  Sissy       
Carol       Greg        Lori        Peter

---

Solution:

Pretty straight forward, and the most difficulty part is to calculate the number of rows and columns correctly first.

Source Code:

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

/**
 * @author antonio081014
 * @since Oct 23, 2011, 1:42:53 PM
 */
class Main {

    /**
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        solve();
    }

    public static void solve() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strLine;
        while ((strLine = br.readLine()) != null) {
            int N = Integer.parseInt(strLine);
            List<String> list = new ArrayList<String>();
            int maxlen = 0;
            for (int i = 0; i < N; i++) {
                list.add(br.readLine());
                maxlen = Math.max(maxlen, list.get(i).length());
            }
            Collections.sort(list);
            display(list, 60, maxlen, 2);
        }
    }

    public static void display(List<String> list, int length, int maxLength,
            int offset) {
        int cols = (length + offset) / (maxLength + offset);
        int rows = (int) Math.ceil(1.0 * list.size() / cols);
        for (int i = 0; i < length; i++)
            System.out.print("-");
        System.out.println();
        for (int i = 0; i < rows; i++) {
            for (int j = i; j < list.size(); j += rows) {
                System.out.print(list.get(j));
                if (j + rows < list.size()) {
                    for (int k = list.get(j).length(); k < maxLength + offset; k++)
                        System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
}

UVa_00299_Train_Swapping.java

Problem Links:

uva00229,

Problem:

Train Swapping

At an old railway station, you may still encounter one of the last remaining ``train swappers''. A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains.
Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for which the load is meant.

The title ``train swapper'' stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right.
The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but train carriages can move either way, so who cares).
Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to be developed, is a routine which decides for a given train the least number of swaps of two adjacent carriages necessary to order the train. Your assignment is to create that routine.

Input Specification

The input contains on the first line the number of test cases (N). Each test case consists of two input lines. The first line of a test case contains an integer L, determining the length of the train (  ). The second line of a test case contains a permutation of the numbers 1 through L, indicating the current order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc. with carriage L coming last.

Output Specification

For each test case output the sentence: 'Optimal train swapping takes S swaps.' where S is an integer.

Example Input

3
3
1 3 2
4
4 3 2 1
2
2 1

Example Output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

---

Solution:

The operations the train swapper did are actually the simulation of bubble sort. Especially when the problem states the rotation operation could only take 2 carriage once with 180 degree rotated.

Source Code:

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

/**
 * @author antonio081014
 * @since Oct 23, 2011, 1:05:45 PM
 */
class Main {

    /**
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        solve();
    }

    public static void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(stk.nextToken());
            }
            System.out.println("Optimal train swapping takes "
                    + bubbleSort(nums) + " swaps.");
        }
    }

    public static int bubbleSort(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    count++;
                    nums[j] ^= nums[j + 1];
                    nums[j + 1] ^= nums[j];
                    nums[j] ^= nums[j + 1];
                }
            }
        }
        return count;
    }

}

School Regional Team Contest Saratov 2011

Date: Oct 18, 2011.

Content:
Problem A.
Problem B.
Problem C.
Problem D.
Problem E.
Problem F.
Problem G.
Problem H.
Problem I.
Problem J.

Tutorial

Problem A:

Solution:

Ad-hoc.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;

/**
 * @author antonio081014
 * @date
 */
public class A {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String str = br.readLine();
            int num = Integer.parseInt(br.readLine());
            if ((str.compareTo("front") == 0 && num == 1)
                    || (str.compareTo("back") == 0 && num == 2))
                out.write("L");
            else
                out.write("R");
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Spoj_04138_Harry_and_big_doughnuts.java

Problem Links:

Spoj04138,

Problem:

4138. Harry and big doughnuts Problem code: DOUGHNUT

Young Harry was asked to buy some foodstuff to his neighbour - weird old lady who owned a lot of fat cats. But cats were weird too and they ate only doughnuts. So the lady wanted Harry to bring exactly one doughnut to each of her pets – and she had c of them. Harry had a rucksack with him but as he was a little boy he could hump only k kilograms. Harry knew that each doughnut weights w kilograms (big cats, big doughnuts). Help him decide whether he should go to supermarket and buy the foodstuff or just give up and dream he could do some magic...

Input

There is a single positive integer t (t <= 100) on the first line of input which corresponds to the number of tests (Harry was asked to buy doughnuts few times). Then t lines follow, each containing three numbers: c, k and w (1 <= c, k, w <= 100).

t [number of tests]
c k w [number of cats, Harry's hoisting capacity and weight of doughnut]
c k w [next test case]
...

Output

t lines containing word “yes” if Harry is capable of handling the task or “no” if doughnuts would cause his spine crack.

Example

Input:
3
5 15 3
1 5 4
13 25 2

Output:
yes
yes
no

---

Solution:

ad-hoc.

Source Code:

//Sat Oct 15 12:53:57 PDT 2011
import java.io.*;
import java.util.*;

public class Main{
        public static void main(String[] args){
                try{
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                int N = Integer.parseInt(br.readLine());
                for(int i=0; i<N; i++){
                        String[] nums = br.readLine().split(" ");
                        if(Integer.parseInt(nums[0]) * Integer.parseInt(nums[2]) <= Integer.parseInt(nums[1]))
                                System.out.println("yes");
                        else
                                System.out.println("no");
                     
                }}catch(Exception e){
                        e.printStackTrace();
                }
        }
}

Spoj_00453_Sums_in_a_Triangle.java

Problem Links:
Spoj00453, Spoj06597,

Problem:

453. Sums in a Triangle (tutorial) Problem code: SUMTRIAN

This is problem SUMITR without strict source limit.

Let us consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:

• on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
• the number of rows is strictly positive, but less than 100;
• all numbers are positive integers between O and 99.

Input

In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.

Output

For each test case write the determined value in a separate line.

Example

Input:
2
3
1
2 1
1 2 3
4 
1 
1 2 
4 1 2
2 3 1 1 

Output:
5
9

---

Solution:

1st, using two arrays (滚动数组 in Chinese) technology is the key to this problem, it saves a lot of memory and also helps to implement the dynamic programming. The pros is it could use less memory to solve the problem, while it could not backtrack the path, which results the maximum.
2nd, the trick I use is if the previous sum is 0 or not, which is the initial value for the declaration.
3rd, using stringtokenizer to split the string is much faster than the string.split API function. It took me 3 or 4 TLE to prove that. Also, from the blog of somebody, some research people did showed the same results.
4th, as the StringTokenizer return the next available element, the countTokens() will decrease. This problem take me more than 1 hour to figure it out.

Source Code:


//Fri Oct 14 20:09:41 PDT 2011
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(
                    System.in));
            int N = Integer.parseInt(br.readLine());
            for (int i = 0; i < N; i++) {
                int n = Integer.parseInt(br.readLine().trim());
                int[][] nums = new int[2][n];
                int mmax = 0;
                for (int j = 0; j < n; j++) {
                    StringTokenizer stk = new StringTokenizer(br.readLine()
                            .trim());
                    int len = stk.countTokens();
                    for (int k = 0; k < len; k++) {
                        int tmp = Integer
                                .parseInt(stk.nextElement().toString());
                        // System.out.print(tmp + ", ");
                        if (k > 0)
                            nums[j % 2][k] = Math.max(nums[1 - j % 2][k],
                                    nums[1 - j % 2][k - 1])
                                    + tmp;
                        else
                            nums[j % 2][k] = nums[1 - j % 2][k] + tmp;
                        mmax = Math.max(mmax, nums[j % 2][k]);
                        // System.out.print(tmp + ", ");
                    }
                    // System.out.println();
                }
                System.out.println();
                System.out.println(mmax);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

2011-10-13: Reverse Linked List.

One of the most basic problem is to reverse a linked list.
Problem:

Reverse A Linked List.
Example:
          1 -> 2 -> 3 -> 4;
Output:
          4 -> 3 -> 2 -> 1;

	Solution 1	Solution 2	Solution 3
Time	O(2*N)	O(N)	O(N)
Memory	O(2*N)	O(2*N)	O(c = 3)

Solution 1:
Using a recursive function to implement it.
Take 1, then reverse the 2 to 4, add 1 as the end element of the linked list.
PS: I used a while loop to reach the end of linked list, or the node will add as the next element of newNode.

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Node root = new Node(1);
        root.next = new Node(2);
        root.next.next = new Node(3);
        root.next.next.next = new Node(4);
        Node newRoot = root.reverse();
        while (newRoot != null) {
            System.out.println(newRoot.data);
            newRoot = newRoot.next;
        }
    }
}

class Node {
    public int data;
    public Node right;

    public Node(int data) {
        this.data = data;
    }

    public Node reverse() {
        return reverse(this);
    }

    private Node reverse(Node node) {
        if (node.right == null)
            return node;
        Node newNode = reverse(node.right);
        node.right = null;
        Node next = newNode;
        while (next.next != null)
            next = next.next;
        next.next = node;
        return newNode;
    }
}
Solution 2:
Compare to the reverse function above, I used another node to restore the next node, so I don't need to use the while loop to reach the right-most to insert the current node. Use some extra memory to have less time consuming.

class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node reverse() {
        return reverse(this);
    }

    private Node reverse(Node node) {
        if (node.next == null)
            return node;
        Node secNode = node.next;
        Node newNode = reverse(node.next);
        node.next = null;
        secNode.next = node;
        return newNode;
    }
}

Solution 3:
Using non-recursive way to solve the problem.
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node reverse() {
        return reverse(this);
    }

    private Node reverse(Node node) {
        Node prev = null;
        Node curr = node;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

SRM203

	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

Source Code:

---

Sivision Two - Level Three:

Solution

Using regular expressions.
It could be updated as: "((http://)?www\\.|http://)([a-zA-Z0-9]+\\.)+(com|tv|info|edu|org)"; if continious punctures are not allowed.

Source Code:

//Sun Oct  9 23:09:33 PDT 2011
public class UnLinker {
    public String clean(String text) {
        String reg = "((http://)?www\\.|http://)([a-zA-Z0-9.]+)\\.+(com|tv|info|edu|org)";
        String[] str = text.split(reg, -2);
        String ret = str[0];
        for (int i = 1; i < str.length; i++) {
            ret += "OMIT" + i + str[i];
        }
        return ret;
    }
    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

Source Code:

---

Division Two - Level One:

Solution

Source Code:

//2009/08/13 03:07:27
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
#include <set>

using namespace std;

class UserName
{
public:
    string newMember(vector <string> exi, string newName)
    {
        set<string> sset;
        set<string>::iterator it;
        for(int i=0; i<exi.size(); i++) sset.insert(exi[i]);
        int sz = sset.size();
        sset.insert(newName);
        if(sset.size() > sz) return newName;
        int num = 1;
        while(1)
        {
            stringstream ss;
            ss << num;
            string s(newName);
            s += ss.str();
            sset.insert(s);
            if(sset.size() > sz) return s;
            num ++;
        }
    }
};

SRM187

	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

Using regular expressions.

Source Code:

//Sun Oct  9 22:28:19 PDT 2011
public class Cyberline {
    public String lastCyberword(String cyberline) {
        cyberline = cyberline.replaceAll("-", "");
        String[] str = cyberline.split("[^a-zA-Z0-9@]+");
        return str[str.length - 1];
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Source Code:

//2009/09/09 11:21:10
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class DNASingleMatcher
{
public:
    int longestMatch(string s1, string s2)
    {
        int ret = 0;
        for (int i=0; i<s1.size(); i++)
        {
            string s;
            s.clear();
            for (int j=i; j<s1.size(); j++)
            {
                s += s1[j];
                if (s2.find(s) != string::npos)
                    ret = max(ret, (int)s.size());
            }
        }
        return ret;
    }
};

---

Division Two - Level One:

Solution

Source Code:

//2009/08/10 22:13:59
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>

using namespace std;

class OfficeParking
{
public:
    int spacesUsed(vector <string> events)
    {
        int space = 0;
        int mmax = 0;
        for(int i=0; i<events.size(); i++)
        {
            stringstream s(events[i]);
            string s1,s2;
            s >> s1 >> s2;
            if(s2.compare("arrives") == 0)
                space ++;
            else if(s2.compare("departs") == 0)
                space --;
            mmax = max(mmax, space);
        }
        return mmax;
    }
};