Problem:


Score : 700 points

Problem Statement

There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter.
Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.

Snuke can apply the following operation to this grid any number of times:

Choose two different rows and swap them. Or, choose two different columns and swap them.

Snuke wants this grid to be symmetric.
That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.

Determine if Snuke can achieve this objective.

Constraints

1 \leq H \leq 12

1 \leq W \leq 12

|S_i| = W

S_i consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

If Snuke can make the grid symmetric, print YES; if he cannot, print NO.

Sample Input 1

2 3
arc
rac

Sample Output 1

YES

If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:

Sample Input 2

3 7
atcoder
regular
contest

Sample Output 2

NO

Sample Input 3

12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv

Sample Output 3

YES



Sample input:
2 3
arc
rac


Sample output:
YES

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def can_palindrome(s):
    l = []
    for c in s:
        if c in l:
            l.remove(c)
        else:
            l.append(c)

    if len(s) % 2 == 0:
        return len(l) == 0
    else:
        return len(l) == 1


def can_pair(s1, s2):
    l = []
    for c1, c2 in zip(s1, s2):
        c = sorted([c1, c2])
        if c in l:
            l.remove(c)
        else:
            l.append(c)

    if len(s1) % 2 == 0:
        return len(l) == 0
    else:
        return len(l) == 1


def pair_graph(s1, s2):
    N = len(s1)
    G = np.zeros([N, N])
    for i in range(N):
        for j in range(i+1, N):
            if s1[i] == s2[j] and s1[j] == s2[i]:
                G[i, j] = 1
                G[j, i] = 1
    return G

import numpy as np
H, W = list(map(int, input().split(' ')))
S = []
d = defaultdict(list)

for h in range(H):
    s = input()
    S.append(s)
    d[''.join(sorted(S))].append(h)

already_paired = np.zeros(H)

Gs = []

for i in range(H):
    if already_paired[i]:
        continue

    for j in range(i+1, H):
        if already_paired[j]:
            continue

        if can_pair(S[i], S[j]):
            already_paired[i] = 1
            already_paired[j] = 1
            G = pair_graph(S[i], S[j])
            Gs.append(G)
        break

if already_paired.sum() < H - 1:
    print('NO')
    exit()

elif already_paired.sum() == H - 1:
    for i in range(H):
        if already_paired[i] == 0:
            Gs.append(pair_graph(S[i], S[i]))
            break

G = np.array(Gs).sum(axis=0) // len(Gs)


def is_perfect_matching(G):
    N = len(G)
    if N == 1:
        return True
    for i in range(N):
        for j in range(i+1, N):
            if G[i, j] == 1:
                l = list(range(N))
                l.remove(i)
                l.remove(j)
                if len(l) == 0:
                    return True
                if is_perfect_matching(G[l][:, l]):
                    return True
    return False

if is_perfect_matching(G):
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    h, w = f.read_int_list()
    s = [list(f.read_str()) for i in xrange(h)]
    s2 = [[s[hi][wi] for hi in xrange(h)] for wi in xrange(w)]

    sh = ["".join(sorted(si)) for si in s]
    sw = ["".join(sorted([s[hi][wi] for hi in xrange(h)])) for wi in xrange(w)]
    odd_h = []
    dh = collections.Counter(sh)
    for k, v in dh.items():
        if v % 2 == 1: odd_h.append(sh.index(k))

    odd_w = []
    dw = collections.Counter(sw)
    for k, v in dw.items():
        if v % 2 == 1: odd_w.append(sw.index(k))


    if len(odd_h) != h % 2 or len(odd_w) != w % 2: return "NO"

    def checkh(oh):
        d = collections.defaultdict(list)
        res = None
        for i, si in enumerate(s[oh]):
            d[si].append(i)
        for k, v in d.items():
            if len(v) % 2 == 0:
                dd = collections.Counter(["".join(sorted(s2[vi])) for vi in v])
                od = 0
                for vv in dd.values():
                    if vv % 2 == 1: od += 1
                if od > 1: return False
            else:
                res = k
        return res

    def checkw(ow):
        d = collections.defaultdict(list)
        res = None
        for i, si in enumerate(s2[ow]):
            d[si].append(i)
        for k, v in d.items():
            if len(v) % 2 == 0:
                dd = collections.Counter(["".join(sorted(s[vi])) for vi in v])
                print dd
                od = 0
                for vv in dd.values():
                    if vv % 2 == 1: od += 1
                if od > 1: return False
            else:
                res = k
        return res

    resh = resw = None
    if len(odd_h) == 1:
        resh = checkh(odd_h[0])
        if resh == False: return "NO"
    if len(odd_w) == 1:
        resw = checkw(odd_w[0])
        if resw == False: return "NO"
    if resh is not None and resw is not None and resh != resw: return "NO"

    return "YES"


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
T = [[None]*H for i in range(W)]
D = {}
for i in range(H):
    for j in range(W):
        c = S[i][j]
        D[c] = D.get(c, 0) ^ 1
