Page Contents
Weird Palindrome Making MAKEPAL Solution
Naveej is from a tribe that speaks some weird language – their alphabet consists of NN distinct characters. He has an array A=[A1,A2,…,AN]A=[A1,A2,…,AN], where AiAi denotes the number of occurrences of the ii-th character with him.
He wants to make a palindromic string using all the characters he has (every character he has must be used in this string).
In order to make this possible, he can perform the following operation:
- Select an ii (1≤i≤N)(1≤i≤N) and convert all occurrences of ii-th alphabet to any other alphabet of his choice.
Note that Naveej just wants to be able to make any palindrome, as long as every character is used. For example, if N=2N=2 and A=[2,2]A=[2,2] and we consider the characters to be aa and bb, he can make both abbaabba and baabbaab, but abaaba is not allowed because it uses only 33 characters.
Find the minimum number of operations required such that Naveej can make a palindromic string using all the characters he has. It can be proven that there always exists at least one sequence of operations allowing for the formation of a palindrome.
Input Format
- The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single integer NN – the size of the alphabet.
- The second line contains NN space-separated integers: A1,A2,…,ANA1,A2,…,AN, where AiAi is the number of occurrences of the ii-th character with Naveej.
Output Format
For each test case, output a single line containing one integer – the minimum number of operations required so that Naveej can make a palindromic string using all the characters he has.
Constraints
- 1≤T≤10001≤T≤1000
- 1≤N≤2⋅1051≤N≤2⋅105
- 1≤Ai≤1091≤Ai≤109
- It is guaranteed that the sum of NN over all test cases does not exceed 2⋅1052⋅105
Subtasks
- Subtask 1 (100 points): Original constraints
Sample Input 1
2 1 4 3 4 3 1
Sample Output 1
0 1
Explanation
- In the first test case, N=1N=1. Let the character be aa. We can make the following palindromic string: aaaaaaaa.
- In the second test case, N=3N=3. Let the characters be aa, bb, cc. It is initially not possible to make a palindrome with the given occurrences of the characters. We perform 1 operation: Convert all the occurrences of bb to cc. Then, we can make the following palindromic string: acaccacaacaccaca.
Weird Palindrome Making MAKEPAL Solution is updated. Click Below
SOLUTION
Program Python: Weird Palindrome Making MAKEPAL Solution in Python
Code Credit: tashi (in comment section)
# cook your dish here T = int(input()) for i in range(0,T): N = int(input()) A = [int(x) for x in input().split()] if N==1: print(0) else: v =[] for i in A: if i in range(1,1000000000,2): v.append(i) if len(v)==1: print(0) elif len(v)%2== 0: print(int(len(v)/2)) else: print(int((len(v)-1)/2))
Program C++: Weird Palindrome Making MAKEPAL Solution in C++
#include <iostream> using namespace std; int main() { // your code goes here int t,n,i,x; scanf("%d",&t); while(t--) { int c=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&x); if (x%2==1) { c++; } } if (c%2==1) { c--; } printf("%d\n",c/2); } return 0; }
Program Java: Weird Palindrome Making MAKEPAL Solution in Java
/* package codechef; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { public static void main (String[] args) throws java.lang.Exception { // your code goes here Scanner sc= new Scanner(System.in); int t=sc.nextInt(); int i; while(t-- >0) { int c=0; int n=sc.nextInt(); for(i=0;i<n;i++) { int x=sc.nextInt(); if (x%2==1) { c++; } } if (c%2==1) { c--; } System.out.println(c/2); } } }
November Long Challenge 2021 Solution
- Which Fuel is Cheaper CHEAPFUEL Solution
- Convex Hulk CONHULK Solution
- Functional Array FUNARR Solution
- Flip or Compress FLIPCOMP Solution
- Maximise the bridges MAXBRIDGE Solution
- Wildcard Replacement WLDRPL Solution
- Xor Equation XOREQN Solution
- Hill Sequence HILLSEQ Solution
- Weird Palindrome Making MAKEPAL Solution
- Equal Coins EQUALCOIN Solution Codechef
Codechef Long Challenges Solution
October Long Challenge 2021 Solution
- Longest AND Subarray
- MEX-OR
- Digit Removal
- Yet another MEX problem
- Characteristic Polynomial Verification
- Chef at the Olympics
- Which Mixture
- Three Boxes
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
T = int(input(“T”))
for i in range(0,T):
N = int(input(“N”))
A = [int(x) for x in input(“A”).split()]
if N==1:
print(0)
else:
v =[]
for i in A:
if i in range(1,1000000000,2):
v.append(i)
if len(v)==1:
print(0)
elif len(v)%2== 0:
print(int(len(v)/2))
else:
print(int((len(v)-1)/2))
We appreciate your solution submission we have added your solution on the post with credit, if possible please leave your codechef profile link to tag you.