Problem: ethan (2018 finals)

The final exam is here, and it's now or never for Ethan. His current grade is
abysmal so he needs a strong showing on this exam to have any chance of
passing his introductory computer science class.

The exam has only one question: devise an algorithm to compute the compactness
of a grid tree.

Ethan recalls that a "grid tree" is simply an unweighted tree with 2**N**
nodes that you can imagine being embedded within a 2x**N** grid. The top row
of the grid contains the nodes 1 ... **N** from left to right, and the bottom
row of the grid contains the nodes (**N** \+ 1) ... 2**N** from left to right.
Every edge in a grid tree connects a pair of nodes which are adjacent in the
2x**N** grid. Two nodes are considered adjacent if either they're in the same
column, or they're directly side-by-side in the same row. There must be
exactly 2**N**-1 edges that connect the 2**N** nodes to form a single tree.
Additionally, the _i_th node in the grid tree is labelled with an integer
**Ai**.

What was "compactness" again? After some intense thought, Ethan comes up with
the following pseudocode to compute the compactness, **c**, of a grid tree:

  * 1\. Set **c** to be equal to 0. 
  * 2\. Iterate _i_ upwards from 1 to 2**N** \- 1: 
  * 2a. Iterate _j_ upwards from _i_+1 to 2**N**: 
  * 2b. Increase **c** by **Ai** * **Aj** * `ShortestDistance(i, j)`
  * 3\. Output **c**. 

`ShortestDistance(i, j)` is a function which returns the number of edges on
the shortest path from node _i_ to node _j_ in the tree, which Ethan has
implemented correctly. In fact, his whole algorithm is quite correct for once.
This is exactly how you compute compactness!

There's just one issue — in his code, Ethan has chosen to store **c** using a
rather small integer type, which is at risk of overflowing if **c** becomes
too large!

Ethan is so close! Feeling sorry for him, you'd like to make some last-minute
changes to the tree in order to minimize the final value of **c**, and thus
minimize the probability that it will overflow in Ethan's program and cost him
much-needed marks. You can't change any of the node labels **A1..2N**, but you
may choose your own set of 2**N** \- 1 edges to connect them into a grid tree.

For example, if **A** = [1, 3, 2, 2, 4, 5], then the grid of nodes looks like
this:

You'd like to determine the minimum possible compactness which Ethan's program
can produce given a valid tree of your choice. For example, one optimal tree
for the above grid of nodes (which results in the minimum possible compactness
of 198) is as follows:

### Input

Input begins with an integer **T**, the number of trees. For each tree, there
are three lines. The first line contains the single integer **N**. The second
line contains the **N** space-separated integers **A1..N**. The third line
contains the **N** space-separated integers **AN+1..2N**.

### Output

For the _i_th tree, output a line containing "Case #_i_: " followed by the
minimum possible output of Ethan's program.

### Constraints

1 ≤ **T** ≤ 80  
1 ≤ **N** ≤ 50  
1 ≤ **Ai** ≤ 1,000,000  

### Explanation of Sample

One optimal tree for the first case is given above. For that tree, Ethan's
program would compute **c** as the sum of the following values (with some
values omitted):

  * **A1** * **A2** * `ShortestDistance(1, 2)` = 1 * 3 * 1 = 3 
  * **A1** * **A3** * `ShortestDistance(1, 3)` = 1 * 2 * 4 = 8 
  * ... 
  * **A1** * **A6** * `ShortestDistance(1, 6)` = 1 * 5 * 3 = 15 
  * **A2** * **A3** * `ShortestDistance(2, 3)` = 3 * 2 * 3 = 18 
  * ... 
  * **A4** * **A6** * `ShortestDistance(4, 6)` = 2 * 5 * 2 = 20 
  * **A5** * **A6** * `ShortestDistance(5, 6)` = 4 * 5 * 1 = 20 

In the second case, there's only one possible tree, for which **c** = 2 * 3 *
1 = 6.

In the third case, two of the four possible trees are optimal (the ones
omitting either the topmost or leftmost potential edge).



Sample input:
6
3
1 3 2
2 4 5
1
2
3
2
1 1
1 2
5
1 5 10 6 5
2 3 5 8 10
8
11 60 25 38 49 84 96 42
3 51 92 37 75 21 97 22
12
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 999999 1000000 1000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 999999 1000000


Sample output:
Case #1: 198
Case #2: 6
Case #3: 14
Case #4: 3226
Case #5: 1019144
Case #6: 1419999746000002



Code: // Ethan Sums Shortest Distances
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 51

int R[2][LIM],sum[2][LIM];
LL dyn[LIM][3][LIM];
// dyn[i][r][p] = min. cost such that:
// - you're ending at a vertical edge in column i (its cost is exluded)
// - you previously had a partial horizontal section in row r (r=2 indicates both rows)
// - the partial horizontal section started in column p

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N;
	LL S;
	int i,i2,j,k,r,r2,p,p2,s;
	LL ans,cur,cur2;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input, and compute each row's prefix sums
			Read(N);
				Fox(i,2)
					Fox(j,N)
					{
						Read(R[i][j]);
						sum[i][j+1]=sum[i][j]+R[i][j];
					}
			S=sum[0][N]+sum[1][N];
			// initial DP step (before first vertical edge)
			Fill(dyn,60);
				Fox(i,N)
				{
					cur=0;
					// compute horizontal section costs for both rows' prefixes
						Fox(j,2)
						{
							s=0;
								Fox(k,i)
								{
									s+=R[j][k];
									cur+=s*(S-s);
								}
						}
					dyn[i][2][0]=cur;
				}
			// main DP
				Fox(i,N)
					FoxI(i2,i+1,N-1)
						Fox(r2,2)
							FoxI(p2,i+1,i2)
							{
								cur=0;
								// compute full horizontal section cost
								s=sum[r2][p2]+sum[1-r2][i+1];
									FoxI(j,i,i2-1)
									{
										cur+=s*(S-s);
										s+=R[1-r2][j+1];
									}
								// compute left partial horizontal section cost
								s=0;
									FoxRI(j,i+1,p2-1)
									{
										s+=R[r2][j];
										cur+=s*(S-s);
									}
								// compute right partial horizontal section cost
								s=0;
									FoxI(j,p2,i2-1)
									{
										s+=R[r2][j];
										cur+=s*(S-s);
									}
								// consider all previous states
									Fox(r,3)
										Fox(p,i+1)
										{
											cur2=dyn[i][r][p]+cur;
											// compute vertical edge cost
												if (r==2)
													s=sum[r2][p2];
												else
												if (r==r2)
													s=sum[r2][p2]-sum[r2][p];
												else
													s=sum[r2][p2]+sum[1-r2][p];
											cur2+=s*(S-s);
											Min(dyn[i2][r2][p2],cur2);
										}
							}
			// final DP step (after last vertical edge)
			ans=(LL)INF*INF;
				Fox(i,N)
					Fox(r,3)
						Fox(p,i+1)
						{
							cur=dyn[i][r][p];
							// compute horizontal section costs for both rows' suffixes
								Fox(j,2)
								{
									s=0;
										FoxRI(k,i+1,N-1)
										{
											s+=R[j][k];
											cur+=s*(S-s);
										}
								}
							// compute vertical edge cost
								if (r==2)
									s=sum[0][N];
								else
									s=sum[r][N]-sum[r][p];
							cur+=s*(S-s);
							Min(ans,cur);
						}
			// output
			printf("Case #%d: %lld\n",t,ans);
		}
	return(0);
}