[Solution] Touchbar Typing solution kickstart

Touchbar Typing solution kickstart – 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.

Demostration of Glide Typing on a mobile device.

Table of Contents

[Solution] Touchbar Typing solution kickstart

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

Imagine that you want to type a word SS that is NN characters long. The linear keyboard KK has MM keys. It is guaranteed that the keys cover all characters in SS. However, some of the keys may be duplicates. In other words, for each character in SS, there is one or more keys in KK 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 11 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 ii which has character KiKi, and we want to type the character KjKj at index jj, we will glide the finger from the key ii to the key jj, which takes |ji||j−i| seconds. If your finger is at key xx, you can type character KxKx any number of times instantly. You need to type string SS character by character. Formally, you need to type SiSi before Si+1Si+1 for each 1iN11≤i≤N−1.

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

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

[Solution] Touchbar Typing solution kickstart

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

The first line of each test case contains one integer NN: the length of the word SS.
The second line of each test case contains NN integers: each SiSi is the character at the ii-th index.
The third line of each test case contains one integer MM: the length of the keyboard KK.
The fourth line of each test case contains MM integers: each KiKi is the character at the ii-th key.

Output

For each test case, output one line containing the minimal time needed to type the word. Case #xxyy, where xx is the test case number (starting from 1) and yy is the minimal time needed to type SS on the keyboard KK.

Limits

Memory limit: 1 GB.
1T1001≤T≤100.
All characters in SS appears at least once in KK.
1Ki25001≤Ki≤2500.
1Si25001≤Si≤2500.

Test Set 1

Time limit: 20 seconds.
1N1001≤N≤100.
1M1001≤M≤100.
It is guaranteed that there are no duplicated keys in keyboard KK.

Test Set 2

Time limit: 20 seconds.
1N1001≤N≤100.
1M1001≤M≤100.

Test Set 3

Time limit: 40 seconds.
1N25001≤N≤2500.
1M25001≤M≤2500.

[Solution] Touchbar Typing solution kickstart

Note: there are additional samples that are not run on submissions down below.

Sample Input
content_copy
2
5
1 2 3 2 1
3
1 2 3
3
1 1 1
2
2 1
Sample Output
content_copy
Case #1: 4
Case #2: 0

[Solution] Touchbar Typing solution kickstart

In Sample Case #1, we can take the following steps to type string SS in minimum time.

  • Start by keeping your finger on key K1K1 which has character 1. We have now typed the first character of the string SS.
  • In order to type the second character 2 of the string SS, glide your finger to key K2K2. it takes |21|=1|2−1|=1 additional second to glide the finger from index 11 to index 22.
  • In order to type the third character 3 of the string SS, glide your finger to key K3K3. it takes |32|=1|3−2|=1 additional second to glide the finger from index 22 to index 33.
  • In order to type the fourth character 2 of the string SS, glide your finger to key K2K2. it takes |23|=1|2−3|=1 additional second to glide the finger from index 33 to index 22.
  • In order to type the fifth character 1 of the string SS, glide your finger to key K1K1. it takes |12|=1|1−2|=1 additional second to glide the finger from index 22 to index 11.
  • We have typed all characters of the string SS in a total of 44 seconds.

 

In Sample Case #2, we can take the following steps to type string SS in minimum time.

  • Start by keeping your finger on key K2K2 which has character 1. We have now typed the first character of the string SS.
  • As our finger is on key K2K2, we can type the character 1 any number of times, without any additional time. Hence, we can type the second and third characters of the string SS.
  • We have typed all characters of the string SS in a total of 00 seconds.

 

 

Additional Sample – Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
content_copy
2
4
2 1 4 1
8
4 1 5 2 1 3 5 4
3
1 2 3
8
2 3 5 1 4 6 7 2
Sample Output
content_copy
Case #1: 4
Case #2: 4

[Solution] Touchbar Typing solution kickstart

In Additional Sample Case #1, we can take the following steps to type string SS in minimum time.

  • Start by keeping your finger on key K4K4 which has character 2. We have now typed the first character of the string SS.
  • In order to type the second character 1 of the string SS, glide your finger to key K2K2. it takes |24|=2|2−4|=2 additional seconds to glide the finger from index 44 to index 22.
  • In order to type the third character 4 of the string SS, glide your finger to key K1K1. it takes |12|=1|1−2|=1 additional second to glide the finger from index 22 to index 11.
  • In order to type the fourth character 1 of the string SS, glide your finger to key K2K2. it takes |21|=1|2−1|=1 additional second to glide the finger from index 11 to index 22.
  • We have typed all characters of the string SS in a total of 44 seconds.

 

In Additional Sample Case #2, we can take the following steps to type string SS in minimum time.

  • Start by keeping your finger on key K4K4 which has character 1. We have now typed the first character of the string SS.
  • In order to type the second character 2 of the string SS, glide your finger to key K1K1. it takes |14|=3|1−4|=3 additional seconds to glide the finger from index 44 to index 11.
  • In order to type the third character 3 of the string SS, glide your finger to key K2K2. it takes |21|=1|2−1|=1 additional second to glide the finger from index 11 to index 22.
  • We have typed all characters of the string SS in a total of 44 seconds.

For Solution

Click Here

Leave a Comment