[Solution] Touchbar Typing Round D 2022 | Kick Start 2022 Solution

Problem

Glide Typing task in Crowdsource app uses a new Google keyboard to type a word by sliding a finger across keys without lifting the finger, as shown in the animation below.

To make the Glide Typing task more challenging, instead of a normal keyboard, we have a special linear keyboard K$K$ that has all the keys in one row.

Imagine that you want to type a word S$S$ that is N$N$ characters long. The linear keyboard K$K$ has M$M$ keys. It is guaranteed that the keys cover all characters in S$S$. However, some of the keys may be duplicates. In other words, for each character in S$S$, there is one or more keys in K$K$ mapped to the character. Note that, all characters and keys are represented as integers.

You may start with your finger on any key. It takes 1$1$ second to move your finger from a key to an adjacent key. Due to Glide Typing, there is no pressing a key. If the finger is currently at the key i$i$ which has character Ki${\mathbf{K}}_{\mathbf{i}}$, and we want to type the character Kj${\mathbf{K}}_{\mathbf{j}}$ at index j$j$, we will glide the finger from the key i$i$ to the key j$j$, which takes |j−i|$|j-i|$ seconds. If your finger is at key x$x$, you can type character Kx${\mathbf{K}}_{\mathbf{x}}$ any number of times instantly. You need to type string S$S$ character by character. Formally, you need to type Si${\mathbf{S}}_{\mathbf{i}}$ before Si+1${\mathbf{S}}_{\mathbf{i}\mathbf{+}\mathbf{1}}$ for each 1≤i≤N−1$1\le i\le \mathbf{N}-1$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

For example, suppose the word S$S$ has characters: 1, 2, 2, 3, 4. You can start by keeping your finger on key with character 1 on the keyboard which is at index i$i$. Then you glide your finger to key which has character 2 which is at index j$j$. It would take |j−i|$|j-i|$ seconds. In order to type character 2 two times in string S$S$, you can do that in no additional time as |j−j|=0$|j-j|=0$ seconds. Then you can continue to glide your finger to type the other characters in the word S$S$ sequentially.

Can you calculate the minimal time needed to type the word?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.

Image Labeler Round D 2022 Solution

Maximum Gain Round D 2022 Solution

Touchbar Typing Round D 2022 Solution

Suspects and Witnesses Round D 2022 Solution

The first line of each test case contains one integer N$N$: the length of the word S$S$.
The second line of each test case contains N$N$ integers: each Si${\mathbf{S}}_{\mathbf{i}}$ is the character at the i$i$-th index.
The third line of each test case contains one integer M$M$: the length of the keyboard K$K$.
The fourth line of each test case contains M$M$ integers: each Ki${\mathbf{K}}_{\mathbf{i}}$ is the character at the i$i$-th key.

Output

For each test case, output one line containing the minimal time needed to type the word. Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the minimal time needed to type S$S$ on the keyboard K$K$.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
All characters in S$S$ appears at least once in K$K$.
1≤Ki≤2500$1\le {\mathbf{K}}_{\mathbf{i}}\le 2500$.
1≤Si≤2500$1\le {\mathbf{S}}_{\mathbf{i}}\le 2500$.

Test Set 1

Time limit: 20 seconds.
1≤N≤100$1\le \mathbf{N}\le 100$.
1≤M≤100$1\le \mathbf{M}\le 100$.
It is guaranteed that there are no duplicated keys in keyboard K$K$.

Test Set 2

Time limit: 20 seconds.
1≤N≤100$1\le \mathbf{N}\le 100$.
1≤M≤100$1\le \mathbf{M}\le 100$.

Test Set 3

Time limit: 40 seconds.
1≤N≤2500$1\le \mathbf{N}\le 2500$.
1≤M≤2500$1\le \mathbf{M}\le 2500$.