Disgust Minimization Codechef Solution

Problem

You have a matrix $A$ with dimensions $N\times N$. Let the disgust of the matrix be defined as:

\sum_{i=1}^{N} \sum_{j=1}^{N} (A_{(i, j)} – A_{(j, i)})^2∑i=1N​∑j=1N​(A(i,j)​−A(j,i)​)2

You also have $M$ tuples with you. Each tuple consists of $3$ integers X_i, Y_i,Xi​,Yi​, ans Z_iZi​ $(1\le i\le M)$. In one operation, you can:

• Choose an element $(p,q)$ $(1\le p,q\le N)$ such that the value of the element A_{(p,q)} = X_iA(p,q)​=Xi​.
• Change the value of the chosen element to Y_iYi​.

The cost of applying the above operation is Z_iZi​. Note that $(1\le i\le M)$ and thus, the operation might correspond to any one of the given tuples.

Find the minimum value of $($totalCost $+$ disgust$)$ after applying the given operation any (possibly zero) number of times.

Input Format

• The first line contains one integer $T$ – the number of test cases. Then $T$ test cases follow.
• The first line of each test case consists of two integer $N$ and $M$, the row size and the number of tuples.
• $N$ lines follow, each consisting of $N$ space-separated integers – the matrix $A$.
• $M$ lines follow, each consisting of $3$ space-separated integers – each tuple X_i, Y_i, Z_iXi​,Yi​,Zi​.

Output Format

For each test case, output the minimum value of $($totalCost $+$ disgust$)$ after applying the given operation any (possibly zero) number of times.

Constraints

Sample 1:

3
3 2
3 3 1
1 2 1
3 2 1
3 2 2
1 2 3
2 1
2 2
2 2
1 1 3
3 2
3 3 1
1 2 1
3 2 1
2 1 1
3 2 1

10
0
5

Explanation:

Test case $1$: We convert A_{(1, 2)}A(1,2)​ to $2$ for a cost of $2$ and we convert A_{(3, 1)}A(3,1)​ to $2$ for a cost of $2$. The total cost is $2+2=4$ and disgust is (3-3)^2 + (2-1)^2 + (1-2)^2 + (1-2)^2 + (2-2)^2 + (1-2)^2 + (2-1)^2 + (2-1)^2 + (1-1)^2 = 6(3−3)2+(2−1)2+(1−2)2+(1−2)2+(2−2)2+(1−2)2+(2−1)2+(2−1)2+(1−1)2=6. Thus, the value $($totalCost $+$ disgust$)$ for the new matrix is $4+6=10$. We can show that this is the minimum value possible.

Test case $2$: We do not need to perform any operations. Thus, the value:
$($totalCost $+$ disgust) = 0 + (2-2)^2 + (2-2)^2 + (2-2)^2 + (2-2)^2 = 0)=0+(2−2)2+(2−2)2+(2−2)2+(2−2)2=0.

Test case $3$: We perform the following operations:

• We choose A_{(1, 2)}A(1,2)​ and change it to $2$ for a cost of $1$. Then, we further change it to $1$ for a cost of $1$.
• We choose A_{(3, 1)}A(3,1)​ and change it to $2$ for a cost of $1$. Then, we further change it to $1$ for a cost of $1$.
• We choose A_{(3, 2)}A(3,2)​ and change it to $1$ for a cost of $1$. The new disgust is $0$ while the cost is $5$. The value $($totalCost $+$ disgust$)$ for the new matrix is $5$. We can verify that this is the minimum possible value.