Connection Status:
Competition Arena > UndoHistory

UndoHistory

SRM 579 · 2012-12-13 · by vexorian

SRM 579 · 2012-12-13 · by vexorian · Greedy, Simple Search, Iteration
Class Name: UndoHistory
Return Type: int
Method Name: minPresses
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Bob is using a peculiar text editor to write a sequence of lines of text. The editor consists of three parts: a results window, a text buffer and an undo history. More details about the three parts follow.
  • The results window contains a sequence of strings: the lines of text you already wrote. Initially, the results window is empty.
  • The text buffer contains a string: the line you are writing at the moment. Initially, the string in the text buffer is empty.
  • The undo history contains a sequence of strings: all the past states of the text buffer. Initially, the undo history contains a single element: an empty string.
You are given a String[] lines. Bob would like to print the contents of lines into the results window. (At the end, the sequence of strings stored in the results window must be precisely equal to lines. Order of elements matters.) Additionally, Bob would like to do so as quickly as possible. He is able to take the following actions:
  • Bob may type a lowercase letter. The letter is appended to the text buffer. The new text buffer is then added as a new element of the undo history. (For example, if the text buffer currently contains "do", then pressing 'g' changes the text buffer to "dog" and then stores "dog" into the undo history.)
  • Bob may press Enter. When he does so, the current content of the text buffer is printed to the results window as a new line, after the lines that were printed earlier. The text buffer remains unmodified. (For example, if the text buffer contains "dog" and Bob presses Enter, "dog" will be appended to the results window, and the results buffer still contains "dog".)
  • Bob may use two mouse clicks to restore any entry from the undo history to the text buffer. This operation does not modify the undo history.
Return the minimum total number of button presses (keyboard and mouse) that Bob needs to print all the given lines into the results window.

Constraints

  • lines will contain between 1 and 50 elements, inclusive.
  • Each element of lines will contain between 1 and 50 characters, inclusive.
  • Each element of lines will contain only lowercase letters ('a'-'z').
Examples
0)
{"tomorrow", "topcoder"}
Returns: 18

Type 't'. The text buffer now contains "t", and the undo history now contains "" and "t". Type 'o'. The text buffer now contains "to", and the undo history now contains "", "t", and "to". Using six more keypresses, type the letters in "morrow". The text buffer now contains "tomorrow" and the undo history contains all prefixes of "tomorrow". The results window is still empty. Press Enter. The results window now contains one string: "tomorrow". Click the mouse twice to restore "to" from undo history. Using another six keypresses, type the letters in "pcoder". Press Enter. The results window now contains "tomorrow" and "topcoder", in this order, and we are done. The total number of button presses was 8 (typing "tomorrow") + 1 (Enter) + 2 (mouse) + 6 (typing "pcoder") + 1 (Enter) = 18.

1)
{"a","b"}
Returns: 6

After typing "a" and pressing enter, we need to restore the empty string (which is always present at the top of the undo buffer) before typing "b".

2)
{"a", "ab", "abac", "abacus" }
Returns: 10

There are times when it is not necessary to use the undo history at all.

3)
{"absolutely", "abs", "absolute"}
Returns: 17

I wonder if people would get this case wrong. Line 2 is a prefix of 3, but it is still better to use the history.

4)
{"pyramid", "sphinx", "sphere", "python", "serpent"}
Returns: 39

Submissions are judged against all 192 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class UndoHistory with a public method int minPresses(vector<string> lines) · 192 test cases · 2 s / 256 MB per case

Submitting as anonymous