perfect-baseline

A particular name-recording system is used by N employees of a firm. Everyday, they have to enter their names into the system.

To make it easier to control the system, each employee has his/her name presented as a string of lowercase letters from 'a' to 'z' with the same length K. Therefore, the system is designed to have K slots. Each slot has one lowercase letter from 'a' - 'z', initially. It takes one second to rotate it either upwards or downwards. Note that the arrangement is not circular, and hence, 'z' cannot be changed into 'a' in one second.  

Given the list of all employee names that need to be entered every morning, can you find the least lexicographically default starting string S to be presented in the system so that the total amount of time spent by all employees is minimized?

Note that after an employee has finished entering his/her name, the system resets to S.

Input:
The first line contains a single integer T, denoting the number of test cases. Each of the T test cases has this format:
 - The first line contains two space-separated integers N and K.
 - Each of the next N lines contains a string of length K representing the name of the respective employee in lowercase.

Output:
Output exactly T strings, each contains the answer to the corresponding test case.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10000
1 ≤ K ≤ 20

SAMPLE INPUT
2
3 3
aaa
ccc
ddd
5 1
a
a
b
b
a

SAMPLE OUTPUT
ccc
a

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Implementation

Ad-hoc


Solutions:
for _ in range(eval(input())):
	n, _ = (int(x) for x in input().split())
	best = ''.join(min(sorted(c)[n >> 1], sorted(c)[n - 1 >> 1]) 
				   for c in zip(*(input() for _ in range(n))))
	print(best)


import sys
import math

T = int(sys.stdin.readline())
for case in range(T):
	[N,K] = [int(x) for x in sys.stdin.readline().split()]
	array = [[0 for x in range(26)] for y in range(K)]
	for na in range(N):
		name = list(sys.stdin.readline().strip())
		for x in range(len(name)):
			array[x][ord(name[x]) - ord('a')] += 1
	min_str = ""
	for x in array:
		minim = -1
		m_char = -1
		for y in range(26):
			tcalc = 0
			for z in range(26): 
				tcalc += math.fabs(z - y) * x[z]
			if minim == -1 or tcalc < minim:
				minim = tcalc
				m_char = y
		min_str += chr(m_char + ord('a')) 
	print(min_str)


for _ in range(eval(input())):
	n, l = list(map(int, input().split()))
	names = []
	for i in range(n):
		names.append(input())
	ans = []
	for j in range(l):
		a = sorted([names[i][j] for i in range(n)])
		ans.append(min(a[n >> 1], a[n - 1 >> 1]));
	print((''.join(ans)))



for i in range(int(input())):
	sol=""
	names=[]
	n,l=[int(i) for i in input().split(" ")]
	for j in range(n):
		names.append(input())
	for k in range(l):
		sarr=sorted([names[m][k] for m in range(n)])
		sol+=(min(sarr[n>>1],sarr[n-1>>1]))
	print(sol)