if sum(D.values()) != (1 if (H%2==1)and(W%2==1) else 0):
    print("NO")
    exit(0)
for i in range(H):
    s = S[i]
    for j in range(W):
        T[j][i] = s[j]
def check(S, H, W):
    res = []
    ok1 = 1
    for p in range(H):
        sp = S[p]
        for q in range(p+1, H):
            sq = S[q]
            d = {}
            for k in range(W):
                if sp[k] < sq[k]:
                    k = sp[k], sq[k]
                    d[k] = d.get(k, 0) + 1
                elif sp[k] == sq[k]:
                    k = sp[k], sp[k]
                    d[k] = d.get(k, 0) ^ 1
                else:
                    k = sq[k], sp[k]
                    d[k] = d.get(k, 0) - 1
            cap = (W % 2)
            ok = 1
            for a, b in d:
                if a == b:
                    if d[a, b]:
                        if cap == 0:
                            ok = ok1 = 0
                        cap -= 1
                else:
                    if d[a, b] != 0:
                        ok = ok1 = 0
            if ok: res.append((p, q))
    if H % 2 == 1:
        for p in range(H):
            d = {}
            for s in S[p]:
                d[s] = d.get(s, 0) ^ 1
            if sum(d.values()) == W % 2:
                res.append((p, p))
    return [] if ok1 else res
sc = check(S, H, W)
tc = check(T, W, H)
def solve(N, P):
    def dfs(state, c):
        if N == c:
            return 1
        for p, q in P:
            v = (1 << p) | (1 << q)
            if state & v:
                continue
            if dfs(state | v, (c+2 if p != q else c+1)):
                return 1
        return 0
    return dfs(0, 0)
if solve(H, sc) and solve(W, tc):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
TH=[sorted(S[i]) for i in range(H)]
PH=[-1 for i in range(H)]
TW=[sorted([S[i][j] for i in range(H)]) for j in range(W)]
PW=[-1 for j in range(W)]
#0<=i<H,0<=j<W
for i in range(H):
    if PH[i]!=-1:
        continue
    else:
        for k in range(H):
            if k==i:continue
            if TH[k]==TH[i]:
                PH[i]=k
                PH[k]=i
                break
for j in range(W):
    if PW[j]!=-1:
        continue
    else:
        for k in range(W):
            if k==j:continue
            if TW[k]==TW[j]:
                PW[j]=k
                PW[k]=j
                break
if H%2==0:
    for i in range(H):
        if PH[i]==-1:
            print("NO")
            exit()
else:
    if PH.count(-1)>=2:
        print("NO")
        exit()
if W%2==0:
    for i in range(W):
        if PW[i]==-1:
            print("NO")
            exit()
else:
    if PW.count(-1)>=2:
        print("NO")
        exit()
