Math Test (Codeforces 1622E)
Tags: Greedy, bitmasks

Petya is a math teacher. $$$n$$$ of his students has written a test consisting of $$$m$$$ questions. For each student, it is known which questions he has answered correctly and which he has not.If the student answers the $$$j$$$-th question correctly, he gets $$$p_j$$$ points (otherwise, he gets $$$0$$$ points). Moreover, the points for the questions are distributed in such a way that the array $$$p$$$ is a permutation of numbers from $$$1$$$ to $$$m$$$.For the $$$i$$$-th student, Petya knows that he expects to get $$$x_i$$$ points for the test. Petya wonders how unexpected the results could be. Petya believes that the surprise value of the results for students is equal to $$$\sum\limits_{i=1}^{n} |x_i - r_i|$$$, where $$$r_i$$$ is the number of points that the $$$i$$$-th student has got for the test.Your task is to help Petya find such a permutation $$$p$$$ for which the surprise value of the results is maximum possible. If there are multiple answers, print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10$$$; $$$1 \le m \le 10^4$$$) — the number of students and the number of questions, respectively.The second line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le \frac{m(m+1)}{2}$$$), where $$$x_i$$$ is the number of points that the $$$i$$$-th student expects to get.This is followed by $$$n$$$ lines, the $$$i$$$-th line contains the string $$$s_i$$$ ($$$|s_i| = m; s_{i, j} \in \{0, 1\}$$$), where $$$s_{i, j}$$$ is $$$1$$$ if the $$$i$$$-th student has answered the $$$j$$$-th question correctly, and $$$0$$$ otherwise.The sum of $$$m$$$ for all test cases does not exceed $$$10^4$$$.

Output: For each test case, print $$$m$$$ integers — a permutation $$$p$$$ for which the surprise value of the results is maximum possible. If there are multiple answers, print any of them.


Sample Inputs:
3
4 3
5 1 2 2
110
100
101
100
4 4
6 2 0 10
1001
0010
0110
0101
3 6
20 3 15
010110
000101
111111

Sample Outputs:
3 1 2 
2 3 4 1 
3 1 4 5 2 6

Solution (Python):
import sys
import time
import random
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
    (n, m) = I()
    expect = I()
    mat = []
    for i in range(n):
        mat.append([*map(int, [*sys.stdin.readline().strip()])])
    onebits = []
    for i in range(1 << n):
        onebits.append(bin(i).count('1'))
    qrep = [0] * m
    for i in range(n):
        for j in range(m):
            if mat[i][j]:
                qrep[j] += 1 << i
    big = -1
    perm = None
    for i in range(1 << n):
        count = [0] * (n + 1)
        vals = [0] * m
        for j in range(m):
            x = onebits[i ^ qrep[j]]
            vals[j] = x
            count[x] += 1
        ind = [0] * (n + 1)
        for j in range(n):
            ind[j + 1] = ind[j] + count[j]
        qvals = [0] * m
        for j in range(m):
            ind[vals[j]] += 1
            qvals[j] = ind[vals[j]]
        tot = 0
        for j in range(n):
            if i >> j & 1:
                tot += expect[j]
            else:
                tot -= expect[j]
        for j in range(m):
            right = onebits[qrep[j]]
            x = onebits[i & qrep[j]]
            tot += (right - 2 * x) * qvals[j]
        if tot > big:
            big = tot
            perm = qvals
    print(*perm)

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
getdigit = [[] for _ in range(1024)]
for i in range(1024):
    curr = i
    d = 0
    while curr:
        if curr & 1:
            getdigit[i].append(d)
        d += 1
        curr = curr >> 1

def main(t):
    (n, m) = map(int, input().split())
    estimate = list(map(int, input().split()))
    score = [0] * m
    maxdiff = -1
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == ord('1'):
                score[j] += 1 << i
    zerom = [0] * m
    for b in range(1 << n):
        currnum = zerom[:]
        count = [0] * (n + 1)
        currnum = [len(getdigit[b ^ score[i]]) for i in range(m)]
        for i in range(m):
            count[currnum[i]] += 1
        accucount = [0] * (n + 1)
        actscore = [0] * n
        for j in range(n):
            accucount[j + 1] = accucount[j] + count[j]
        tempans = zerom[:]
        for i in range(m):
            tempans[i] = accucount[currnum[i]] + 1
            accucount[currnum[i]] += 1
            for index in getdigit[score[i]]:
                actscore[index] += tempans[i]
        diff = sum([abs(actscore[j] - estimate[j]) for j in range(n)])
        if diff > maxdiff:
            maxdiff = diff
            ans = tempans[:]
    print(*ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
getdigit = [[] for _ in range(1024)]
for i in range(1024):
    curr = i
    d = 0
    while curr:
        if curr & 1:
            getdigit[i].append(d)
        d += 1
        curr = curr >> 1

def main(t):
    (n, m) = map(int, input().split())
    estimate = list(map(int, input().split()))
    score = [0] * m
    maxdiff = -1
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == ord('1'):
                score[j] += 1 << i
    zerom = [0] * m
    for b in range(1 << n):
        currnum = zerom[:]
        count = [0] * (n + 1)
        currnum = [len(getdigit[b ^ score[i]]) for i in range(m)]
        for i in range(m):
            count[currnum[i]] += 1
        accucount = [0] * (n + 1)
        actscore = [0] * n
        for j in range(n):
            accucount[j + 1] = accucount[j] + count[j]
        tempans = zerom[:]
        for i in range(m):
            tempans[i] = accucount[currnum[i]] + 1
            accucount[currnum[i]] += 1
            for index in getdigit[score[i]]:
                actscore[index] += tempans[i]
        diff = sum([abs(actscore[j] - estimate[j]) for j in range(n)])
        if diff > maxdiff:
            maxdiff = diff
            ans = tempans[:]
    print(*ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1