## Problem

You are provided with four possible operations that can be done on the editor(each operation requires 1 keyboard hit)- A
- Ctrl+A
- Ctrl+C
- Ctrl+V

## Algorithm

The first intuition on seeing this problem is we should use dynamic programming, as this problem has a clear structure of sub-problems. A straightforward trial is to distinguish different cases by the last operation. Nevertheless, difficulty arises when the last operation is Ctrl+V and the second last operation is not Ctrl+C.In order to solve this problem, we have to further dissect the properties of an optimal edit sequence:

- Ctrl+A always immediately precedes Ctrl+C, otherwise it cannot be optimal.
- If a Ctrl+V follows an A, it is safe to push Ctrl+A backward to bypass A.
- If a combo Ctrl+A Ctrl+C precedes an A, it is better to push the combo forward to bypass A. That is the original edit sequence cannot be optimal.

As a consequence, if we denote the longest sequence of n operations by C(n), the recursion can be expressed as:

$$C(n) = max(1+ C(n-1), max_{i}((i+1)\times C(n-2-i)))$$

in which \(1+C(n-1)\) is for the case when the last operation is A, and the latter part is for the case when a continuous block of Ctrl+V is at the end of the optimal edit sequence. Since we don't know the optimal size of the block, we have to do a linear scan which amounts to an algorithm of \(O(n^2)\)

## Code

static String[] OPERATIONS = {"A", "Ctrl+A", "Ctrl+C", "Ctrl+V"}; int longestText(int n) { assert n > 0; int[] length = new int[n + 1]; length[0] = 0; length[1] = 1; int[] optBlockSizes = new int[n+1]; // optimal size of Ctrl+V block ending at each position optBlockSizes[1] = 0; // no Ctrl+V block, i.e., A for (int i = 2; i < n+1; i++) { // for each length of edit sequence int len = length[i-1] + 1; optBlockSizes[i] = 0; // i.e., A for (int j = 1; j < i-2; j++) { // for each size of Ctrl+V block int newLen = (j+1)*length[i-2-j]; if (newLen > len) { len = newLen; optBlockSizes[i] = j; } } } // print the edit sequence printEditSequence(optBlockSizes); return length[n]; } void printEditSequence(int[] pastBlocks) { // the array is [0,n], with the first element useless int n = pastBlocks.length - 1; String[] editSequence = new String[n+1]; printEditSequence(editSequence, pastBlocks, n); } // last is the largest unprocessed element index void printEditSequence(String[] sequence, int[] blocks, int last) { if (last == 0) {// print sequence[1:n]; for (int i = 1; i < sequence.length-1; i++) { System.out.print(sequence[i]+", "); } System.out.println(sequence[sequence.length-1]); } else { if (blocks[last] == 0) { sequence[last] = "A"; printEditSequence(sequence, blocks, last-1); } else { int blockSize = blocks[last]; for (int i = last; i > last - blockSize; last--) { sequence[i] = "Ctrl+V"; } sequence[last-blockSize-1] = "Ctrl+A"; sequence[last-blockSize] = "Ctrl+C"; printEditSequence(sequence, blocks, last-blockSize-2); } } }

## No comments:

Post a Comment