You are given an input string S$[1$ : n$].$ You want to find a contiguous substring

S$[$i : j$]$ that forms the longest possible palindrome. For example, if your string

is $$YABBADABBADOO$,$ the solution would be $$ABBADABBA$.$ Design an

efficient dynamic programming algorithm to solve this problem, and analyze the

runtime.

$2$

campers. One of his plans is a mini$-$triathlon, where each participant must first

swim $20$ laps in the swimming pool, then bike $10$ miles, and finally run $3$ miles.

For safety reasons there can only be one student in the pool at a time. That

is$,$ when the triathlon begins, the first participant swims their $20$ laps, gets out

of the pool and starts biking. As soon as the first person is out of the pool, the

second participant begins to swim their $20$ laps. Once they finish swimming they

get out and start biking while the third participant starts their $20$ laps in the

pool etc. Each contestant has a projected swimming time $($the expected time it

will take them to complete $20$ laps$),$ a projected biking time $($the expected time

it will take them to complete the $10$ miles of cycling$),$ and projected running

time $($the expected time it will take them to complete the $3$ miles of running$).$

John does not want the triathlon to end too late, so he needs to come up with

a starting order of the participants that makes sure that the competition ends

as quickly as possible. Let$$s say that the completion time of a given starting

order is the time at which all participants will be finished with all three parts of

the triathlon, assuming they each perform exactly according to their projected

swimming, biking and running times. $($Note that multiple participants can and

will cycle and run simultaneously, but at most one person can be in the pool

at any time.$)$ Help out John by providing him with an efficient algorithm that

produces a starting order that leads to the earliest possible completion time.