Deja Vu solution codechef algomanic

You’re given a sequence of NN – distinct positive integers, not necessarily sorted in ascending order. Your task is pretty straightforward: sort the sequence in ascending order. At any point of time, you can perform one of the following operations: Deja Vu solution codechef

  • If there is only one sequence, with a length greater than 11, split it at some point to divide it into two non-empty sequences. The cost to perform this operation is the minimum of the sizes of the two broken parts.
  • If there are multiple sequences (due to one or more split operations in the past), you may choose one of them with a length greater than 11 and split it at some point to divide it into two non-empty sequences. The cost to perform this operation is the minimum of the sizes of the two broken parts.
  • If there are multiple sequences (due to one or more split operations in the past), you may choose two of them and concatenate them in any order. The cost to perform this operation is the length of the resulting sequence, i.e., the sum of the lengths of the first and the second part.

It turns out that there are a LOT of ways to sort the array by following this scheme! You need to find out the minimum cost of all the operations required to sort the array in the optimal manner.

Input Format Deja Vu solution codechef

  • Each test file contains multiple test cases. The first line contains the number of test cases, TT. Description of the test cases follows.
  • The first line of each test case contains a single integer NN, the length of the array.
  • The second line of each test case contains NN space-separated integers, the elements of the array.

Output Format

For each test case, output in a single line, the minimum cost of operations that is required to sort the array according to the given scheme.

Constraints Deja Vu solution codechef

  • 1≤T≤101≤T≤10
  • 1≤N≤2001≤N≤200
  • 1≤Ai≤1061≤Ai≤106

Sample Input 1

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

Sample Output 1  Deja Vu solution codechef

11
0

Explanation

  • In the first test case, we can achieve an optimal cost of 1111 with the following sequence of operations:
  • First split the sequence [1,2,4,5,3][1,2,4,5,3] between 55 and 33 into two new sequences: [1,2,4,5][1,2,4,5] and [3][3]. We have two sequences now: {[1,2,4,5],[3]}{[1,2,4,5],[3]}. The cost to perform this operation is min(length([1,2,4,5]), length([3]))min(length([1,2,4,5]), length([3])) = min(4,1)min(4,1) = 11.
  • Now, split the sequence [1,2,4,5][1,2,4,5] between 22 and 44 into two new sequences: [1,2][1,2] and [4,5][4,5]. We have three sequences now: {[1,2],[4,5],[3]}{[1,2],[4,5],[3]}. The cost to perform this operation is min(length([1,2]), length([4,5]))min(length([1,2]), length([4,5])) = min(2,2)min(2,2) = 22.
  • Now, concatenate the sequences [3][3] and [4,5][4,5] in this order to form a new sequence: [3,4,5][3,4,5]. We have two sequences now: {[1,2],[3,4,5]}{[1,2],[3,4,5]}. The cost to perform this operation is length([3])+length([4,5])length([3])+length([4,5]) = 1+21+2 = 33.
  • Now, concatenate the sequences [1,2][1,2] and [3,4,5][3,4,5] in this order to form a new sequence: [1,2,3,4,5][1,2,3,4,5]. We have one sequence now: [1,2,3,4,5][1,2,3,4,5], which is sorted as desired. The cost to perform this operation is length([1,2])+length([3,4,5])length([1,2])+length([3,4,5]) = 2+32+3 = 55.
  • Hence, the total cost = 1+2+3+51+2+3+5 = 1111.
  • In the second test case, we notice that the sequence is already in ascending order. Hence, we need not do any operations. The total cost is 00, without a scratch.

Deja Vu solution codechef

Leave a Comment