HardProof | Topcoder Archive

Problem Statement

You are preparing for an exam in Calculus 4. In the chapter "Abstract Fourier Series", you encountered an excercise in which you are given a collection of N statements and your task is to prove that all N statements are equivalent. For the purpose of this problem, we will number the statements 0 through N-1.

For any pair of statements x and y, you are able to prove that statement x implies statement y. However, the proofs of different implications may have different difficulties. You are given a int[] D with N^2 elements. For each x and y, the difficulty of proving the implication "x => y" is D[x*N+y].

The exercise is solved by proving a set of implications such that each statement directly or indirectly implies each other statement. For example, if N = 3, one way of solving the exercise is to prove the implications 0 => 1, 1 => 0, 0 => 2, and 2 => 0. Another way of solving the exercise is to prove the implications 0 => 1, 1 => 2, and 2 => 0.

You are not looking for the least difficult solution. When writing proofs, your biggest issue is switching between easy and hard proofs. Therefore, you are looking for a solution where the difference between the difficulty of the hardest proof and the difficulty of the easiest proof is as small as possible. Compute and return that difference.

Definition

Class:: HardProof
Method:: minimumCost
Parameters:: int[]
Returns:: int
Method signature:: int minimumCost(int[] D)
(be sure your method is public)

Constraints

D will contain exactly N^2 elements.
N will be between 1 and 50, inclusive.
Each element of D will be between 0 and 150,000, inclusive.
For each valid x, D[x*N+x] will be 0.

Examples

```
{0,11,13,13,
10,0,12,13,
10,10,0,11,
12,10,10,0}
```
```
Returns: 1
```
Here, an optimal solution consists of the following proofs: 0 => 1, 1 => 2, 2 => 3, and 3 => 0. The difficulties of these proofs are 11, 12, 11, and 12, respectively. The difference between the largest and the smallest difficulty is 12-11 = 1.

{0,1000,1000,1000,1000,
1,0,1000,1000,1000,
1,1,0,1000,1000,
1,1,1,0,1000,
1,1,1,1,0}

Returns: 999

{0,95,1,10,
95,0,76,33,
1,76,0,49,
10,33,49,0}

Returns: 32

{0,136946,89305,28946,
40152,0,150000,85407,
122920,110420,0,32811,
2092,79717,53028,0}

Returns: 50771

{0,2159,2234,2720,2029,2853,2187,
2564,0,2409,2519,2441,2665,2654,
2666,2575,0,2215,2978,2588,2582,
2067,2743,2156,0,2840,2970,2480,
2724,2057,2136,2044,0,2030,2424,
2860,2512,2026,2867,2594,0,2401,
2893,2194,2802,2892,2151,2554,0}

Returns: 206

