HackerEarth Perfect Baseline problem solution

In this HackerEarth Perfect Baseline problem solution, A particular name-recording system is used by N employees of a firm. Every day, 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.

HackerEarth Perfect Baseline problem solution

HackerEarth Perfect Baseline problem solution.

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

Second solution

#include <bits/stdc++.h>
using namespace std;

#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = (n) - 1; i >= 0; i--)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))

#define uint64 unsigned long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define PI 3.1415926535897932385
#define EPS 1e-7
#define MOD 1000000007
#define INF 1500111222
#define MAX 100111

int n, k;
string s[MAX];

char chooseBestChar(int j) {
int minCost = INF, res = 'a';
fr(c, 'a', 'z') {
int cost = 0;
rep(i, n) cost += abs(c - s[i][j]);
if (cost < minCost) {
minCost = cost;
res = c;
return res;

int main() {
int cases;
scanf("%d", &cases);
assert(1 <= cases && cases <= 10);
while (cases--) {
scanf("%d %d", &n, &k);
assert(1 <= n && n <= 10000);
assert(1 <= k && k <= 20);
rep(i, n) {
cin >> s[i];
assert(s[i].length() == k);
rep(j, k) assert('a' <= s[i][j] && s[i][j] <= 'z');
string res = "";
rep(j, k) res += chooseBestChar(j);
cout << res << endl;
return 0;;

Post a Comment