Connection Status:
Competition Arena > Undo

Undo

SRM 419 · 2008-09-24 · by andrewzta

SRM 419 · 2008-09-24 · by andrewzta · Simulation, String Manipulation, String Parsing
Class Name: Undo
Return Type: String
Method Name: getText
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

You are writing a simple text editor that supports only the following two commands:

  • "type c" where c is a character: Append character c to the end of the current text.
  • "undo t" where t is an integer: Undo all operations that were performed in the previous t seconds in reverse order.

All quotes are for clarity only. The text in the editor is initially empty.

For example, consider the following sequence of commands: 

Second 1: type a
Second 2: type b
Second 3: type c
Second 5: undo 3

At the end of second 3, the text is "abc". At second 5, all commands performed in the previous 3 seconds are undone in reverse order. This means 'c' is removed, and then 'b' is removed. The text becomes just "a".

Note that "undo" commands can also be undone. For example: 

Second 1: type a
Second 2: type b
Second 3: undo 2
Second 4: undo 2

After second 2, the text is "ab". After second 3, everything is undone, and the text becomes empty. At second 4, the previous "undo" is undone, so the text becomes "ab" again. Then, the "type b" is also undone and the text becomes just "a".

You are given a String[] commands and a int[] time. Each element of commands is a single command, and commands[i] is performed at time[i]. The commands are given in chronological order. Return the text after all the commands are executed.

Constraints

  • commands will contain between 1 and 50 elements, inclusive.
  • Each element of commands will be either "type c" where c is a lowercase letter ('a'-'z') or "undo t" where t is an integer between 1 and 10^9, inclusive, with no leading zeroes (quotes for clarity only).
  • time will contain the same number of elements as commands.
  • Each element of time will be between 1 and 10^9, inclusive.
  • The elements of time will be in strictly ascending order.
Examples
0)
{"type a", "type b", "type c", "undo 3"}
{1, 2, 3, 5}
Returns: "a"

The first example from the problem statement.

1)
{"type a", "type b", "undo 2", "undo 2"}
{1,2,3,4}
Returns: "a"

The second example from the problem statement.

2)
{"type a", "undo 1", "undo 1"}
{1,2,3}
Returns: "a"
3)
{"type a", "type b", "type c", "undo 10"}
{1, 2, 3, 1000}
Returns: "abc"

Note that "undo" can undo nothing if it is too late.

4)
{"undo 1"}
{1}
Returns: ""

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

Coding Area

Language: C++17 · define a public class Undo with a public method string getText(vector<string> commands, vector<int> time) · 203 test cases · 2 s / 256 MB per case

Submitting as anonymous