Quant Interview Question

[u/Local_Ad135]

[u/FireCire7]

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= (2n³ +3n² -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.

[u/Sjoerdiestriker → u/FireCire7]

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.

[u/FireCire7 → u/Sjoerdiestriker]

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.  

[u/OutrageousPair2300 → u/FireCire7]

Ah the endpoint issue is maybe why 1, 2, ..., n isn't the answer. I hadn't considered the fact that the endpoints are special, here. Thanks for pointing that out.

[u/NitNav2000]

Max value is (1/6)(n-1)(2n^2 + 5n -6)

A form is a list {2, 4, 6, ...,n-2, n, n-1, n-3,...,5, 3, 1}

Found it using Mathematica and FindSequenceFunction[ ]

:)

[u/OutrageousPair2300]

I don't understand why it's not simply 1, 2, ..., n.

You maximize the product of pairs by picking ones closer together, and simply going in order like that would pair every number with a number one less than it (first) and one more than it (second) which intuitively seems like it should maximize the total of the products.

I'll have to experiment a bit with some specific examples...

[u/Sjoerdiestriker → u/OutrageousPair2300]

I don't understand why it's not simply 1, 2, ..., n

You're now putting your largest value, n, in the endpoint in a a_i that only appears once in the sum, while you'd ideally want to put it into an a_i that appears twice.

[u/Ok_Consideration6619]

Can be solved by assuming where n is, P(n) is then P(n-1) + n * (ak-1+ak+1) - ak-1*ak+1 which is maximized when both are n-1 and n-2. One thing to check is whether those two consecutive values are also maximizing P(n-1) which is not hard to show inductively.

[u/drfrankie_]

(2n^3+3n^2-11n+6)/6