UVA – 111 – History Grading

Longest Increasing Subsequence problem.

storing the new indexing order and output the LIS for each sequence.

I used the O( n log(k) ) { where k is the size of the LIS. } algorithm using binary search. it took me lots of time to understand the algorithm 4-full days. i was asked that at facebook’s interview and i only got the O(n^2) dynamic LCS soloution. and i couldn’t minize it more then.

Donald Knuth Solved it in O(n) but i couldn’t find a refrence for the original soloution if you can find a link for it .. please put it in the comments.

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static void main(String[] args) throws NumberFormatException,
			IOException {

		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[] o = new int[N];
		for (int i = 0; i < N; i++)
			o[i] = in.nextInt();
		while (in.hasNext()) {
			int[] a = new int[N];
			for (int i = 0; i < N; i++)
				a[in.nextInt() - 1] = o[i];
			int count = LIS(a).length;
			System.out.println(count);
		}
	}

	public static int[] LIS(int[] a) {
		int[] parent = new int[a.length];
		Vector<Integer> ans = new Vector<Integer>();
		ans.add(0);
		for (int i = 1; i < a.length; i++) {

			if (a[i] > a[ans.lastElement()]) {
				parent[i] = ans.lastElement();
				ans.add(i);
				continue;
			}
			int k = binSearch(i, a, ans);

			if (a[i] < a[ans.get(k)]) {
				ans.set(k, i);
				parent[i] = k > 0 ? ans.get(k - 1) : 0;
			}
		}

		int[] r = new int[ans.size()];
		for (int i = ans.size() - 1, p = ans.lastElement(); i >= 0; i--) {
			ans.set(i, p);
			p = parent[p];
		}

		for (int i = 0; i < r.length; i++)
			r[i] = a[ans.get(i)];

		return r;
	}

	private static int binSearch(int i, int[] a, Vector<Integer> ans) {

		int c = 0, u = 0, v = ans.size() - 1;
		while (u < v) {
			c = (u + v) / 2;
			if (a[i] > a[ans.get(c)])
				u = c + 1;
			else
				v = c;
		}
		return u;
	}
}
Advertisements

One thought on “UVA – 111 – History Grading

  1. package LongestIncreasingSubsequence;

    import java.io.IOException;
    import java.util.Arrays;
    import java.util.Scanner;

    public class HistoryGrading {
    public static void main(String[] args) throws NumberFormatException,
    IOException {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int[] o = new int[N];
    for (int i = 0; i < N; i++)
    o[i] = in.nextInt();

    while (in.hasNext()) {
    int[] a = new int[N];
    for (int i = 0; i < N; i++)
    a[in.nextInt() – 1] = o[i];
    System.out.println(getLsi(a));
    }
    }

    public static int getLsi(int[] input) {
    int[] a = new int[input.length];
    int l = -1;
    for (int z : input) {
    int x = Arrays.binarySearch(a, 0, l + 1, z);
    if (x < 0) {
    x = -x – 1;
    a[x] = z;
    if (x == l + 1)
    l++;
    }
    }
    return l + 1;
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: