adplus-dvertising

Palindrome Swaps Codechef Solution

We Are Discuss About CODECHEF SOLUTION

Palindrome Swaps Codechef Solution

Palindrome Swaps Codechef Solution

Answers will be Uploaded Shortly and it will be Notified on Telegram, So JOIN NOW
JoinScishowEngineerTelegram

Problem

Chef has N strings. Each string S_i has length M and consists only of lowercase english letters.

Chef likes palindromes, and would like each S_i to be a palindrome. To achieve this, he can perform the following move:

  • Pick an index¬†i¬†such that¬†1 \leq i \lt N¬†and an index¬†j¬†such that¬†1 \leq j \leq M.
  • Then, swap the¬†j^{th}¬†character of string¬†S_i¬†with the¬†j^{th}¬†character of string¬†S_{i+1}.

Informally, Chef can swap the j^{th} character of any two consecutive strings.

Find the minimum number of moves required to make every string a palindrome. Print -1 if it is not possible to achieve this.

Input Format

  • The first line of input contains a single integer¬†T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two space-separated integers¬†N¬†and¬†M, denoting the number of strings and their length, respectively.
    • The¬†i^{th}¬†of the next¬†N¬†lines contains the string¬†S_i.

Output Format

  • Print a single integer on a new line as the answer to each test case: the¬†minimum¬†number of swaps needed to make every¬†S_i¬†a palindrome, or¬†-1¬†if this is not possible.

Constraints

  • 1 \leq T \leq 5\cdot 10^5
  • 1 \leq N, M \leq 5 \cdot 10^5
  • Each¬†S_i¬†contains only lowercase english letters.
  • The sum of¬†N\times M¬†across all test cases won’t exceed¬†5\cdot 10^5.

Sample 1:

Input

Output

4
3 2
ac
ba
cb
2 3
xkx
ptp
4 4
abaa
baba
baab
aabb
4 4
abaa
baba
baab
aaab
2
0
-1
3

Explanation:

Test case 1: Chef can make all the strings palindromes in two operations:

  • First, swap the second characters of¬†S_1¬†and¬†S_2. Now, the strings are¬†\{\texttt{aa, bc, cb}\}
  • Then, swap the first characters of¬†S_2¬†and¬†S_3. Now, the strings are¬†\{\texttt{aa, bb, cc} \}, which are all palindromes.

Test case 2: Both strings are already palindromes.

Test case¬†3:¬†It can be shown that it’s impossible to make all¬†4¬†strings simultaneously palindromes.

Test case 4: One optimal sequence of operations is as follows:

  • Swap the first characters of¬†S_3¬†and¬†S_4. Now, the strings are¬†\{\texttt{abaa, baba, aaab, baab} \}.
  • Swap the second characters of¬†S_1¬†and¬†S_2. Now, the strings are¬†\{\texttt{aaaa, bbba, aaab, baab} \}.
  • Swap the fourth characters of¬†S_2¬†and¬†S_3. Now, the strings are¬†\{\texttt{aaaa, bbbb, aaaa, baab} \}.

Thus, the final strings are all palindromes. It can be proven that we cannot achieve all palindromes in less than 3 moves.

Answers will be Uploaded Shortly and it will be Notified on Telegram, So JOIN NOW
JoinScishowEngineerTelegram

 

SOLUTION

Here Discuss About Palindrome Swaps Codechef Solution

SOLUTION

Palindrome Swaps Codechef Solution

SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.