#C10304. Taco Array Transformation
Taco Array Transformation
Taco Array Transformation
Problem Statement:
Given two arrays \(a\) and \(b\) of length \(n\), perform the following transformation on array \(a\) based on the values of array \(b\):
- For each element \(b_i\) in array \(b\) (processed in order), locate its right-most occurrence in the current array \(a\). Formally, if \(a = [a_0, a_1, \dots, a_{n-1}]\) then find an index \(j\) (with \(0 \le j < n\)) such that \(a_j = b_i\) and \(j\) is maximum among the available indices that have not been removed.
- If such an occurrence is found, remove the element at that index from \(a\) (so that it is no longer available in subsequent steps) and append it to the result sequence.
- If \(b_i\) does not exist in the current array \(a\), then the transformation for that test case is deemed impossible. In this case, output
NO
.
If the transformation is possible for all elements of \(b\), output the resulting sequence as a space-separated list of numbers. Otherwise, output NO
.
Note: When describing any formula, use LaTeX formatting (e.g. \(\LaTeX\)).
inputFormat
Input:
- The first line contains an integer \(t\) representing the number of test cases.
- For each test case:
- A line containing an integer \(n\), the number of elements in arrays \(a\) and \(b\).
- A line containing \(n\) space-separated integers representing array \(a\).
- A line containing \(n\) space-separated integers representing array \(b\).
outputFormat
Output:
For each test case, output a single line:
- If the transformation is possible, output the transformed sequence as a space-separated list of numbers.
- If the transformation is not possible, output
NO
.
3
5
4 3 2 5 1
2 3 1 5 4
3
1 4 2
3 4 2
4
6 5 7 8
8 6 5 7
2 3 1 5 4
NO
8 6 5 7
</p>