Number of Pushes, time limit exceeding

Question

There are N boys standing in line in order 1 to n. For each ith boy (i from 1 to N) W[i] gives his weight. A boy in line can push another boy if his weight is more than or equal to the sum of weight of boys between them. We have to calculate for each boy, the number of boys he can get pushed by. My solution is taking too much time. (1<=N<=10^5)
first line has N, second has weight of N boys in line.
For example:
INPUT:
5
2 5 8 10 12
OUTPUT:
2 3 3 2 1
My code:

 class A {

public static void main(String[] args) throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        long[] W=new long[n];
        long[] sumtill_i=new long[n];
        int[] pushedby=new int[n];
        long sum=0;
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++)
        {
            W[i]=Long.parseLong(st.nextToken());
            sum+=W[i];
            sumtill_i[i]=sum;
        }
        int j;
        for(int i=0;i<n;i++)
        {
            j=n-1;
            while(j>=0)
            {
                if(j>i)
                {
                    if(W[j]>=(sumtill_i[j]-sumtill_i[i]-W[j]))
                        pushedby[i]++;
                }
                if(j<i)
                {
                    if(W[j]>=(sumtill_i[i]-sumtill_i[j]-W[i]))
                        pushedby[i]++;
                }
                j--;

            }
        }
        for(int i=0;i<n;i++)
            System.out.print(pushedby[i]+" ");
}
 } 

Answer 1

Some style points first:

• StringTokeniser is discouraged see here
• variables are lowerCamelCase in java convention. Try to avoid _ and don't start with a capital letter.
• Longer meaningful names are a lot better than short (especially 1 letter) variable names. What exactly is that W? A variable called weights is so much easier to understand. I'll make an exception for n for being part of the assignment and i and j as loop variables for beïng know as loop variables.
• java coding conventions say to ALWAYS use braces after each if/for/...
  (The only exception I make is if you put the next statement on the same line as the if, for an example take a look at an auto generated equals implementation).
• the opening braces usually go on the same line, not the next line, but it's a good thing that you're consistent.

Here's a cleaned up version of your code. It should still work exactly the same:

Scanner input = new Scanner(System.in);
int n = input.nextInt();
input.nextLine(); // needed to proces the end of the first input line.
long[] weights = new long[n];
long[] cumulativeSum = new long[n];
int[] pushedby = new int[n];
long sum = 0;

for (int i = 0; i < n; i++) {
    weights[i] = input.nextLong();
    sum += weights[i];
    cumulativeSum[i] = sum;
}

for (int i = 0; i < n; i++) {
    for(int j = n-1; j >= 0; j--){
        if (j > i) {
            if (weights[j] >= (cumulativeSum[j] - cumulativeSum[i] - weights[j])) {
                pushedby[i]++;
            }
        }
        if (j < i) {
            if (weights[j] >= (cumulativeSum[i] - cumulativeSum[j] - weights[i])) {
                pushedby[i]++;
            }
        }
    }
}

for (int i = 0; i < n; i++) {
    System.out.print(pushedby[i] + " ");
}

---

You had an interesting idea with storing the sumtill but does it really help you? After all, you're still checking each possible pair.

What you could do instead is for each person in the list, walk the list to the left and to the right adding up the total weight up till that point and check if you can still push that guy. If you can, increment the pushedBy counter for that other guy. As soon as you can't you stop going further down the list.

Putting that into code looks something like this:

Scanner input = new Scanner(System.in);
int n = input.nextInt();
input.nextLine(); // needed to proces the end of the first input line.
long[] weights = new long[n];
int[] pushedby = new int[n];
long sum = 0;

for (int i = 0; i < n; i++) {
    weights[i] = input.nextLong();
    sum += weights[i];
}

for (int currentPerson = 0; currentPerson < n; currentPerson++) {
    //check left of the current person as long as the current person can push them all.
    long totalWeight = -weights[currentPerson];
    for (int i = currentPerson - 1; i >= 0; i--) {
        totalWeight += weights[i];
        if (totalWeight > 0) {
            break; // can no longer push them all
        }
        pushedby[i]++;
    }

    //same for right of the current person
    totalWeight = -weights[currentPerson];
    for (int i = currentPerson + 1; i < n; i++) {
        totalWeight += weights[i];
        if (totalWeight > 0) {
            break;
        }
        pushedby[i]++;
    }

}

for (int i = 0; i < n; i++) {
    System.out.print(pushedby[i] + " ");
}
System.out.println(); //actually finish the line

I did notice that this gives a different result than yours. You may want to check which result is the correct solution to the problem.