[Solution] Another String Minimization Problem solution codeforces

Another String Minimization Problem solution codeforces – You have a sequence 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an of length 𝑛n, consisting of integers between 11 and 𝑚m. You also have a string 𝑠s, consisting of 𝑚m characters B.

Table of Contents

[Solution] Another String Minimization Problem solution codeforces

You are going to perform the following 𝑛n operations.

  • At the 𝑖i-th (1𝑖𝑛1≤i≤n) operation, you replace either the 𝑎𝑖ai-th or the (𝑚+1𝑎𝑖)(m+1−ai)-th character of 𝑠s with A. You can replace the character at any position multiple times through the operations.

Find the lexicographically smallest string you can get after these operations.

A string 𝑥x is lexicographically smaller than a string 𝑦y of the same length if and only if in the first position where 𝑥x and 𝑦y differ, the string 𝑥x has a letter that appears earlier in the alphabet than the corresponding letter in 𝑦y.

Input

The first line contains the number of test cases 𝑡t (1𝑡20001≤t≤2000).

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛,𝑚501≤n,m≤50) — the length of the sequence 𝑎a and the length of the string 𝑠s respectively.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑚1≤ai≤m) — the sequence 𝑎a.

[Solution] Another String Minimization Problem solution codeforces

For each test case, print a string of length 𝑚m — the lexicographically smallest string you can get. Each character of the string should be either capital English letter A or capital English letter B.

Example
input

Copy
6
4 5
1 1 3 1
1 5
2
4 1
1 1 1 1
2 4
1 3
2 7
7 5
4 5
5 5 3 5
output

Copy
ABABA
BABBB
A
AABB
ABABBBB
ABABA

[Solution] Another String Minimization Problem solution codeforces

In the first test case, the sequence 𝑎=[1,1,3,1]a=[1,1,3,1]. One of the possible solutions is the following.

  • At the 11-st operation, you can replace the 11-st character of 𝑠s with A. After it, 𝑠s becomes ABBBB.
  • At the 22-nd operation, you can replace the 55-th character of 𝑠s with A (since 𝑚+1𝑎2=5m+1−a2=5). After it, 𝑠s becomes ABBBA.
  • At the 33-rd operation, you can replace the 33-rd character of 𝑠s with A. After it, 𝑠s becomes ABABA.
  • At the 44-th operation, you can replace the 11-st character of 𝑠s with A. After it, 𝑠s remains equal to ABABA.

The resulting string is ABABA. It is impossible to produce a lexicographically smaller string.In the second test case, you are going to perform only one operation. You can replace either the 22-nd character or 44-th character of 𝑠s with A. You can get strings BABBB and BBBAB after the operation. The string BABBB is the lexicographically smallest among these strings.

In the third test case, the only string you can get is A.

In the fourth test case, you can replace the 11-st and 22-nd characters of 𝑠s with A to get AABB.

In the fifth test case, you can replace the 11-st and 33-rd characters of 𝑠s with A to get ABABBBB.

For Solution

Click Here

Leave a Comment