ACM ICPC Amritapuri Online Round Solution : Creating a Warmhole

Dr Ryan Stone is the Mission Specialist, and she went out to fix some communications equipment when suddenly news came in about debris from other satellite heading towards them. Very quickly, she realizes that she does not have enough time to get all her equipments back in before the Debris field hits them. Therefore, she decided to adopt an alternative way of handling the debris. She has got “N” pieces of equipments. Each equipment is essentially an iron stick of some length. The i^th equipment has length a_i. She wants to join them end to end to form a closed polygon. She will then send some electric current through the polygon to create a giant magnetic field which will attract all debris. Thus, this polygon will act as a wormhole, sucking in all the debris and allowing rest of the satellite/crew to go unharmed. She wants to form as big a polygon as possible, and hence she wants to quickly know the maximum number of equipments she can use to form a polygon. Note that the area of polygon should be non-zero, otherwise debris can’t pass through it. You should output -1 if no polygon can be formed.

Input Format:

The first line contains the number of test cases T. For each test case, the first line contains N, the number of equipments. The following line contains N space delimited integers, the ith integer specifying the length of the ith equipment. Output: For each test case, output the maximum number of equipments which can be used to form a polygon.

Constraints:

1 <= T <= 100
3 <= N <= 10000
1 <= a_i <= 10^9

Sample Input:

2
7
1 12 3 2 5 1 50
3
1 1 2

Sample Output:

5
-1

Explanation:

For the first test case, we can use the equipments of lengths 1, 3, 2, 5, 1 and form a polygon out of them. There is no way to form a polygon using more than 5 equipments. For the second test case, we cannot form a valid polygon from the given equipments.

Time Limit

4 s

Memory Limit

256 MB 

Solution : 

The logic is quite simple.

1. Sort the array.
2. At ith index store the sum of elements upto ith index.
3. now start comparing elements from last position.

          if ith element is smaller than all previous element than print (i+1)

       if no polygon can be formed than out -1.

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author VIK
 */
public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int tt[] = new int[t];
        for (int i = 1; i <= t; i++) {
            int n = sc.nextInt();
            int[] temp = new int[n];

            for (int j = 0; j < temp.length; j++) {

                temp[j] = sc.nextInt();

            }

            Arrays.sort(temp);
            for (int j = 1; j < temp.length; j++) {
                temp[j] += temp[j - 1];
            }
            boolean flag = true;
            for (int j = temp.length - 1; j > 1; j--) {
                if ((temp[j] - temp[j - 1]) < temp[j - 1]) {
                    tt[i - 1] = (j + 1);

                    flag = false;
                    break;

                }
            }
            if (flag) {
                tt[i - 1] = -1;

            }



        }
        for (int i = 0; i < tt.length; i++) {
            if (i != t) {
                System.out.println(tt[i]);
            } else {
                System.out.print(tt[i]);
            }
        }
    }
}