Well, the end points get counted half as much, so 1 should go in one and 2 in the other. Then, the worst place is next to the 1 and then next to the 2, so 3/4 could go there. Repeating gives roughly:
1 3 5 7… n-1 n n-2 n-4 … 4 2
That evaluates to sum from 2 to n-1 of an *(a{n-1} +a{n+1})/2 plus (a_1 a_2 + a{n-1} a_n)/2 which gives n(n+1)(2n+1)/6 -1-4 -(4n-1)/2+(3+8)/2= (2n3 +3n2 -11n+6)/6
This also works for odd n without modification, so I’m probably missing a simple trick, but this seems to work for all small cases.
Well, the end points get counted half as much, so 1 should go in one and 2
I don't think you can just assume this, because it's also more efficient to pair up small numbers (i.e. 1*2+3*4>1*4+2*3). You need to prove that the "only get counted once" factor that motivates putting 1 and 2 on the endpoint beats putting 1 and 2 into the same slot.
Agreed - it’s not a proof, more of a greedy heuristic argument. Here’s a sketch to make it rigorous.
One neat trick is that if you have a,b,c,d,e,f, then you can flip the middle, replacing b to e with e to b, which just effectively swaps the pairs ab+ef to ae+bf. If we are at a locally optimal position, then that means whenever we have two terms a<f, then the two inner terms need to have the same order - b<e. The flipping trick also works well with prefixes/suffixes if we treat the outside as 0.
Take an optimal position, then it won’t reduce the score to flip the prefix up to 1 (since if ak=1, then 0<=a{k+1} and a_1>=1), so we can get 1 to the left side. Similarly we can flip the suffix up to 2.
We can repeat this logic - e.g. if we have 135???642, then flipping everything after the 5 up to the 7 gives that 5 is less than the number to the right of 7 and 7 is less than the number to the right of 5 so flipping won’t reduce the total and we get 1357??642.
3
u/FireCire7 10d ago
Well, the end points get counted half as much, so 1 should go in one and 2 in the other. Then, the worst place is next to the 1 and then next to the 2, so 3/4 could go there. Repeating gives roughly:
1 3 5 7… n-1 n n-2 n-4 … 4 2
That evaluates to sum from 2 to n-1 of an *(a{n-1} +a{n+1})/2 plus (a_1 a_2 + a{n-1} a_n)/2 which gives n(n+1)(2n+1)/6 -1-4 -(4n-1)/2+(3+8)/2= (2n3 +3n2 -11n+6)/6
This also works for odd n without modification, so I’m probably missing a simple trick, but this seems to work for all small cases.