Time Limit exceeded :(

Hello, So in the February lunchtime 2022, There was this problem called parallel preprocessing under division 4. The link to the problem is here. : Contest Page | CodeChef
And my solution was this
Approach

  1. User enters number if test cases, loop so many times.

  2. user adds the number if processes(n), followed by n elements of the array (a). Initialize a variable declare to 0 first, as the user enters n elements, keep adding them to sum.
    i.e sum+=a[i]

  3. This sum can be represented as a sum of 2 numbers.
    Ex: if the sum is 9. It can be represented as:

1,8
2,7
3,6
4,5
****** after this, the numbers repeat.
So the total no of such combinations we can get for a given number sum is: n/2
Here 9/2=4 combinations we have got.

  1. So i made a for loop from i=1 to sum/2 terms and filled it with the sum-ith term.
    i.e all the elements to the right.
    8,7,6,5.

Now the minimum of this would result in the answer.
so i printed that out. ( def[(sum/4)]th term is printed. )

There is one exception however and that is, if there is only process, that process itself would take the minimum time as this process can be assigned to either p1 or p2.

Code:


#include <iostream>
using namespace std;

int main() {
	int T;
	cin>>T;
	
	while(T--){
	    int n,sum=0;
	    cin>>n;
	    int a[n];
	   
	    for(int i=0;i<n;i++){
	        cin>>a[i];
	        sum+=a[i];
	    }
	   
	    if(n==1){
	       cout<<sum<<endl;
	        break;
	    }
	   
	    int def[(sum/2)];
	    def[0]=0;
	    for(int i=1;i<=(sum/2);i++){ /// 8 7 6 5
	       def[i]=(sum-i);
	       
	    }
	    cout<<def[(sum/2)]<<endl;
	    
	}
	
	
	return 0;
}

I do this, i get the correct output, except it says, Time exceeded. Any tips and suggestions would help. Thanks

Your approach is incorrect. Kindly refer the editorial for correct approach.
However, you are getting TLE as sum of the elements can reach upto 10^{10}.

1 Like

These are the 2 errors i am getting. RE and TLE.

You are declaring an array of size sum/2 in each test case.

As 1<=N<=1e5 and 1<=A[i]<=1e5, the sum can be of the order 1e10.
So declaring an array of size 1e10 would result in Time Limited exceeded/Memory Limit Exceeded.