Interview Street Challenges - Vertical Sticks

Vertical_sticks.java

import java.util.*;

public class Vertical_sticks {

	public boolean permute(int[] data) {
		int k = data.length - 2;
		while (data[k] >= data[k + 1]) {
			k--;
			if (k < 0) {
				return false;
			}
		}
		int l = data.length - 1;
		while (data[k] >= data[l]) {
			l--;
		}
		swap(data, k, l);
		int length = data.length - (k + 1);
		for (int i = 0; i < length / 2; i++) {
			swap(data, k + 1 + i, data.length - i - 1);
		}
		return true;
	}

	private void swap(int[] data, int k, int l) {
		data[k] = data[k] + data[l];
		data[l] = data[k] - data[l];
		data[k] = data[k] - data[l];
	}

	public double process(int[] set) {
		Arrays.sort(set);
		long v = 0, count = 0;
		do {
			v += perform(set);
			count++;
		} while (permute(set));
		// System.out.println("v="+v+" and num.of permutations"+count);
		double ret = (double) v / count;
		return ret;
	}

	public int perform(int[] intArray) {
		int len = intArray.length;
		int total_len = 0;
		for (int i = len - 1; i > 0; i--) {
			int ray_len = 1;
			// System.out.println("Comparing with "+intArray[i]);
			for (int j = i - 1; j >= 0; j--) {
				if (intArray[j] >= intArray[i]) {
					// System.out.println(intArray[j]+">="+intArray[i]);
					break;
				}
				ray_len++;
			}
			// System.out.println("Ray length is "+ray_len);
			total_len += ray_len;
		}
		return total_len + 1;
	}

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int num_of_testcases = sc.nextInt();
		Vertical_sticks v_sticks = new Vertical_sticks();
		for (int i = 0; i < num_of_testcases; i++) {
			int num_of_points = sc.nextInt();
			int sticks[] = new int[num_of_points];
			for (int j = 0; j < num_of_points; j++) {
				sticks[j] = sc.nextInt();
			}
			System.out.printf("%8.2f\n", v_sticks.process(sticks));
		}
	}
}

Vertical Sticks (50 Points)
Given array of integers Y=y1,...,yn, we have n line segments such that endpoints of segment i are (i, 0) and (i, yi). Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, v1, ..., vn, where vi is equal to length of ray shot from the top of segment i. We define V(y1, ..., yn) = v1 + ... + vn.
For example, if we have Y=[3,2,5,3,3,4,1,2], then v1, ..., v8 = [1,1,3,1,1,3,1,2], as shown in the picture below:

For each permutation p of [1,...,n], we can calculate V(yp1, ..., ypn). If we choose a uniformly random permutation p of [1,...,n], what is the expected value of V(yp1, ..., ypn)?
Input Format
First line of input contains a single integer T (1 <= T <= 100). T test cases follow.
First line of each test-case is a single integer N (1 <= N <= 50). Next line contains positive integer numbers y1, ..., yN separated by a single space (0 < yi <= 1000).
Output Format
For each test-case output expected value of V(yp1, ..., ypn), rounded to two digits after the decimal point.
Sample Input
6
3
1 2 3
3
3 3 3
3
2 2 3
4
10 2 4 4
5
10 10 10 5 10
6
1 2 3 4 5 6
Sample Output
4.33
3.00
4.00
6.00
5.80
11.15
Explanation

Case 1: We have V(1,2,3) = 1+2+3 = 6, V(1,3,2) = 1+2+1 = 4, V(2,1,3) = 1+1+3 = 5, V(2,3,1) = 1+2+1 = 4, V(3,1,2) = 1+1+2 = 4, V(3,2,1) = 1+1+1 = 3. Average of these values is 4.33.
Case 2: No matter what the permutation is, V(yp1, yp2, yp3) = 1+1+1 = 3, so the answer is 3.00.
Case 3: V(y1 ,y2 ,y3)=V(y2 ,y1 ,y3) = 5, V(y1, y3, y2)=V(y2, y3, y1) = 4, V(y3, y1, y2)=V(y3, y2, y1) = 3, and average of these values is 4.00.

The time complexity is too high, can not pass all the test cases here: https://www.hackerrank.com/challenges/vertical-sticks