Hard Divide and Conquer > Dynamic Programming

Mahir Kabir is the most popular senior among his juniors . But his university is going to end soon so he is planning to treat all of his juniors . But Some of them had problems with others rather we can say each person has some dissatisfaction with others . Which can be describe as dissatisfaction factor . Say dissatisfaction factor are given as **Dij**. **Dij** means the dissatisfaction factor according to person **i** towards **j**. If the value is negative that means ith person likes jth person. Positive value meansithperson hates jth person. 0 means ith person is neutral about jth person. Obviously **Dij** can be different from **Dji** since ith person may like jth person, but jth person may not like ith person and vice versa. Now, if Mahir groups some people, the dissatisfaction factor is the summation of all the members' dissatisfaction factors towards other people in the group. Mahir has to group them with minimum dissatisfaction factor. he can make as many groups as he like . Mahir wants to treat all of his juniors with minimum dissatisfaction factor . Can you help him . Input: ------ Input starts with an integer **T (≤ 50 )**, denoting the number of test cases. Each case starts with a line containing an integer **n (2 ≤ n ≤ 15**). Each of the next n lines contains n space separated integers. The jth integer in the ith line denotes Dij. You can assume that **- 200 ≤ Dij ≤ 200** and of course **Dii = 0**. Output: ------- For each case, print the case number and the minimum dissatisfaction factor you can make after grouping them. Sample Input ------------ 2 3 0 2 3 -3 0 5 2 3 0 4 0 -1 -2 -3 1 0 -2 3 1 2 0 -1 2 -2 1 0 Sample Output ------------- Case 1: -1 Case 2: -2

Shakil Ahmed