HardProof
SRM 692 · 2016-06-04 · by Xellos0
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
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.
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.
{0,1,
1,0}
Returns: 0
{0,1,1,
1,0,1,
1,1,0}
Returns: 0
{0,5,
2,0}
Returns: 3
There are two statements. In order to solve the exercise, we need to prove both 0 => 1 and 1 => 0. The maximum difficulty of a proof is 5, the minimum difficulty is 2, thus the difference is 5-2 = 3.
{0,100000,100000,100000,100000,
100000,0,100000,100000,100000,
100000,100000,0,100000,100000,
100000,100000,100000,0,100000,
100000,100000,100000,100000,0}
Returns: 0
{0,10,28,1,
75,0,10,1,
15,99,0,10,
1,1,5,0}
Returns: 9
{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.
Submissions are judged against all 102 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HardProof with a public method int minimumCost(vector<int> D) · 102 test cases · 2 s / 256 MB per case