PNOI 2k8 Problem E: Text Messages

Problems from PNOI2008

Type: string
Difficulty: easy-medium, tedious

This problem was probably overlooked due to its position: since the easiest problems came earlier, and some harder problems came before this, it can be supposed that this was assumed to be harder than on first blush. The tediousness in this problem is in the encoding of the key-press map, whereas in problem C it is in the output formatting.

The key idea here is not only to be able to translate characters into key-presses, but to be able to determine which sequences of characters require additional key-presses. Dr. Pablo Manalastas, head judge of PNOI 2k8, and whose daughter suggested this problem, suggests the use of an array of structures, each structure storing the number of the button to press and the number of times that button has to be pressed to generate the character. My own approach is a little more convoluted, but only relies on a reference string and some mathematical overhead.

To determine both the button and the button-press multiplicity, we can use a function that returns a number that stores both pieces of information:

int button_and_multiplicity(char ch) {
  return index of position of ch in "abc2ghi3jkl4mno5pqrstuv8wxyz "
}

The number returned is [(B - 2) * 4] + (P - 1) where B is the number of the button to press and P is the number of times the button is pressed, noting that the function returns 0 for a. The numbers are there to space the characters properly, since only s and z require four key-presses.

Then, the process is simply to read through every character and adding the number of key-presses, noting that if the current character and the one before it are on the same button, an additional key-press is required:

prevChar = -1;
pressCount = 0;
for (index = 0; index < length(message); index ++) {
  thisChar = button_and_multiplicity(charAt(message, index));
  if (prevChar / 4 == thisChar / 4)
    pressCount ++;
  pressCount += (thisChar % 4) + 1;
  prevChar = thisChar;
}

prevChar is initially set to -1, since the first character does not compare with any character before it; the last statement makes the current character-value become the value of the previous character, for the next comparison. When dividing integers, the result is an integer, without the decimals, if there are any. That is why dividing the result of the function gives the number of the button that is pressed minus two.

This approach may not be obvious, but experience will determine if you can use it and how to set up such a reference string and then such a function.