{0,44,47,42,44,45,47,42,47,43,46,46,42,47,47,45,44,46,43,47,44,43,43,47,47,44,46,47,44,44,46,43,44,42,42,44,43,43,46,44,45,44,43,43,42,47,47,45,45,42,
44,0,44,43,43,46,44,47,43,46,44,42,42,46,44,44,45,44,43,46,46,46,47,47,44,47,42,44,45,44,42,42,43,46,46,44,43,44,42,45,44,45,44,45,46,44,42,47,43,43,
42,46,0,42,44,43,42,42,43,46,45,45,45,45,46,46,47,46,42,42,43,45,44,43,45,47,47,47,45,47,46,44,43,46,42,47,42,47,43,43,47,45,44,42,44,44,47,47,42,45,
45,43,47,0,47,42,43,47,47,45,43,43,46,46,43,43,43,45,42,45,42,45,47,45,42,47,45,44,42,44,42,43,45,45,42,47,45,42,45,47,43,44,42,42,45,47,44,42,47,45,
43,43,46,47,0,44,47,42,45,45,46,46,42,45,43,47,42,45,42,47,44,43,43,45,47,46,47,44,43,42,42,47,44,42,45,47,44,44,44,47,43,42,46,47,46,47,44,43,45,45,
42,43,44,45,43,0,43,43,43,44,42,47,42,44,47,45,46,43,47,46,47,43,44,45,43,47,44,44,46,43,43,43,44,43,43,46,47,47,43,44,44,44,44,47,43,43,43,47,45,47,
46,45,46,43,47,42,0,43,42,46,42,42,42,44,47,46,46,43,46,44,42,45,45,46,47,47,47,47,42,47,46,45,42,47,45,45,44,44,47,42,47,43,43,44,47,46,47,44,43,45,
46,43,45,47,44,47,45,0,44,43,45,47,44,45,44,47,45,42,47,46,44,46,44,44,45,45,43,47,44,44,45,45,42,42,42,42,45,46,42,43,43,42,44,45,47,46,47,47,45,42,
46,46,47,44,43,46,44,42,0,43,44,45,43,46,43,42,45,43,43,42,46,47,43,44,44,42,44,47,45,46,42,45,43,45,44,42,45,45,42,43,46,47,43,46,47,46,43,47,46,45,
43,46,45,44,43,45,42,42,46,0,44,47,43,42,46,42,45,45,46,45,47,44,45,44,46,47,45,43,45,46,46,45,47,44,46,42,44,46,44,44,46,43,42,45,42,43,42,45,44,44,
42,45,46,42,46,42,42,45,44,47,0,45,43,44,44,46,43,42,42,42,45,47,44,44,44,47,44,43,43,47,42,45,47,42,45,45,43,42,45,42,47,44,44,44,44,45,42,45,43,42,
47,47,46,43,44,45,45,42,42,43,44,0,43,43,43,46,42,43,42,43,43,46,47,47,42,43,46,47,43,42,43,42,45,45,42,47,45,42,42,44,46,44,43,42,47,47,46,47,47,46,
42,43,42,43,43,46,43,47,47,44,44,45,0,47,44,42,44,44,42,46,44,44,46,42,46,47,43,45,46,42,43,46,43,45,42,47,47,47,45,47,47,45,47,45,42,47,43,42,45,44,
43,47,47,46,46,43,42,45,47,47,44,44,47,0,44,45,47,45,44,43,46,43,42,43,44,43,42,43,47,42,42,47,44,46,44,47,44,47,47,42,42,42,45,46,45,47,45,44,43,47,
43,47,47,42,44,42,45,43,44,47,43,42,46,42,0,43,46,44,42,43,47,45,47,46,46,42,47,42,42,44,44,47,42,43,44,42,42,44,43,45,46,45,42,45,43,47,47,46,45,47,
42,42,43,47,46,46,43,42,46,43,43,43,42,45,47,0,42,43,46,47,46,46,44,42,47,46,42,46,44,45,47,46,45,45,42,44,43,46,42,45,45,45,42,47,42,47,42,46,44,44,
42,44,45,46,42,45,44,45,47,43,44,45,44,45,46,42,0,43,44,44,46,45,45,43,42,43,47,46,46,43,46,47,46,45,43,47,44,42,42,47,45,46,46,47,43,42,44,43,47,47,
45,42,45,46,43,43,42,46,44,46,47,46,47,44,46,42,43,0,44,44,47,45,45,42,43,42,44,46,43,45,45,43,46,47,45,45,46,43,44,47,45,47,45,46,45,47,46,43,45,47,
42,45,47,47,46,42,42,43,43,47,46,42,43,47,46,43,42,45,0,42,45,46,42,47,43,47,42,47,44,44,42,44,45,44,46,44,43,46,42,47,46,43,44,47,42,42,44,47,42,45,
47,42,45,42,44,47,44,44,43,46,45,46,46,42,45,45,42,42,43,0,45,43,44,42,47,43,43,45,47,42,42,43,46,42,44,47,47,46,44,43,47,43,43,46,47,47,45,45,45,46,
42,42,46,46,45,44,42,43,43,45,44,44,46,42,44,46,47,42,43,45,0,43,42,42,46,46,42,45,45,45,44,46,45,43,43,47,42,47,47,43,44,43,44,44,46,45,44,43,43,46,
44,44,47,42,46,42,45,47,46,44,43,42,42,44,46,47,46,45,42,47,46,0,43,43,47,42,44,44,42,44,45,45,46,44,46,44,47,46,44,46,46,47,45,42,45,44,43,42,42,42,
43,42,44,44,42,44,44,42,47,42,47,47,47,45,45,43,43,45,47,47,46,42,0,42,45,42,47,42,44,43,46,46,42,46,43,43,45,43,46,47,44,42,47,45,43,46,46,47,44,45,
44,46,44,43,44,47,46,42,47,47,47,46,43,47,42,47,42,44,44,42,47,46,44,0,44,45,44,42,43,43,42,43,42,46,45,43,44,42,46,43,46,47,43,45,44,46,45,42,42,42,
47,46,44,44,42,47,43,47,47,46,42,45,44,43,44,43,45,42,43,43,42,42,45,46,0,46,43,45,43,47,44,42,47,43,42,43,46,45,45,43,43,42,45,45,44,45,42,42,45,45,
43,44,47,46,43,43,44,42,44,46,45,45,42,42,44,46,47,44,47,44,46,44,47,47,43,0,43,42,45,42,45,45,44,44,45,46,45,47,45,45,47,47,46,47,46,45,45,43,45,44,
46,42,46,42,44,44,45,45,44,44,46,45,43,43,47,43,44,44,43,46,46,43,47,47,45,44,0,44,42,43,47,42,42,47,44,43,45,47,44,43,44,47,43,45,47,42,43,45,46,42,
44,47,43,43,45,44,46,42,47,45,46,45,45,42,45,42,44,45,45,47,47,42,47,46,44,42,42,0,44,43,47,47,47,42,44,45,44,42,44,44,47,46,42,45,46,47,42,43,44,43,
42,43,42,44,45,45,47,42,42,45,43,47,45,46,46,44,42,46,43,42,47,42,43,47,47,44,45,42,0,42,43,46,46,44,44,45,42,45,43,45,44,42,45,43,44,45,47,47,44,45,
47,42,42,46,44,44,46,44,42,47,45,44,43,45,42,44,46,43,44,42,43,42,46,43,44,45,46,47,42,0,45,43,45,43,44,45,46,47,46,45,47,43,44,42,42,46,47,42,43,44,
44,44,45,46,47,42,42,45,44,42,44,47,47,44,45,45,45,43,46,42,45,47,43,43,42,44,43,47,47,42,0,47,43,45,45,44,46,43,42,42,44,42,45,43,46,43,42,47,43,42,
42,45,43,47,45,46,46,42,43,44,42,47,44,47,45,44,44,45,42,46,47,45,44,46,42,47,42,46,45,42,46,0,44,44,43,45,44,44,44,44,43,44,42,42,44,47,47,45,45,42,
43,43,43,46,44,43,43,46,45,45,44,43,42,45,47,42,45,45,46,42,44,42,46,47,43,44,42,44,42,46,43,47,0,42,42,42,45,47,46,45,43,46,45,45,46,47,45,44,45,46,
43,47,45,42,46,47,43,46,44,45,45,42,44,47,44,44,46,47,46,46,42,46,43,45,43,45,46,42,46,42,47,46,42,0,43,47,43,42,43,44,47,44,45,42,46,46,47,43,46,43,
42,42,44,45,43,45,45,47,47,45,45,43,42,45,42,45,45,43,43,43,46,42,44,47,43,43,42,43,46,42,47,46,47,43,0,44,45,46,42,47,45,44,46,45,46,44,47,46,42,44,
43,44,45,45,47,44,44,45,42,45,45,47,46,47,43,46,45,47,44,47,42,44,44,42,45,42,42,43,47,43,42,47,43,47,42,0,43,42,46,46,43,46,45,46,44,45,42,42,47,46,
45,47,42,45,45,42,42,44,42,44,42,42,47,47,43,46,47,47,42,43,42,44,42,46,45,44,47,43,45,42,44,44,47,43,43,46,0,45,46,42,43,47,46,44,45,43,47,42,43,46,
45,45,44,43,43,45,45,42,42,43,44,47,46,44,42,47,46,45,42,44,43,45,44,46,46,44,47,42,47,44,45,47,47,47,46,42,47,0,46,46,44,44,46,45,47,45,45,44,45,44,
47,42,45,46,43,47,42,43,47,42,42,42,46,42,44,42,42,46,45,43,44,46,47,47,43,47,45,44,45,42,46,47,44,44,43,47,42,42,0,46,46,45,47,42,45,46,44,43,44,42,
46,42,46,44,44,44,44,46,42,44,44,45,42,44,47,45,44,47,44,42,46,43,45,45,45,43,46,44,44,47,43,42,46,45,47,43,42,46,45,0,43,45,43,42,43,45,43,47,47,42,
43,44,46,43,45,42,42,43,43,45,42,46,42,47,45,44,43,42,47,44,42,42,42,44,42,42,46,44,45,42,47,42,42,44,42,46,47,42,44,44,0,45,44,43,45,44,42,47,43,47,
45,43,45,45,42,47,42,46,43,45,43,46,43,42,47,45,45,44,47,47,47,43,44,42,47,47,44,45,44,42,43,47,47,45,46,46,43,45,47,44,45,0,47,47,45,42,45,47,42,42,
46,42,45,45,47,46,47,46,45,43,43,43,46,45,46,46,47,44,45,44,46,47,45,42,45,45,45,42,44,43,45,42,47,47,46,44,43,45,46,45,44,43,0,44,45,46,47,45,46,43,
44,43,43,42,47,45,46,46,43,42,43,45,42,42,42,42,45,46,47,47,45,46,45,43,47,47,45,47,45,42,46,45,46,45,45,44,47,47,45,44,44,47,42,0,44,47,47,43,47,42,
46,46,45,47,42,42,47,42,47,45,44,47,46,46,45,43,44,42,44,43,43,47,43,43,47,44,42,42,46,42,46,44,47,47,45,45,44,42,45,47,44,45,46,43,0,44,45,45,46,47,
46,46,44,42,42,44,46,45,45,46,44,43,46,45,43,47,47,47,42,42,42,42,45,44,45,45,42,45,44,42,46,43,43,43,44,42,43,43,45,43,47,47,43,43,45,0,43,44,44,46,
43,43,42,42,45,47,42,46,44,45,45,45,45,42,44,45,42,43,45,43,43,43,47,43,44,45,47,43,47,45,43,43,45,42,46,47,43,47,44,43,43,42,42,42,43,45,0,44,42,42,
47,43,46,42,45,43,47,44,47,45,44,45,43,42,42,46,46,44,46,42,46,43,44,43,42,42,47,45,47,46,45,42,42,47,45,45,46,47,43,43,44,44,42,43,43,42,47,0,42,43,
45,45,46,47,42,47,46,46,43,44,46,47,43,46,46,42,47,45,42,45,47,42,42,45,47,43,42,43,43,42,45,47,45,43,43,45,43,43,47,42,46,43,45,46,47,45,47,46,0,45,
46,46,42,47,47,47,42,44,43,46,43,47,43,43,46,45,42,45,47,42,47,42,44,42,43,47,43,45,42,44,45,46,43,46,46,44,46,43,42,44,45,42,42,47,43,47,45,46,42,0}

Returns: 0

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.