Problem 6. (20 points) Texting. You are competing with your friends to type text messages on your...

Problem 6. (20 points) Texting. You are competing with your friends to type text messages on your smartphone as quickly as possible. Here are the rules: you use two thumbs for texting and they start out on the bottom left and bottom right keys of the keyboard. To type a character, you move either thumb from its current key to the key you need to press, and it takes time equal to the distance between the keys. You can assume the following: The keyboard has keys labeled (1,2,...,k) and there is a function dist(i.j) to calculate the distance between two keys i and j. (To visualize this, you may want to imagine the digits 1 through 9 arranged on a standard numeric keypad). . Your left thumb starts on key a, and your right thumb starts on key b. (For example, on the 9-digit numeric keypad, a-7 is the bottom left key, and b 9 is the bottom right key.) . You can press any key with either thumb . Both thumbs can rest on the same key if necessary The characters to by typed are ciccn, where c E 1,2,.. , k is the ith key to push omework 4 3 Design an algorithm that finds the fastest way to type the message. In other words, your algorithm needs to decide which thumb to use to type each character, and it should minimize the total distance moved by your two thumbs. Try to use O(nk2) time. Example. Imagine the 9-digit numeric keypad where your thumbs start at a 7 and b 9, with input message cic2c3 589. The solution "left, right, left" would look like this: 0 Left/right thumbs start at 7/9 1. Left thumb moves from 7 to ci 5. Time dist(7, 5). Thumbs end at 5/9. 2. Right thumb moves from 9 to c2-8. Time- dist(9, 8). Thumbs end at 5/8. 3. Left thumb moves from 5 to c 9. Time dist(5, 9). Thumbs end at 9/8. Total time dist(7, 5) + dist(9, 8) + dist(5, 9)