Skip to main content

Salesforce

SalesForce OA 2023 -Tom And Holes

Problem Description:

Tom wants to catch Jerry by digging M holes on a straight track. Each hole has a certain depth, and digging a one-unit deep hole takes one unit of time. Since Tom is lazy, he asks N fellow cats to help him dig the holes. Tom assigns each of the N cats a set of consecutive holes to dig. Two cats will not dig the same hole.

Your task is to help Tom assign the holes to the cats in such a way that the total time taken to dig all the holes is minimized. The time taken by each cat is the sum of the depths of the holes assigned to them, and the goal is to minimize the maximum time taken by any single cat.

Input Format:

  • The first line contains an integer T, the number of test cases.
  • For each test case:
    • The first line contains two integers N and M, where N is the number of cats and M is the number of holes.
    • The second line contains M space-separated integers representing the depth of each hole.

Output Format:

  • For each test case, output the minimum amount of time required to dig all the holes on a new line.

Constraints:

  • 1 <= T <= 10
  • 1 <= N <= M <= 100,000
  • 1 <= depth of holes <= 10,000

Sample Testcases:

Sample Input 1:

1
3 10
5 3 20 16 18 1 10 10 9 8

Sample Output 1:

37

Explanation:

An optimal assignment of holes to the cats is:

  • Cat 1: (5, 3, 20)
  • Cat 2: (16, 18, 1)
  • Cat 3: (10, 10, 9, 8)

The total time taken is minimized, and the maximum time taken by any cat is 37 units.

Note: Although the below distribution of holes yields a maximum time of 34 which is lesser than the answer, since consecutive holes are not assigned to cats below distribution is an invalid distribution.

cat1=> (20,9,3,1), total time = 33
cat2=> (18,10,5), total time = 33
cat3=> (16,10,8), total time = 34

Sample Input 2:

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

Sample Output 2:

5
1

Explanation:

In the first case, the optimal assignment is:

  • Cat 1: (1, 2)
  • Cat 2: (3)
  • Cat 3: (4)
  • Cat 4: (5)

The maximum time taken by any cat is 5 units.

In the second case:

  • Cat 1: (1)
  • Cat 2: (1)

The time taken is 1 for both cats.