#usedcheck
QH=[0 for i in range(H)]
QW=[0 for j in range(W)]
RH=[]
RW=[]
SH=[-1 for i in range(H)]
SW=[-1 for j in range(W)]
for i in range(H):
    if QH[i]==0:
        if PH[i]==-1:
            SH[H//2]=i
            continue
        RH.append((i,PH[i]))
        QH[i]=1
        QH[PH[i]]=1
for j in range(W):
    if QW[j]==0:
        if PW[j]==-1:
            SW[W//2]=j
            continue
        RW.append((j,PW[j]))
        QW[j]=1
        QW[PW[j]]=1
for i in range(H//2):
    SH[i]=RH[i][0]
    SH[H-1-i]=RH[i][1]
for j in range(W//2):
    SW[j]=RW[j][0]
    SW[W-1-j]=RW[j][1]
U=[[S[SH[i]][SW[j]] for j in range(W)] for i in range(H)]
flag=0
for i in range(H):
    for j in range(W):
        if U[i][j]!=U[H-1-i][W-1-j]:
            flag=1
if flag==1:
    print("NO")
else:
    print("YES")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = ''
for i in range(H):
    S += input()
if H % 2 == 1 and W % 2 == 1:
    odd_cnt = 0
    for i in 'abcdefghijklmnopqrstuvwxyz':
        if S.count(i) % 2 == 1 and odd_cnt == 0:
            odd_cnt += 1
        elif S.count(i) % 2 == 1 and odd_cnt == 1:
            odd_cnt += 1
            print('NO')
            break
    if odd_cnt == 1:
        print('YES')
    elif odd_cnt == 0:
        print('NO')
else:
    odd = False
    for i in 'abcdefghijklmnopqrstuvwxyz':
        if S.count(i) % 2 == 1:
            print('NO')
            odd = not(odd)
            break
    if not(odd):
        print('YES')

Submission status: Wrong Answer

Solution code:
import random
from collections import Counter

H,W = map(int,input().split())
src = [input() for i in range(H)]

def tostr(ctr):
    ret = ''
    for k,v in sorted(ctr.items()):
        ret += k + str(v)
    return ret

hctrs = [tostr(Counter(row)) for row in src]
vctrs = [tostr(Counter(col)) for col in zip(*src)]
hc2 = Counter(hctrs)
vc2 = Counter(vctrs)

allow_odd = H%2
a = 0
for k,v in hc2.items():
    if v%2:
        if allow_odd:
            allow_odd = False
            a += 1
        else:
            print('NO')
            exit()

allow_odd = W%2
for k,v in vc2.items():
    if v%2:
        if allow_odd:
            allow_odd = False
            a += 1
        else:
            print('NO')
            exit()


if H%2 and W%2 and a == 2:
    if random.randrange(2):
        print('NO')
        exit()

print('YES')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
H, W = map(int, input().split())
s = [input() for _ in range(H)]
if H == 1 and W == 1:
    print('NO')
else:

    d_h = [[0 for i in range(28)] for _ in range(H)]
    d_w = [[0 for i in range(28)] for _ in range(W)]

    for i in range(H):
        for c in s[i]:
            d_h[i][ord(c) - ord("a")] += 1

    for i in range(H):
        for j in range(W):
            d_w[j][ord(s[i][j]) - ord("a")] += 1
    #
    # for i in range(H):
    #     d_h[i].sort()
    #     d_w[i].sort()

    check_h = []
    check_w = []

    for i in range(H):
        if i in check_h:
            continue
        for j in range(i + 1, H):
            if j in check_h:
                continue
            else:
                if d_h[i] == d_h[j]:
                    check_h.append(i)
                    check_h.append(j)
                    break

    for i in range(W):
        if i in check_w:
            continue
        for j in range(i + 1, W):
            if j in check_w:
                continue
            else:
                if d_w[i] == d_w[j]:
                    check_w.append(i)
                    check_w.append(j)
                    break

    c_w = 0
    c_h = 0

    for i in range(H):
        if i in check_h:
            c_h += 1
    for i in range(W):
        if i in check_w:
            c_w += 1

    if c_h >= H - 1 and c_w >= W - 1:

        print('YES')
    else:
        print('NO')

Submission status: Wrong Answer

Solution code:
# E
import numpy as np

H, W = map(int, input().split())
S = list()
for _ in range(H):
    S.append(list(input()))
S_arr = np.array(S)

res = "YES"

def check_ok(S_arr, H, W):
    res = True
    for i in range(H):
        for j in range(W):
            if S_arr[i, j] != S_arr[H-1-i, W-1-j]:
                res = False
    return res


def apply_switch(S_arr, row_matching, col_matching):
    S_arr_row = S_arr.copy()
    i = 0
    for mat in row_matching:
        if len(mat) == 2:
            S_arr_row[i, :] = S_arr[mat[0], :]
            S_arr_row[H-1-i, :] = S_arr[mat[1], :]
            i += 1
        else:
            S_arr_row[(H-1)//2, :] = S_arr[mat[0], :]
    S_arr_rowcol = S_arr_row.copy()
    j = 0
    for mat in col_matching:
        if len(mat) == 2:
            S_arr_rowcol[:, j] = S_arr_row[:, mat[0]]
            S_arr_rowcol[:, W-1-j] = S_arr_row[:, mat[1]]
            j += 1
        else:
            S_arr_rowcol[:, (W-1)//2] = S_arr_row[:, mat[0]]
    return S_arr_rowcol
    
# row_matching
same_row_list = []
done_row_list = np.zeros(H)
for i in range(H):
    if done_row_list[i] == 1:
        continue
    done_row_list[i] = 1
    j_list = [i]
    for j in range(H):
        if i != j and np.prod(np.sort(S_arr[i, :]) == np.sort(S_arr[j, :])) == 1:
            j_list.append(j)
            done_row_list[j] = 1
    same_row_list.append(j_list)

# col_matching
same_col_list = []
done_col_list = np.zeros(W)
for i in range(W):
    if done_col_list[i] == 1:
        continue
    done_col_list[i] = 1
    j_list = [i]
    for j in range(W):
        if i != j and np.prod(np.sort(S_arr[:, i]) == np.sort(S_arr[:, j])) == 1:
            j_list.append(j)
            done_col_list[j] = 1
    same_col_list.append(j_list)
    
if len(same_row_list) == (H+1) // 2 and len(same_col_list) == (W+1) // 2:
    if check_ok(apply_switch(S_arr, same_row_list, same_col_list), H, W) == False:
        res = "NO"
elif len(same_row_list) > (H+1) // 2:
    res = "NO"
elif len(same_col_list) > (W+1) // 2:
    res = "NO"
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    h, w = map(int, input().split())
    s = []
    for _ in range(h):
        col = []
        s.append(col)
        for c in input().strip():
            col.append(ord(c))
    c_row = defaultdict(int)
    for col in s:
        c_row[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_row.values()) > h % 2:
        print('NO')
        return
    mid = None
    for row, c in c_row.items():
        if c % 2:
            count = defaultdict(int)
            for ch in row:
                count[ch] += 1
            if sum(cc % 2 for cc in count.values()) > w % 2:
                print('NO')
                return
            for ch, c2 in count.items():
                if c2 % 2:
                    mid = ch

    c_col = defaultdict(int)
    for col in zip(*s):
        c_col[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_col.values()) > w % 2:
        print('NO')
        return

    for col, c in c_col.items():
        if c % 2:
            count = defaultdict(int)
            for ch in col:
                count[ch] += 1
            if sum(cc % 2 for cc in count.values()) > h % 2:
                print('NO')
                return
            for ch, c2 in count.items():
                if c2 % 2:
                    if mid is not None and mid != ch:
                        print('NO')
                        return 

    print('YES')


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
H, W = map(int, input().split())
s = [input() for _ in range(H)]
if H == 1 and W == 1:
    print('YES')
elif H==1:
    print('YES')
else:

    d_h = [[0 for i in range(28)] for _ in range(H)]
    d_w = [[0 for i in range(28)] for _ in range(W)]

    for i in range(H):
        for c in s[i]:
            d_h[i][ord(c) - ord("a")] += 1

    for i in range(H):
        for j in range(W):
            d_w[j][ord(s[i][j]) - ord("a")] += 1
    #
    # for i in range(H):
    #     d_h[i].sort()
    #     d_w[i].sort()

    check_h = []
    check_w = []

    for i in range(H):
        if i in check_h:
            continue
        for j in range(i + 1, H):
            if j in check_h:
                continue
            else:
                if d_h[i] == d_h[j]:
                    check_h.append(i)
                    check_h.append(j)
                    break

    for i in range(W):
        if i in check_w:
            continue
        for j in range(i + 1, W):
            if j in check_w:
                continue
            else:
                if d_w[i] == d_w[j]:
                    check_w.append(i)
                    check_w.append(j)
                    break

    c_w = 0
    c_h = 0

    for i in range(H):
        if i in check_h:
            c_h += 1
    for i in range(W):
        if i in check_w:
            c_w += 1

    if c_h >= H - 1 and c_w >= W - 1:

        print('YES')
    else:
        print('NO')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    h, w = map(int, input().split())
    s = []
    for _ in range(h):
        col = []
        s.append(col)
        for c in input().strip():
            col.append(ord(c))
    c_row = defaultdict(int)
    for col in s:
        c_row[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_row.values()) > h % 2:
        print('NO')
        return
    mid = None
    for row, c in c_row.items():
        if c % 2:
            count = defaultdict(int)
            for ch in row:
                count[ch] += 1
            if sum(cc % 2 for cc in count.values()) > w % 2:
                print('NO')
                return
            for ch, c2 in count.items():
                if c2 % 2:
                    mid = ch

    c_col = defaultdict(int)
    for col in zip(*s):
        c_col[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_col.values()) > w % 2:
        print('NO')
        return

    for col, c in c_col.items():
        if c % 2:
            count = defaultdict(int)
            for ch in col:
                count[ch] += 1
            if sum(cc % 2 for cc in count.values()) > h % 2:
                print('NO')
                return
            for ch, c2 in count.items():
                if c2 % 2:
                    if mid != ch:
                        print('NO')
                        return 

    print('YES')


main()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
TH=[sorted(S[i]) for i in range(H)]
PH=[-1 for i in range(H)]
TW=[sorted([S[i][j] for i in range(H)]) for j in range(W)]
PW=[-1 for j in range(W)]
#0<=i<H,0<=j<W
for i in range(H):
    if PH[i]!=-1:
        continue
    else:
        for k in range(H):
            if k==i:continue
            if TH[k]==TH[i]:
                PH[i]=k
                PH[k]=i
                break
for j in range(W):
    if PW[j]!=-1:
        continue
    else:
        for k in range(W):
            if k==j:continue
            if TW[k]==TW[j]:
                PW[j]=k
                PW[k]=j
                break
if H%2==0:
    for i in range(H):
        if PH[i]==-1:
            print("NO")
            exit()
else:
    if PH.count(-1)>=2:
        print("NO")
        exit()
if W%2==0:
    for i in range(W):
        if PW[i]==-1:
            print("NO")
            exit()
else:
    if PW.count(-1)>=2:
        print("NO")
        exit()
#usedcheck
QH=[0 for i in range(H)]
QW=[0 for j in range(W)]
RH=[]
RW=[]
SH=[-1 for i in range(H)]
SW=[-1 for j in range(W)]
for i in range(H):
    if QH[i]==0:
        if PH[i]==-1:
            SH[H//2]=i
            continue
        RH.append((i,PH[i]))
        QH[i]=1
        QH[PH[i]]=1
for j in range(W):
    if QW[j]==0:
        if PW[j]==-1:
            SW[W//2]=j
            continue
        RW.append((j,PW[j]))
        QW[j]=1
        QW[PW[j]]=1
for i in range(H//2):
    SH[i]=RH[i][0]
    SH[H-1-i]=RH[i][1]
for j in range(W//2):
    SW[j]=RW[j][0]
    SW[W-1-j]=RW[j][1]
'''
XH=sorted(SH)
XW=sorted(SW)
for i in range(H):
    if i!=XH[i]:
        print("NO")
        exit()
for j in range(W):
    if j!=XW[j]:
        print("NO")
        exit()
'''
U=[[S[SH[i]][SW[j]] for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if U[i][j]!=U[H-1-i][W-1-j]:
            print("NO")
            exit()
print("YES")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import numpy as np
from copy import deepcopy
from collections import Counter

def main():
    H, W = map(int, input().split())
    area = np.array([list(input()) for _ in range(H)])

    hcounts = [Counter(area[i, :]) for i in range(H)]
    vcounts = [Counter(area[:, i]) for i in range(W)]

    h_paired, v_paired = set(), set()
    h_pairs, v_pairs = [], []
    for i in range(H):
        if i in h_paired:
            continue
        for j in range(i+1, H):
            if j in h_paired:
                continue
            if hcounts[i]==hcounts[j]:
                h_paired |= {i, j}
                h_pairs.append((i, j))
    
    for i in range(W):
        if i in v_paired:
            continue
        for j in range(i+1, W):
            if j in v_paired:
                continue
            if vcounts[i]==vcounts[j]:
                v_paired |= {i, j}
                v_pairs.append((i, j))
    
    if H-len(h_paired) >= 2 or W-len(v_paired) >= 2:
        print('NO')
        return

    # 実際にならべなおす
    # print(h_pairs, v_pairs)
    h_pos = list(range(H))
    v_pos = list(range(W))
    area_orig = deepcopy(area)

    for i, (a, b) in enumerate(h_pairs):
        area[i, :] = area_orig[a, :]
        area[H-1-i, :] = area_orig[b, :]
    for c in set(range(H))-h_paired:
        area[H//2, :] = area_orig[c, :]
    
    area_orig = deepcopy(area)
    for i, (a, b) in enumerate(v_pairs):
        area[:, i] = area_orig[:, a]
        area[:, W-1-i] = area_orig[:, b]
    for c in set(range(W))-v_paired:
        area[:, W//2] = area_orig[:, c]
    
    for i in range(H):
        for j in range(W):
            if area[i, j] != area[H-i-1, W-j-1]:
                print('NO')
                return
    print('YES')
            

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def can_palindrome(s):
    l = []
    for c in s:
        if c in l:
            l.remove(c)
        else:
            l.append(c)

    if len(s) % 2 == 0:
        return len(l) == 0
    else:
        return len(l) == 1


def can_pair(s1, s2):
    l = []
    for c1, c2 in zip(s1, s2):
        c = sorted([c1, c2])
        if c in l:
            l.remove(c)
        else:
            l.append(c)

    if len(s1) % 2 == 0:
        return len(l) == 0
    else:
        return len(l) == 1


def pair_graph(s1, s2):
    N = len(s1)
    G = np.zeros([N, N])
    for i in range(N):
        for j in range(i+1, N):
            if s1[i] == s2[j] and s1[j] == s2[i]:
                G[i, j] = 1
                G[j, i] = 1
    return G

import numpy as np
H, W = list(map(int, input().split(' ')))
S = []
d = defaultdict(list)

for h in range(H):
    s = input()
    S.append(s)
    d[''.join(sorted(S))].append(h)

already_paired = np.zeros(H)

Gs = []

for i in range(H):
    if already_paired[i]:
        continue

    for j in range(i+1, H):
        if already_paired[j]:
            continue

        if can_pair(S[i], S[j]):
            already_paired[i] = 1
            already_paired[j] = 1
            G = pair_graph(S[i], S[j])
            Gs.append(G)

if already_paired.sum() < H - 1:
    print('NO')
    exit()

elif already_paired.sum() == H - 1:
    for i in range(H):
        if already_paired[i] == 0:
            Gs.append(pair_graph(S[i], S[i]))
            break

G = np.array(Gs).sum(axis=0) // len(Gs)

def is_perfect_matching(G):
    N = len(G)
    for i in range(N):
        for j in range(i+1, N):
            if G[i, j] == 1:
                l = list(range(N))
                l.remove(i)
                l.remove(j)
                if len(l) == 0:
                    return True
                if is_perfect_matching(G[l][:, l]):
                    return True
    return False

if is_perfect_matching(G):
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter

H, W = list(map(int, input().split()))
S = np.array([list(input()) for _ in range(H)])

def main(S):
    u, c = np.unique(S), list(Counter(S.flatten()).values())
    c = np.array(c)
    if all([i%2==1 for i in S.shape]):
        if np.sum(c%2) != 1:
            print("NO")
            return
    else:
        if np.sum(c%2) >= 1:
            print("NO")
            return
    print("YES")
main(S)

Submission status: Wrong Answer

Solution code:
#! -*- coding: utf-8 -*-

import numpy as np

h,w = map(int,raw_input().split())
s_l = []
al = "abcdefghijklmnopqrstuvwxyz"
al_gyou = np.zeros([h,26])
al_retsu = np.zeros([w,26])
for i in range(h):
    line = raw_input()
    #s_l.append(line)
    for j in range(w):
        for k in range(26):
            if line[j] == al[k]:
                al_gyou[i][k]+=1
                al_retsu[j][k]+=1

#print al_gyou
#print al_retsu

count = 0
flag = 0

gyou_kakunin = np.zeros([h])
retsu_kakunin = np.zeros([w])

for i in range(h):
    status = 0
    if gyou_kakunin[i] == 1:
        status = 1
    else:
        for j in range(h):
            if i==j or gyou_kakunin[j] == 1:
                pass
            else:
                if np.allclose(al_gyou[i],al_gyou[j]):
                    status = 1
                    break
    if status == 0:
        count += 1
        break

#print count
if count > h%2:
    flag =1

count = 0
for i in range(w):
    status = 0
    if retsu_kakunin[i] == 1:
        status = 1
    else:
        for j in range(w):
            if i==j or retsu_kakunin[j] == 1:
                pass
            else:
                if np.allclose(al_retsu[i],al_retsu[j]):
                    status = 1
                    break
    if status == 0:
        count += 1
        break

#print count
if count > w%2:
    flag = 1

if flag == 0:
    ans = "YES"
else:
    ans = "NO"

print ans

Submission status: Wrong Answer

Solution code:
a = ord('a')
z = ord('z')

def isEq(l1, l2):
	for i in range(len(l1)):
		if l1[i] != l2[i]:
			return False
	return True
	
def isOK(l):
	L = sorted([(l[i], i) for i in range(len(l))])
	lenL = len(L)
	i = 0
	while i < len(L) - 1:
		if isEq(L[i][0], L[i+1][0]):
			L.pop(i)
			L.pop(i)
		else:
			i += 1
	if len(L) > lenL % 2:
		return (False, None, None)
	if lenL % 2 == 1:
		ret_i = L[0][1]
		x = L[0][0]
		C = [(x.count(chr(c)), chr(c)) for c in range(a, z+1) if x.count(chr(c)) % 2 == 1]
		if len(C) > 1:
			return (False, None, None)
		else:
			if len(C) == 0:
				return (True, ret_i, None)
			else:
				return (True, ret_i, C[0][1])
	else:
		return (True, None, None)

H,W = map(int,input().split())
S = []
for i in range(H):
	S.append(input())

row_list = [sorted(list(s)) for s in S]
col_list = [sorted([S[i][j] for i in range(H)])for j in range(W)]
flag1, row, c1 = isOK(row_list)
flag2, col, c2 = isOK(col_list)

if flag1 and flag2:
	if c1 is not None and c2 is not None:
		if c1 == c2:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
T = [[None]*H for i in range(W)]
D = {}
for i in range(H):
    for j in range(W):
        c = S[i][j]
        D[c] = D.get(c, 0) ^ 1
if sum(D.values()) != (1 if (H%2==1)and(W%2==1) else 0):
    print("NO")
    exit(0)
for i in range(H):
    s = S[i]
    for j in range(W):
        T[j][i] = s[j]
def check(S, H, W):
    res = []
    for p in range(H):
        sp = S[p]
        for q in range(p+1, H):
            sq = S[q]
            d = {}
            for k in range(W):
                if sp[k] < sq[k]:
                    k = sp[k], sq[k]
                    d[k] = d.get(k, 0) + 1
                elif sp[k] == sq[k]:
                    k = sp[k], sp[k]
                    d[k] = d.get(k, 0) ^ 1
                else:
                    k = sq[k], sp[k]
                    d[k] = d.get(k, 0) - 1
            cap = (W % 2)
            ok = 1
            for a, b in d:
                if a == b:
                    if d[a, b]:
                        if cap == 0:
                            ok = 0
                        cap -= 1
                else:
                    if d[a, b] != 0:
                        ok = 0
            if ok: res.append((p, q))
    if H % 2 == 1:
        for p in range(H):
            d = {}
            for s in S[p]:
                d[s] = d.get(s, 0) ^ 1
            if sum(d.values()) == W % 2:
                res.append((p, p))
    return res
sc = check(S, H, W)
tc = check(T, W, H)
def solve(N, P):
    def dfs(state, c):
        if N == c:
            return 1
        for p, q in P:
            v = (1 << p) | (1 << q)
            if state & v:
                continue
            if dfs(state | v, (c+2 if p != q else c+1)):
                return 1
        return 0
    return dfs(0, 0)
if solve(H, sc) and solve(W, tc):
    print("YES")
else:
    print("NO")