Parallel Processing solution codechef- There are NN tasks waiting in line to be executed. The execution time for the ithith task is AiAi seconds. Chef has two processors to execute these NN tasks. Both these processors work simultaneously. Each processor executes the assigned tasks one by one.

Parallel Processing solution codechef

 

There are NN tasks waiting in line to be executed. The execution time for the ithith task is AiAi seconds.

Chef has two processors to execute these NN tasks. Both these processors work simultaneously. Each processor executes the assigned tasks one by one.

Chef assigns a prefix of these tasks to the first processor and the remaining tasks to the second processor.

For example, if there are 33 tasks, Chef can do one of the following:

  • Assign no task to the first processor. This means, the second processor will execute tasks 1,21,2 and 33.
  • Assign task 11 to the first processor. This means, the second processor will execute tasks 22 and 33.
  • Assign tasks 11 and 22 to the first processor. This means, the second processor will execute task 33.
  • Assign tasks 1,21,2 and 33 to the first processor. Thus, second processor would execute no tasks.

Find the minimum time in which all the tasks can be executed.

Input Format Parallel Processing solution codechef

  • First line will contain TT, number of test cases. Then the test cases follow.
  • The first line of each test case contains a single integer NN, the number of tasks waiting to be executed.
  • The second line of each test case contains NN space separated positive integers A1,A2,,ANA1,A2,…,AN denoting the execution time for each task.

Output Format

For each test case, output in a single line, the minimum time in which all tasks can be executed.

Constraints Parallel Processing solution codechef

  • 1T1001≤T≤100
  • 1N1051≤N≤105
  • 1Ai1051≤Ai≤105
  • The sum of NN over all test cases is not more than 21052⋅105.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

3
3
4 2 3
6
1 1 1 1 1 1
1
5

Parallel Processing solution codechef Sample Output 1 

5
3
5

Explanation

Test Case 1: Chef assigns task 11 to the first processor and tasks 22 and 33 to the second processor. The first processor takes 44 seconds to execute task 11. The second processor takes 2+3=52+3=5 seconds to execute tasks 22 and 33. Thus, atleast 55 seconds are required to execute all tasks.

Test Case 2: Chef assigns tasks 1,21,2 and 33 to the first processor. Processes 4,54,5 ad 66 are executed by second processor.

Test Case 3: Chef assigns task 11 to the first processor. No task is executed by second processor.

SOLUTION – CLICK HERE

Leave a Comment

Your email address will not be published.