No Unpaired Chefs
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Codechef has now decided to make an admin panel amongst their chefs. This way they think that it would be easier for them to control and regulate their contests. To do so, they have asked them to rate everyone including themselves by a non-negative integer.
There are N chefs, numbered from 1 to N. Each chef has submitted a rating to the Codechef panel for other all the chefs including a rating to himself. Surprisingly for the team, for each pair of chefs (say, chef with the number i and the chef with the number j), they collaborated within themselves and gave the same rating to each other i.e. the rating that the chef i has given to the chef j is equal to the rating that the chef j has given to the chef i. The Codechef team built a rating matrix from this input from Chefs. Now, from this input rating matrix M, they will make a Paired rating matrix P as follows:
- P is symmetric.
- Pi, j is either equal to zero, or to Mi, j, where Mi, j is the rating given by ith chef to the jth chef.
- There exists S > 0, such that each entry in P + P2 + ... + PS is positive.
- To make things more friendly between the admin panel of Chefs, the sum of values in P is minimum possible.
Help the Codechef panel in selecting such a matrix P from M. Please find the minimum possible sum of entries in the matrix P such that P will still satisfy the constraints.
The first line of the input contains T, number of test cases to follow. Then T test cases follow.
Each test case start with a line containing an integer N, the number of chefs in Codechef team.
Then N lines follow. Each of them contains N space-separated integers. The jth integer in the ith line is the rating given by chef with the number i to chef with the number j.
For each test case, print the minimum sum of entries, possible for P. If it is not possible to do, print "-1" (without quotes).
- 1 ≤ T ≤ 100
- Constraints on N:
- Subproblem 1 (30 points): 1 ≤ N ≤ 5
- Subproblem 2 (70 points): 1 ≤ N ≤ 100
- 0 ≤ Mi, j ≤ 109
Input: 2 2 1 0 0 1 2 1 1 1 1 Output: -1 2
In the first sample case, there are only two choices of choosing P, one is a zero-matrix, for a zero matrx, we will never be able to make P + P2 + ... + PS all positive. Another choice is to chose P = M, for this case also, we can never make the sum with all positive values for any S.
In the second case, if one selects P such that we eliminate diagonal elements from M, we get all sum positive for S=2 itself. One can check that this is the minimum sum value for P possible to satisfy all constraints.
|Tags||graph-theory, ltime22, medium-hard, mst, pnkjjindal|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.