Optimal Division


I think this problem's check has an error.
Consider Input [1,1,1,2] ,output "1/(1/1/2)" and "1/1/(1/2)" should be both correct , with answer "1/(1/(1/2))" wrong("Your expression should NOT contain redundant parenthesis.").
However, when I am hacking other's solution using Input [1,1,1,1,1,1,1,1,1,2], I found that sometimes the standard program outputs "1/(1/(1/(1/(1/(1/(1/(1/1/2)))))))", with redundant parenthesis, and answer "1/1/1/1/1/1/1/1/(1/2)" Unaccepted.
By the way,Brute Force will not always get Time Limit Exceeded if you write this algorithm well (but the accuracy error is a big problem when you calculating the expression)
(Sorry for my poor English

@zhangz5434 You are right when input has 1. So the problem is designed that the input start from 2. See the note please.

@fallcreek TAT. But when I was post challenges, the checker didn't told me that the input was invalid...
So I hacked many people with a wrong input...

@zhangz5434 That's my fault. Sorry for that. The standard solution didn't check for input in this problem.

I have a AC DP solution
time complexity O(n^3), space complexity O(n^2)
Maybe you can have a look.


@zizhengwu we are dividing list into two parts left and right. We need not have to add parenthesis in the left part as divide operator is left associative but we have to add parenthesis on the right part except last number.

@sean46 I have revised the complexity analysis for #2. If you have any questions, please let me know. Thanks.

Thanks @vinod23. As @zizhengwu mentioned earlier, can we maybe add some more explanation as to why our solution doesn't have redundant parenthesis?



your math proof is far from perfect... If a0/.../an = p/q. how do you know p has to be a0 and q has to be (a1/.../an)?
as a learner of algebraic number theory, I will give the following proper proof:
we shall prove maximum number is the following number:
(a0a2...*an)/a1
we need the simple fact that any sequence a0/.../an with any parenthesis added can be reduced to a simple fraction p/q, where p, q are products of (partitioned) elements in the sequence. using induction we can easily show this fact (just argue when n = 1 and use complete induction). furthermore, we can extract a useful lemma from the induction that a0 always occurs in p (in the numerator product)
then it suffices to show a1 must be in q (the denominator), that if q = a1, i.e., a1 is the only element in q, then the theorem will be proved as q is minimized.
we now discuss two cases around a1:
a) a1 is associate to the left division: in this case, the sequence has form (a0/a1)/.../an, then view (a0/a1) as a single element and use the lemma, we know if (a0/a1)/.../an = p'/q', then (a0/a1) must be in p', so after a single step of simplification, we have a1 must be in the denominator.
b) a1 is associate to the right division: in this case the sequence has form a0/(a1/.../an), then apply lemma on the sequence a1/.../an, we have if a1/.../an = p'/q', then a1 must be in p', so after a single step of simplification, we have a1 also must be in the denominator.
In each case, we have a1 must be in the denominator product, regardless how we add the parenthesis. Hence the theorem is proved.
QED.

@vinod23, for the approach #1 & #2, there are two places can be optimized, see details below:
 Remove "String res" from signature of method optimal();
 Remove repeated statement of
(i + 1 != end ? "(" : "")
, here is my sample:
String lb, rb; for (int i = start; i < end; i++) { //Recursive calls T left = optimal(nums, start, i); T right = optimal(nums, i + 1, end); lb = i + 1 == end ? "" : "("; rb = i + 1 == end ? "" : ")"; if (t.min > left.min / right.max) { t.min = left.min / right.max; t.minStr = left.minStr + "/" + lb + right.maxStr + rb; } if (t.max < left.max / right.min) { t.max = left.max / right.min; t.maxStr = left.maxStr + "/" + lb + right.minStr + rb; } }