Mixing
Dynamic programming spoj proof LISA
I was trying to solve https://www.spoj.com/problems/LISA/
In the problem, the expression is given which has only * and +. Placing bracket maximum value need to output.
like
1+2*3+4*5 = (1+2)*(3+4)*5 = 105
2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42
The implementation of 2D dynamic problem way of solving I came across is like below. Taking each number is matrix row and column and doing bottom to top approach.
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )
Like 3,5 = Max of [ (3,4) * (5,5) or (3,3)+(4,5) ]
= Max of [ 7*5 or 3+20 ]
= Max of [ 35,23 ] = 35
I am not able to prove that the result I am getting is maximum and correct. How to prove below solution is max and optimal?
-----------------------------------
C1 C2 C3 C4 C5
C1 1 3 9 13 105
C2 2 6 14 70
C3 3 7 35
C4 4 20
C5 5
algorithm dynamic-programming
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
add a comment |
I was trying to solve https://www.spoj.com/problems/LISA/
In the problem, the expression is given which has only * and +. Placing bracket maximum value need to output.
like
1+2*3+4*5 = (1+2)*(3+4)*5 = 105
2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42
The implementation of 2D dynamic problem way of solving I came across is like below. Taking each number is matrix row and column and doing bottom to top approach.
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )
Like 3,5 = Max of [ (3,4) * (5,5) or (3,3)+(4,5) ]
= Max of [ 7*5 or 3+20 ]
= Max of [ 35,23 ] = 35
I am not able to prove that the result I am getting is maximum and correct. How to prove below solution is max and optimal?
-----------------------------------
C1 C2 C3 C4 C5
C1 1 3 9 13 105
C2 2 6 14 70
C3 3 7 35
C4 4 20
C5 5
algorithm dynamic-programming
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
To me, this equation :f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )seems to be a little off. I think it needs to bef(i,j) = Max( f(i,j-1) operator c(j,j) , c(i,i) operator f( i+1,j) ). But then how would you fillf(i,j)without first gettingf(i+1, j)?
– SomeDude
Nov 19 '18 at 18:55
add a comment |
I was trying to solve https://www.spoj.com/problems/LISA/
In the problem, the expression is given which has only * and +. Placing bracket maximum value need to output.
like
1+2*3+4*5 = (1+2)*(3+4)*5 = 105
2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42
The implementation of 2D dynamic problem way of solving I came across is like below. Taking each number is matrix row and column and doing bottom to top approach.
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )
Like 3,5 = Max of [ (3,4) * (5,5) or (3,3)+(4,5) ]
= Max of [ 7*5 or 3+20 ]
= Max of [ 35,23 ] = 35
I am not able to prove that the result I am getting is maximum and correct. How to prove below solution is max and optimal?
-----------------------------------
C1 C2 C3 C4 C5
C1 1 3 9 13 105
C2 2 6 14 70
C3 3 7 35
C4 4 20
C5 5
algorithm dynamic-programming
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
I was trying to solve https://www.spoj.com/problems/LISA/
In the problem, the expression is given which has only * and +. Placing bracket maximum value need to output.
like
1+2*3+4*5 = (1+2)*(3+4)*5 = 105
2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42
The implementation of 2D dynamic problem way of solving I came across is like below. Taking each number is matrix row and column and doing bottom to top approach.
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )
Like 3,5 = Max of [ (3,4) * (5,5) or (3,3)+(4,5) ]
= Max of [ 7*5 or 3+20 ]
= Max of [ 35,23 ] = 35
I am not able to prove that the result I am getting is maximum and correct. How to prove below solution is max and optimal?
-----------------------------------
C1 C2 C3 C4 C5
C1 1 3 9 13 105
C2 2 6 14 70
C3 3 7 35
C4 4 20
C5 5
algorithm dynamic-programming
algorithm dynamic-programming
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
asked Nov 19 '18 at 15:47
Sumeet
4,59522546
4,59522546
To me, this equation :f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )seems to be a little off. I think it needs to bef(i,j) = Max( f(i,j-1) operator c(j,j) , c(i,i) operator f( i+1,j) ). But then how would you fillf(i,j)without first gettingf(i+1, j)?
– SomeDude
Nov 19 '18 at 18:55
add a comment |
To me, this equation :f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )seems to be a little off. I think it needs to bef(i,j) = Max( f(i,j-1) operator c(j,j) , c(i,i) operator f( i+1,j) ). But then how would you fillf(i,j)without first gettingf(i+1, j)?
– SomeDude
Nov 19 '18 at 18:55
To me, this equation :
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) ) seems to be a little off. I think it needs to be f(i,j) = Max( f(i,j-1) operator c(j,j) , c(i,i) operator f( i+1,j) ). But then how would you fill f(i,j) without first getting f(i+1, j)?– SomeDude
Nov 19 '18 at 18:55
To me, this equation :
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) ) seems to be a little off. I think it needs to be f(i,j) = Max( f(i,j-1) operator c(j,j) , c(i,i) operator f( i+1,j) ). But then how would you fill f(i,j) without first getting f(i+1, j)?– SomeDude
Nov 19 '18 at 18:55
add a comment |
2 Answers
2
active
oldest
votes
This is my implementation: (it assumes the query is well-formed)
class LISASolver:
def solve(self, query):
"""
takes a query, a string with numbers and +, *,
returns a tuple of min, max
"""
numbers, operators = self.parse_inputs(query)
n = len(numbers)
self.numbers = numbers
self.operators = operators
self.memo = {}
out = self.dp(0, len(numbers) - 1)
return out
def dp(self, i, j):
if i == j:
n = self.numbers[i]
return n, n
if (i, j) in self.memo:
return self.memo[(i, j)]
curmins =
curmaxs =
for k in range(i, j):
o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
leftmin, leftmax = self.dp(i, k)
rightmin, rightmax = self.dp(k + 1, j)
curmins.append(o(leftmin, rightmin))
curmaxs.append(o(leftmax, rightmax))
self.memo[(i, j)] = (min(curmins), max(curmaxs))
return self.memo[(i, j)]
def parse_inputs(self, query):
numbers =
operators =
current_number =
for c in query:
if c.isdigit():
current_number.append(c)
else:
numbers.append(
int(''.join(current_number))
)
current_number =
operators.append(c)
numbers.append(
int(''.join(current_number))
)
return numbers, operators
s = LISASolver()
query = '1+2*3+4*5'
print(s.solve(query))
>>> 27, 105
query = '2*0*3+7+1*0*3'
print(s.solve(query))
>>> 0, 42
The subproblem is the optimal min and min result of the result from the i-th number to the j-th number. The optimality is assured by calculating the min and max of the results on every subarray then apply the recurrence relation. The time complexity is O(n^3) since there are O(n^2) subproblems and each takes O(n).
Edit:
Explanation:
For dynamic programming, it's crucial to identify what is the subproblem and how a subproblem relates to other subproblems. For this problem with say n numbers (hence n - 1 operators), the subproblem is: what is the min/max value you can get by combining the numbers and operators in between the i-th number and the j-th number (inclusive).
The base case is i = j, we have only one number, the min/max is itself.
For any j > i, the subproblems to this problem is for k ranging from i to j - 1 the minimum and maximum value of the left part (subproblem with i and k as the two endpoints) and the right part (subproblem with k + 1 and j as the two endpoints). For each k what we are essentially doing is applying the k-th operator as the last operator, hence the minimum we can get for each k is the minimum of left (operator) minimum of right (similarly for maximum). (Note that the operators are either * or +, which are monotonic so we combine minimums to get minimum and maximums to get maximum. For a more generic problem with more operators such as - or / we probably need to consider a lot of cases but the basic structure should be the same). So the recurrence relations is simply
minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)
(same for max)
We have to solve each subproblem (total O(n^2) of them) for once only and cache it (or memoize it as people would say) and each subproblem requires an O(n) loop to solve. Hence the time complexity is O(n^3).
A deeper understanding of dynamic programming would really help you solve all similar problems. I suggest read something about it if you are not sure what to expect in such a setting.
answered Nov 19 '18 at 23:22
Kevin He
564415
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
I think there arensubproblems more precisely as many as number of operators and each one would takeO(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity isO(n^3)again.
– SomeDude
Nov 20 '18 at 20:16
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
add a comment |
This problem can be categorized as divide and conquer problem with memoization.
Imagine your string is s = s1 op1 s2 op2 s3 op3 s4
Now you can partition s at each op
Lets say you partition s at op1 to give you two strings :
Left string : s1 and
Right string : s2 op2 s3 op3 s4.
Lets say the minimum, maximum value that can be obtained for left string are min1, max1
and for right string are : min2, max2.
You might think that min1 op1 min2 is minimum and max1 op1 max2 is maximum
But not yet done.
You need to do it for each op and accumulate values for min and max. Why? Because the partition at op1 might not be optimal.
Then out of all those partitions, pick the min(mins) and max(maxs)
You could recursively implement this with remembering the results in Java like:
private static int recurse( String input, Map<String, int> map ) {
if ( map.containsKey(input) ) {
return map.get(input);
}
int ans = null;
List<Integer> mins = new ArrayList<>();
List<Integer> maxs = new ArrayList<>();
for ( int i = 0; i < input.length(); i++ ) {
if ( !Character.isDigit( input.charAt(i) ) ) {
String left = input.substring(0, i);
String right = input.substring(i+1);
int leftResult = recurse(left, map);
int rightResult = recurse(right, map);
int leftMin = leftResult[0];
int leftMax = leftResult[1];
int rightMin = rightResult[0];
int rightMax = rightResult[1];
switch( input.charAt(i) )
{
case '+':
mins.add( leftMin + rightMin );
maxs.add( leftMax + rightMax );
break;
case '*':
mins.add( leftMin*rightMin );
maxs.add( leftMax*rightMax );
break;
default:
break;
}
}
}
if ( mins.isEmpty() || maxs.isEmpty() ) {
ans = new int{Integer.valueOf(input), Integer.valueOf(input)};
} else {
ans[0] = Integer.MAX_VALUE;
ans[1] = Integer.MIN_VALUE;
for ( int i = 0; i < mins.size(); i++ ) {
ans[0] = Math.min( ans[0], mins.get(i) );
ans[1] = Math.max( ans[1], maxs.get(i) );
}
}
map.put( input, ans );
return ans;
}
private static void getMinMax( String in ) {
if ( in.isEmpty() ) {
System.out.println("0 0");
return;
}
int ans = recurse(in, new HashMap<String, int>() );
System.out.println(ans[1] + " " + ans[0]);
}
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53378199%2fdynamic-programming-spoj-proof-lisa%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is my implementation: (it assumes the query is well-formed)
class LISASolver:
def solve(self, query):
"""
takes a query, a string with numbers and +, *,
returns a tuple of min, max
"""
numbers, operators = self.parse_inputs(query)
n = len(numbers)
self.numbers = numbers
self.operators = operators
self.memo = {}
out = self.dp(0, len(numbers) - 1)
return out
def dp(self, i, j):
if i == j:
n = self.numbers[i]
return n, n
if (i, j) in self.memo:
return self.memo[(i, j)]
curmins =
curmaxs =
for k in range(i, j):
o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
leftmin, leftmax = self.dp(i, k)
rightmin, rightmax = self.dp(k + 1, j)
curmins.append(o(leftmin, rightmin))
curmaxs.append(o(leftmax, rightmax))
self.memo[(i, j)] = (min(curmins), max(curmaxs))
return self.memo[(i, j)]
def parse_inputs(self, query):
numbers =
operators =
current_number =
for c in query:
if c.isdigit():
current_number.append(c)
else:
numbers.append(
int(''.join(current_number))
)
current_number =
operators.append(c)
numbers.append(
int(''.join(current_number))
)
return numbers, operators
s = LISASolver()
query = '1+2*3+4*5'
print(s.solve(query))
>>> 27, 105
query = '2*0*3+7+1*0*3'
print(s.solve(query))
>>> 0, 42
The subproblem is the optimal min and min result of the result from the i-th number to the j-th number. The optimality is assured by calculating the min and max of the results on every subarray then apply the recurrence relation. The time complexity is O(n^3) since there are O(n^2) subproblems and each takes O(n).
Edit:
Explanation:
For dynamic programming, it's crucial to identify what is the subproblem and how a subproblem relates to other subproblems. For this problem with say n numbers (hence n - 1 operators), the subproblem is: what is the min/max value you can get by combining the numbers and operators in between the i-th number and the j-th number (inclusive).
The base case is i = j, we have only one number, the min/max is itself.
For any j > i, the subproblems to this problem is for k ranging from i to j - 1 the minimum and maximum value of the left part (subproblem with i and k as the two endpoints) and the right part (subproblem with k + 1 and j as the two endpoints). For each k what we are essentially doing is applying the k-th operator as the last operator, hence the minimum we can get for each k is the minimum of left (operator) minimum of right (similarly for maximum). (Note that the operators are either * or +, which are monotonic so we combine minimums to get minimum and maximums to get maximum. For a more generic problem with more operators such as - or / we probably need to consider a lot of cases but the basic structure should be the same). So the recurrence relations is simply
minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)
(same for max)
We have to solve each subproblem (total O(n^2) of them) for once only and cache it (or memoize it as people would say) and each subproblem requires an O(n) loop to solve. Hence the time complexity is O(n^3).
A deeper understanding of dynamic programming would really help you solve all similar problems. I suggest read something about it if you are not sure what to expect in such a setting.
answered Nov 19 '18 at 23:22
Kevin He
564415
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
I think there arensubproblems more precisely as many as number of operators and each one would takeO(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity isO(n^3)again.
– SomeDude
Nov 20 '18 at 20:16
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
add a comment |
This is my implementation: (it assumes the query is well-formed)
class LISASolver:
def solve(self, query):
"""
takes a query, a string with numbers and +, *,
returns a tuple of min, max
"""
numbers, operators = self.parse_inputs(query)
n = len(numbers)
self.numbers = numbers
self.operators = operators
self.memo = {}
out = self.dp(0, len(numbers) - 1)
return out
def dp(self, i, j):
if i == j:
n = self.numbers[i]
return n, n
if (i, j) in self.memo:
return self.memo[(i, j)]
curmins =
curmaxs =
for k in range(i, j):
o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
leftmin, leftmax = self.dp(i, k)
rightmin, rightmax = self.dp(k + 1, j)
curmins.append(o(leftmin, rightmin))
curmaxs.append(o(leftmax, rightmax))
self.memo[(i, j)] = (min(curmins), max(curmaxs))
return self.memo[(i, j)]
def parse_inputs(self, query):
numbers =
operators =
current_number =
for c in query:
if c.isdigit():
current_number.append(c)
else:
numbers.append(
int(''.join(current_number))
)
current_number =
operators.append(c)
numbers.append(
int(''.join(current_number))
)
return numbers, operators
s = LISASolver()
query = '1+2*3+4*5'
print(s.solve(query))
>>> 27, 105
query = '2*0*3+7+1*0*3'
print(s.solve(query))
>>> 0, 42
The subproblem is the optimal min and min result of the result from the i-th number to the j-th number. The optimality is assured by calculating the min and max of the results on every subarray then apply the recurrence relation. The time complexity is O(n^3) since there are O(n^2) subproblems and each takes O(n).
Edit:
Explanation:
For dynamic programming, it's crucial to identify what is the subproblem and how a subproblem relates to other subproblems. For this problem with say n numbers (hence n - 1 operators), the subproblem is: what is the min/max value you can get by combining the numbers and operators in between the i-th number and the j-th number (inclusive).
The base case is i = j, we have only one number, the min/max is itself.
For any j > i, the subproblems to this problem is for k ranging from i to j - 1 the minimum and maximum value of the left part (subproblem with i and k as the two endpoints) and the right part (subproblem with k + 1 and j as the two endpoints). For each k what we are essentially doing is applying the k-th operator as the last operator, hence the minimum we can get for each k is the minimum of left (operator) minimum of right (similarly for maximum). (Note that the operators are either * or +, which are monotonic so we combine minimums to get minimum and maximums to get maximum. For a more generic problem with more operators such as - or / we probably need to consider a lot of cases but the basic structure should be the same). So the recurrence relations is simply
minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)
(same for max)
We have to solve each subproblem (total O(n^2) of them) for once only and cache it (or memoize it as people would say) and each subproblem requires an O(n) loop to solve. Hence the time complexity is O(n^3).
A deeper understanding of dynamic programming would really help you solve all similar problems. I suggest read something about it if you are not sure what to expect in such a setting.
answered Nov 19 '18 at 23:22
Kevin He
564415
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
I think there arensubproblems more precisely as many as number of operators and each one would takeO(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity isO(n^3)again.
– SomeDude
Nov 20 '18 at 20:16
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
add a comment |
This is my implementation: (it assumes the query is well-formed)
class LISASolver:
def solve(self, query):
"""
takes a query, a string with numbers and +, *,
returns a tuple of min, max
"""
numbers, operators = self.parse_inputs(query)
n = len(numbers)
self.numbers = numbers
self.operators = operators
self.memo = {}
out = self.dp(0, len(numbers) - 1)
return out
def dp(self, i, j):
if i == j:
n = self.numbers[i]
return n, n
if (i, j) in self.memo:
return self.memo[(i, j)]
curmins =
curmaxs =
for k in range(i, j):
o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
leftmin, leftmax = self.dp(i, k)
rightmin, rightmax = self.dp(k + 1, j)
curmins.append(o(leftmin, rightmin))
curmaxs.append(o(leftmax, rightmax))
self.memo[(i, j)] = (min(curmins), max(curmaxs))
return self.memo[(i, j)]
def parse_inputs(self, query):
numbers =
operators =
current_number =
for c in query:
if c.isdigit():
current_number.append(c)
else:
numbers.append(
int(''.join(current_number))
)
current_number =
operators.append(c)
numbers.append(
int(''.join(current_number))
)
return numbers, operators
s = LISASolver()
query = '1+2*3+4*5'
print(s.solve(query))
>>> 27, 105
query = '2*0*3+7+1*0*3'
print(s.solve(query))
>>> 0, 42
The subproblem is the optimal min and min result of the result from the i-th number to the j-th number. The optimality is assured by calculating the min and max of the results on every subarray then apply the recurrence relation. The time complexity is O(n^3) since there are O(n^2) subproblems and each takes O(n).
Edit:
Explanation:
For dynamic programming, it's crucial to identify what is the subproblem and how a subproblem relates to other subproblems. For this problem with say n numbers (hence n - 1 operators), the subproblem is: what is the min/max value you can get by combining the numbers and operators in between the i-th number and the j-th number (inclusive).
The base case is i = j, we have only one number, the min/max is itself.
For any j > i, the subproblems to this problem is for k ranging from i to j - 1 the minimum and maximum value of the left part (subproblem with i and k as the two endpoints) and the right part (subproblem with k + 1 and j as the two endpoints). For each k what we are essentially doing is applying the k-th operator as the last operator, hence the minimum we can get for each k is the minimum of left (operator) minimum of right (similarly for maximum). (Note that the operators are either * or +, which are monotonic so we combine minimums to get minimum and maximums to get maximum. For a more generic problem with more operators such as - or / we probably need to consider a lot of cases but the basic structure should be the same). So the recurrence relations is simply
minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)
(same for max)
We have to solve each subproblem (total O(n^2) of them) for once only and cache it (or memoize it as people would say) and each subproblem requires an O(n) loop to solve. Hence the time complexity is O(n^3).
A deeper understanding of dynamic programming would really help you solve all similar problems. I suggest read something about it if you are not sure what to expect in such a setting.
answered Nov 19 '18 at 23:22
Kevin He
564415
This is my implementation: (it assumes the query is well-formed)
class LISASolver:
def solve(self, query):
"""
takes a query, a string with numbers and +, *,
returns a tuple of min, max
"""
numbers, operators = self.parse_inputs(query)
n = len(numbers)
self.numbers = numbers
self.operators = operators
self.memo = {}
out = self.dp(0, len(numbers) - 1)
return out
def dp(self, i, j):
if i == j:
n = self.numbers[i]
return n, n
if (i, j) in self.memo:
return self.memo[(i, j)]
curmins =
curmaxs =
for k in range(i, j):
o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
leftmin, leftmax = self.dp(i, k)
rightmin, rightmax = self.dp(k + 1, j)
curmins.append(o(leftmin, rightmin))
curmaxs.append(o(leftmax, rightmax))
self.memo[(i, j)] = (min(curmins), max(curmaxs))
return self.memo[(i, j)]
def parse_inputs(self, query):
numbers =
operators =
current_number =
for c in query:
if c.isdigit():
current_number.append(c)
else:
numbers.append(
int(''.join(current_number))
)
current_number =
operators.append(c)
numbers.append(
int(''.join(current_number))
)
return numbers, operators
s = LISASolver()
query = '1+2*3+4*5'
print(s.solve(query))
>>> 27, 105
query = '2*0*3+7+1*0*3'
print(s.solve(query))
>>> 0, 42
The subproblem is the optimal min and min result of the result from the i-th number to the j-th number. The optimality is assured by calculating the min and max of the results on every subarray then apply the recurrence relation. The time complexity is O(n^3) since there are O(n^2) subproblems and each takes O(n).
Edit:
Explanation:
For dynamic programming, it's crucial to identify what is the subproblem and how a subproblem relates to other subproblems. For this problem with say n numbers (hence n - 1 operators), the subproblem is: what is the min/max value you can get by combining the numbers and operators in between the i-th number and the j-th number (inclusive).
The base case is i = j, we have only one number, the min/max is itself.
For any j > i, the subproblems to this problem is for k ranging from i to j - 1 the minimum and maximum value of the left part (subproblem with i and k as the two endpoints) and the right part (subproblem with k + 1 and j as the two endpoints). For each k what we are essentially doing is applying the k-th operator as the last operator, hence the minimum we can get for each k is the minimum of left (operator) minimum of right (similarly for maximum). (Note that the operators are either * or +, which are monotonic so we combine minimums to get minimum and maximums to get maximum. For a more generic problem with more operators such as - or / we probably need to consider a lot of cases but the basic structure should be the same). So the recurrence relations is simply
minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)
(same for max)
We have to solve each subproblem (total O(n^2) of them) for once only and cache it (or memoize it as people would say) and each subproblem requires an O(n) loop to solve. Hence the time complexity is O(n^3).
A deeper understanding of dynamic programming would really help you solve all similar problems. I suggest read something about it if you are not sure what to expect in such a setting.
answered Nov 19 '18 at 23:22
Kevin He
564415
edited Nov 20 '18 at 18:31
answered Nov 19 '18 at 23:22
Kevin He
564415
answered Nov 19 '18 at 23:22
Kevin He
564415
answered Nov 19 '18 at 23:22
Kevin He
564415
564415
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
I think there arensubproblems more precisely as many as number of operators and each one would takeO(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity isO(n^3)again.
– SomeDude
Nov 20 '18 at 20:16
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
add a comment |
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
I think there arensubproblems more precisely as many as number of operators and each one would takeO(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity isO(n^3)again.
– SomeDude
Nov 20 '18 at 20:16
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
It would help OP if you can explain your implementation.
– SomeDude
Nov 20 '18 at 1:05
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Can you explain the algorithm in detail?
– Sumeet
Nov 20 '18 at 3:17
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
Nice explanation. Upvoted.
– SomeDude
Nov 20 '18 at 20:07
I think there are
n subproblems more precisely as many as number of operators and each one would take O(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity is O(n^3) again.– SomeDude
Nov 20 '18 at 20:16
I think there are
n subproblems more precisely as many as number of operators and each one would take O(n^2), because once you divide a string into two parts, each one would end up in a list and you need to consider every combination of the values in that list. Total complexity is O(n^3) again.– SomeDude
Nov 20 '18 at 20:16
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
That's an alternative way to solve it. Both are valid.
– Kevin He
Nov 20 '18 at 21:58
add a comment |
This problem can be categorized as divide and conquer problem with memoization.
Imagine your string is s = s1 op1 s2 op2 s3 op3 s4
Now you can partition s at each op
Lets say you partition s at op1 to give you two strings :
Left string : s1 and
Right string : s2 op2 s3 op3 s4.
Lets say the minimum, maximum value that can be obtained for left string are min1, max1
and for right string are : min2, max2.
You might think that min1 op1 min2 is minimum and max1 op1 max2 is maximum
But not yet done.
You need to do it for each op and accumulate values for min and max. Why? Because the partition at op1 might not be optimal.
Then out of all those partitions, pick the min(mins) and max(maxs)
You could recursively implement this with remembering the results in Java like:
private static int recurse( String input, Map<String, int> map ) {
if ( map.containsKey(input) ) {
return map.get(input);
}
int ans = null;
List<Integer> mins = new ArrayList<>();
List<Integer> maxs = new ArrayList<>();
for ( int i = 0; i < input.length(); i++ ) {
if ( !Character.isDigit( input.charAt(i) ) ) {
String left = input.substring(0, i);
String right = input.substring(i+1);
int leftResult = recurse(left, map);
int rightResult = recurse(right, map);
int leftMin = leftResult[0];
int leftMax = leftResult[1];
int rightMin = rightResult[0];
int rightMax = rightResult[1];
switch( input.charAt(i) )
{
case '+':
mins.add( leftMin + rightMin );
maxs.add( leftMax + rightMax );
break;
case '*':
mins.add( leftMin*rightMin );
maxs.add( leftMax*rightMax );
break;
default:
break;
}
}
}
if ( mins.isEmpty() || maxs.isEmpty() ) {
ans = new int{Integer.valueOf(input), Integer.valueOf(input)};
} else {
ans[0] = Integer.MAX_VALUE;
ans[1] = Integer.MIN_VALUE;
for ( int i = 0; i < mins.size(); i++ ) {
ans[0] = Math.min( ans[0], mins.get(i) );
ans[1] = Math.max( ans[1], maxs.get(i) );
}
}
map.put( input, ans );
return ans;
}
private static void getMinMax( String in ) {
if ( in.isEmpty() ) {
System.out.println("0 0");
return;
}
int ans = recurse(in, new HashMap<String, int>() );
System.out.println(ans[1] + " " + ans[0]);
}
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
add a comment |
This problem can be categorized as divide and conquer problem with memoization.
Imagine your string is s = s1 op1 s2 op2 s3 op3 s4
Now you can partition s at each op
Lets say you partition s at op1 to give you two strings :
Left string : s1 and
Right string : s2 op2 s3 op3 s4.
Lets say the minimum, maximum value that can be obtained for left string are min1, max1
and for right string are : min2, max2.
You might think that min1 op1 min2 is minimum and max1 op1 max2 is maximum
But not yet done.
You need to do it for each op and accumulate values for min and max. Why? Because the partition at op1 might not be optimal.
Then out of all those partitions, pick the min(mins) and max(maxs)
You could recursively implement this with remembering the results in Java like:
private static int recurse( String input, Map<String, int> map ) {
if ( map.containsKey(input) ) {
return map.get(input);
}
int ans = null;
List<Integer> mins = new ArrayList<>();
List<Integer> maxs = new ArrayList<>();
for ( int i = 0; i < input.length(); i++ ) {
if ( !Character.isDigit( input.charAt(i) ) ) {
String left = input.substring(0, i);
String right = input.substring(i+1);
int leftResult = recurse(left, map);
int rightResult = recurse(right, map);
int leftMin = leftResult[0];
int leftMax = leftResult[1];
int rightMin = rightResult[0];
int rightMax = rightResult[1];
switch( input.charAt(i) )
{
case '+':
mins.add( leftMin + rightMin );
maxs.add( leftMax + rightMax );
break;
case '*':
mins.add( leftMin*rightMin );
maxs.add( leftMax*rightMax );
break;
default:
break;
}
}
}
if ( mins.isEmpty() || maxs.isEmpty() ) {
ans = new int{Integer.valueOf(input), Integer.valueOf(input)};
} else {
ans[0] = Integer.MAX_VALUE;
ans[1] = Integer.MIN_VALUE;
for ( int i = 0; i < mins.size(); i++ ) {
ans[0] = Math.min( ans[0], mins.get(i) );
ans[1] = Math.max( ans[1], maxs.get(i) );
}
}
map.put( input, ans );
return ans;
}
private static void getMinMax( String in ) {
if ( in.isEmpty() ) {
System.out.println("0 0");
return;
}
int ans = recurse(in, new HashMap<String, int>() );
System.out.println(ans[1] + " " + ans[0]);
}
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
add a comment |
This problem can be categorized as divide and conquer problem with memoization.
Imagine your string is s = s1 op1 s2 op2 s3 op3 s4
Now you can partition s at each op
Lets say you partition s at op1 to give you two strings :
Left string : s1 and
Right string : s2 op2 s3 op3 s4.
Lets say the minimum, maximum value that can be obtained for left string are min1, max1
and for right string are : min2, max2.
You might think that min1 op1 min2 is minimum and max1 op1 max2 is maximum
But not yet done.
You need to do it for each op and accumulate values for min and max. Why? Because the partition at op1 might not be optimal.
Then out of all those partitions, pick the min(mins) and max(maxs)
You could recursively implement this with remembering the results in Java like:
private static int recurse( String input, Map<String, int> map ) {
if ( map.containsKey(input) ) {
return map.get(input);
}
int ans = null;
List<Integer> mins = new ArrayList<>();
List<Integer> maxs = new ArrayList<>();
for ( int i = 0; i < input.length(); i++ ) {
if ( !Character.isDigit( input.charAt(i) ) ) {
String left = input.substring(0, i);
String right = input.substring(i+1);
int leftResult = recurse(left, map);
int rightResult = recurse(right, map);
int leftMin = leftResult[0];
int leftMax = leftResult[1];
int rightMin = rightResult[0];
int rightMax = rightResult[1];
switch( input.charAt(i) )
{
case '+':
mins.add( leftMin + rightMin );
maxs.add( leftMax + rightMax );
break;
case '*':
mins.add( leftMin*rightMin );
maxs.add( leftMax*rightMax );
break;
default:
break;
}
}
}
if ( mins.isEmpty() || maxs.isEmpty() ) {
ans = new int{Integer.valueOf(input), Integer.valueOf(input)};
} else {
ans[0] = Integer.MAX_VALUE;
ans[1] = Integer.MIN_VALUE;
for ( int i = 0; i < mins.size(); i++ ) {
ans[0] = Math.min( ans[0], mins.get(i) );
ans[1] = Math.max( ans[1], maxs.get(i) );
}
}
map.put( input, ans );
return ans;
}
private static void getMinMax( String in ) {
if ( in.isEmpty() ) {
System.out.println("0 0");
return;
}
int ans = recurse(in, new HashMap<String, int>() );
System.out.println(ans[1] + " " + ans[0]);
}
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
This problem can be categorized as divide and conquer problem with memoization.
Imagine your string is s = s1 op1 s2 op2 s3 op3 s4
Now you can partition s at each op
Lets say you partition s at op1 to give you two strings :
Left string : s1 and
Right string : s2 op2 s3 op3 s4.
Lets say the minimum, maximum value that can be obtained for left string are min1, max1
and for right string are : min2, max2.
You might think that min1 op1 min2 is minimum and max1 op1 max2 is maximum
But not yet done.
You need to do it for each op and accumulate values for min and max. Why? Because the partition at op1 might not be optimal.
Then out of all those partitions, pick the min(mins) and max(maxs)
You could recursively implement this with remembering the results in Java like:
private static int recurse( String input, Map<String, int> map ) {
if ( map.containsKey(input) ) {
return map.get(input);
}
int ans = null;
List<Integer> mins = new ArrayList<>();
List<Integer> maxs = new ArrayList<>();
for ( int i = 0; i < input.length(); i++ ) {
if ( !Character.isDigit( input.charAt(i) ) ) {
String left = input.substring(0, i);
String right = input.substring(i+1);
int leftResult = recurse(left, map);
int rightResult = recurse(right, map);
int leftMin = leftResult[0];
int leftMax = leftResult[1];
int rightMin = rightResult[0];
int rightMax = rightResult[1];
switch( input.charAt(i) )
{
case '+':
mins.add( leftMin + rightMin );
maxs.add( leftMax + rightMax );
break;
case '*':
mins.add( leftMin*rightMin );
maxs.add( leftMax*rightMax );
break;
default:
break;
}
}
}
if ( mins.isEmpty() || maxs.isEmpty() ) {
ans = new int{Integer.valueOf(input), Integer.valueOf(input)};
} else {
ans[0] = Integer.MAX_VALUE;
ans[1] = Integer.MIN_VALUE;
for ( int i = 0; i < mins.size(); i++ ) {
ans[0] = Math.min( ans[0], mins.get(i) );
ans[1] = Math.max( ans[1], maxs.get(i) );
}
}
map.put( input, ans );
return ans;
}
private static void getMinMax( String in ) {
if ( in.isEmpty() ) {
System.out.println("0 0");
return;
}
int ans = recurse(in, new HashMap<String, int>() );
System.out.println(ans[1] + " " + ans[0]);
}
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
edited Nov 20 '18 at 20:05
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
answered Nov 19 '18 at 19:50
SomeDude
4,33531327
4,33531327
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53378199%2fdynamic-programming-spoj-proof-lisa%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
To me, this equation :
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )seems to be a little off. I think it needs to bef(i,j) = Max( f(i,j-1) operator c(j,j) , c(i,i) operator f( i+1,j) ). But then how would you fillf(i,j)without first gettingf(i+1, j)?– SomeDude
Nov 19 '18 at 18:55