DCP-71: Mahir’s TREAT Back to All Problems

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


Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

10/27

Solve/Submission

Ranking

# User Language Timing
01 moinul_shaon Cpp14 0.56s
02 Morass Cpp14 0.58s
03 mahbubcseju Cpp14 0.62s
04 raihatneloy Cpp14 0.64s
05 Matrix_code Cpp14 0.68s
06 khatribiru Cpp14 0.69s
07 faisal47 Cpp14 0.69s
08 Robbinb1993 Cpp14 0.79s
09 nfssdq Cpp14 1.21s
10 sahedsohel Cpp14 1.66s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support