srikarbs
BAN USERAt each step either the left most set of continuous occupants (L) need to be moved to right or the right most set of continuous occupants(R) needs to be moved to left.
We can be greedy and chose the smaller group.
Reasoning:Eventually the gap needs to be bridged between L & R. assume L is the smaller group. If in optimal solution L is not moved right, (R+(Total - L -R) which is > R > L) need to be moved to left as a last step. Which is costlier than moving L to right. This means L moving right in last steps gives a better solution. This contradicts that L is not moved right in solution.
Solution: in each step move lower of L, R to right or left respectively. Add new next continuous merged block to L or R respectively. Continue till L meets R.
Python code:
#left is number of continuous occupants to left of rest of seats to be looked into
#right is number of continuous occupants to right of rest of seats to be looked into
#b is left index of seats yet to be looked into
#e is right index of seats yet to be looked into
def cost(left, right, b, e):
if (b == e):
return 0
nl = left+summary[b]
nr = right+summary[e];
if (nl <= nr):
return nl * summary[b+1] + cost(nl, right, b + 2, e)
else:
return nr * summary[e-1] + cost(left, nr, b, e-2)
seating = get_string_from_user("Enter seat occupancy string: ");
#seating = "...XXX..XX.XXXX...."
print seating
summary = [];
inplen = len(seating)
summary.append(0);
j = 0;
prev = 'X'
dpa={}
# build summary array that contains alternating counts of occupied sets and empty seats
# always starts with occupied seats and ends with occupied seats
for i in range (inplen):
if (seating[i] == prev):
summary[j] = summary[j] + 1
else:
prev = seating[i]
summary.append(1)
j = j+1
if(seating[inplen-1] == '.'):
j = j + 1
summary.append(0)
print summary
print cost(0, 0, 0, j)
2 + OPT(i+1, j-1) if A[i] = A[j] is incorrect it would fail a test case "HabobeH" - it will return 5 as the answer, while it should have been 3.
- srikarbs November 06, 2014it is
2 + OPT(i+1, j-1) if j > i + 1 and A[i]=A[j] and OPT(i+1,j-1) == j-i-1)
2 if j == i + 1 and A[i]=A[j]