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:

"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W

WA…
→どうやらNOをYESと表示しているらしい
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin
import sys

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])
#print (S)

#ペア列挙
p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])

#print (p)

for pl in p:
    able = [True] * H
    flag = 0
    #print (pl)
    for i in range(H):
        if able[i]:
            for j in range(i+1,H):
                if not able[j]:
                    continue
                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]] or S[j][pl[2*w]] != S[i][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                if H % 2 == 0 or flag == 1:
                    flag = 2
                    break
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[i][pl[2*w+1]]:
                        flag = 2
                        break
                else:
                    flag = 1
                    able[i] = False
                    print (i)
                if flag == 2:
                    break
                
    if flag != 2:
        #print (flag)
        #print (pl)
        print ("YES")
        break
else:
    print ("NO")

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin
import sys

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])
#print (S)

#ペア列挙
p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])

#print (p)

for pl in p:
    able = [True] * H
    flag = 0

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

                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]] or S[j][pl[2*w]] != S[i][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                if H % 2 == 0 or flag == 1:
                    flag = 2
                    break
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[i][pl[2*w+1]]:
                        flag = 2
                        break
                else:
                    flag = 1
                    able[i] = False
                
    if flag != 2:
        print ("YES")
        break
else:
    print ("NO")

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin
import sys

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])
#print (S)

#ペア列挙
p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])

#print (p)

for pl in p:
    able = [True] * H
    flag = 0

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

                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]] or S[j][pl[2*w]] != S[i][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                if H % 2 == 0 or flag == 1:
                    flag = 2
                    break
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[i][pl[2*w+1]]:
                        flag = 2
                        break
                else:
                    flag = 1
                    able[i] = False
                
    if flag != 2:
        print ("YES")
        break
else:
    print ("NO")

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin
import sys

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])
#print (S)

#ペア列挙
p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])

for pl in p:
    able = [True] * H
    flag = 0

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

                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                if H % 2 == 0 or flag == 1:
                    flag = 2
                    break
                j = i
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]]:
                        flag = 2
                        break
                else:
                    flag = 1
                
    if flag != 2:
        print ("YES")
        break
else:
    print ("NO")

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])
#print (S)

#ペア列挙
p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])

for pl in p:
    able = [True] * H
    flag = True

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

                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                flag = False
                break
    if flag:
        print ("YES")
        break
else:
    print ("NO")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import random
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
flgx,flgy = 0,0
for _ in range(300):
  random.shuffle(grid)
  if judge(grid):
    flgx = 1
    break
for _ in range(300):
  random.shuffle(gt)
  if judge(gt):
    flgy = 1
    break
if flgx*flgy:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import random
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
flgx,flgy = 0,0
for _ in range(100):
  random.shuffle(grid)
  if judge(grid):
    flgx = 1
for _ in range(100):
  random.shuffle(gt)
  if judge(gt):
    flgy = 1
if flgx*flgy:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
def check(field):
    tr = list(map(''.join, zip(*field)))
    paired = set()
    center = -1
    for i, col1 in enumerate(tr):
        if i in paired:
            continue
        for j, col2 in enumerate(tr[i + 1:], start=i + 1):
            if j in paired:
                continue
            if col1 == col2[::-1]:
                paired.add(i)
                paired.add(j)
                break
        else:
            if center == -1 and col1 == col1[::-1]:
                center = i
            else:
                return False
    return True


def arrange_row(field, new_field, i, remain):
    if len(remain) == 0:
        return check(new_field)
    j = remain.pop()
    new_field[i] = field[j]
    if len(remain) == 0:
        result = check(new_field)
        if result:
            return True
        remain.add(j)
        return False
    for k in list(remain):
        remain.remove(k)
        new_field[h - i - 1] = field[k]
        result = arrange_row(field, new_field, i + 1, remain)
        if result:
            return True
        remain.add(k)
    remain.add(j)
    return False


h, w = map(int, input().split())
field = [input() for _ in range(h)]
print('YES' if arrange_row(field, [None] * h, 0, set(range(h))) else 'NO')

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


# ペアのとり方は 10395 通り
# a = math.factorial(12) / (2 ** 6) / math.factorial(6)
# print(a)  # 10395

def test(groups):
    # print(groups)
    # return False
    seen = [False] * 6
    order = [-1] * len(groups)
    for i, g in enumerate(groups):
        if g == -1:
            # 真ん中
            order[W // 2] = i
            continue
        if not seen[g]:
            order[g] = i
            seen[g] = True
        else:
            order[~g] = i

    rows = []
    for s in S:
        row = ''
        for i in order:
            row += s[i]
        rows.append(row)
    ok = [False] * H
    for i in range(H):
        if ok[i]:
            continue
        rev = rows[i][::-1]
        for j in range(i, H):
            if not ok[j] and rows[j] == rev:
                ok[i] = ok[j] = True
                break
    ng_cnt = ok.count(False)
    if ng_cnt == 0:
        return True
    if ng_cnt == 1:
        i = ok.index(False)
        return rows[i] == rows[i][::-1]
    return False


def solve(groups, depth=0):
    if depth == W // 2:
        return test(groups)

    i = 0
    for _ in range(2 if W % 2 == 1 else 1):
        while groups[i] != -1:
            i += 1

        groups[i] = depth
        for j in range(i + 1, W):
            if groups[j] != -1:
                continue
            groups[j] = depth
            if solve(groups, depth + 1):
                return True
            groups[j] = -1
        groups[i] = -1
        i += 1

    return False


groups = [-1] * W
ok = solve(groups)
if ok:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


# ペアのとり方は 10395 通り
# a = math.factorial(12) / (2 ** 6) / math.factorial(6)
# print(a)  # 10395

def test(groups):
    seen = [False] * 6
    order = [-1] * len(groups)
    for i, g in enumerate(groups):
        if g == -1:
            # 真ん中
            order[W // 2] = i
            continue
        if not seen[g]:
            order[g] = i
            seen[g] = True
        else:
            order[~g] = i

    rows = []
    for s in S:
        row = ''
        for i in order:
            row += s[i]
        rows.append(row)
    ok = [False] * H
    for i in range(H):
        if ok[i]:
            continue
        rev = rows[i][::-1]
        for j in range(i, H):
            if not ok[j] and rows[j] == rev:
                ok[i] = ok[j] = True
                break
    ng_cnt = ok.count(False)
    if ng_cnt == 0:
        return True
    if ng_cnt == 1:
        i = ok.index(False)
        return rows[i] == rows[i][::-1]
    return False


def solve(groups, depth=0):
    if depth == W // 2:
        return test(groups)

    i = 0
    while groups[i] != -1:
        i += 1
    for i in (range(i, i + 2) if W % 2 == 1 and depth == 0 else range(i, i + 1)):
        groups[i] = depth
        for j in range(i + 1, W):
            if groups[j] != -1:
                continue
            groups[j] = depth
            if solve(groups, depth + 1):
                return True
            groups[j] = -1
        groups[i] = -1

    return False


groups = [-1] * W
ok = solve(groups)
if ok:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


# ペアのとり方は 10395 通り
# a = math.factorial(12) / (2 ** 6) / math.factorial(6)
# print(a)  # 10395

def test(groups):
    seen = [False] * 6
    order = [-1] * len(groups)
    for i, g in enumerate(groups):
        if g == -1:
            # 真ん中
            order[W // 2] = i
            continue
        if not seen[g]:
            order[g] = i
            seen[g] = True
        else:
            order[~g] = i

    rows = []
    for s in S:
        row = ''
        for i in order:
            row += s[i]
        rows.append(row)
    ok = [False] * H
    for i in range(H):
        if ok[i]:
            continue
        rev = rows[i][::-1]
        for j in range(i, H):
            if not ok[j] and rows[j] == rev:
                ok[i] = ok[j] = True
                break
    ng_cnt = ok.count(False)
    if ng_cnt == 0:
        return True
    if ng_cnt == 1:
        i = ok.index(False)
        return rows[i] == rows[i][::-1]
    return False


def solve(groups, depth=0):
    if depth == W // 2:
        return test(groups)

    i = 0
    while groups[i] != -1:
        i += 1
    groups[i] = depth
    for j in range(i + 1, W):
        if groups[j] != -1:
            continue
        groups[j] = depth
        if solve(groups, depth + 1):
            return True
        groups[j] = -1
    groups[i] = -1
    return False


groups = [-1] * W
ok = solve(groups)
if ok:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations
from random import randrange
readline = sys.stdin.readline

mod = 10**9+9
base = 2009   
def rollinhash(S):
    N = len(S)           
    has = 0
    for i in range(N):
        s = S[i]
        has = (has*base + s)%mod
    return has

phr = []
while len(set(phr)) != 26:
    phr = [randrange(1, 10**9) for _ in range(26)]
def shash(S):
    N = len(S)            
    has = 0
    for i in range(N):
        has = has + phr[S[i]]*phr[S[N-1-i]]
    return has

H, W = map(int, readline().split())
G = [list(map(ord, readline().strip())) for _ in range(H)]

ans = 'No'
fh = H//2
ch = H-fh
lir = list(range(H))
seen = set()
for k in permutations(lir, ch):
    k = list(k)
    sk = set(k)
    for i in range(H):
        if i not in sk:
            k.append(i)
    
    sh = shash(k)
    if sh in seen:
        continue
    seen.add(sh)
    
    
    G2 = []
    for j in k:
        G2.append(G[j])
    G2 = list(map(list, zip(*G2)))
    G2h = [rollinhash(g) for g in G2]
    G2hi = [rollinhash(g[::-1]) for g in G2]
    
    used = [False]*W
    w1 = 0
    match = W//2
    while match and w1 < W:
        if used[w1]:
            w1 += 1
            continue
        sa = G2hi[w1]
        for w2 in range(w1+1, W):
            if used[w2]:
                continue
            if G2h[w2] == sa:
                used[w1] = True
                used[w2] = True
                match -= 1
                break
        w1 += 1
    if sum(used) >= W-1:
        if sum(used) == W-1:
            mid = used.index(False)
            if G2h[mid] == G2hi[mid]:
                ans = 'Yes'
        else:
            ans = 'Yes'
    if ans == 'Yes':
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)

def main():
    def per(s, a=[]):
        if not s:
            return [a]
        if len(s) % 2:
            cs = copy.deepcopy(s)
            res = []
            for u in cs:
                s.remove(u)
                res += per(s, [u] + a)
                s.add(u)
            return res
        u = min(s)
        s.remove(u)
        cs = copy.deepcopy(s)
        res = []
        for uu in cs:
            if uu < u: continue
            s.remove(uu)
            res += per(s, a + [u, uu])
            s.add(uu)
        s.add(u)
        return res

    ord_a = ord("a")
    h, w = map(int, input().split())
    t0 = [[ord(c) - ord_a for c in input()] for _ in range(h)]
    h_set = set(range(h))
    pattern = per(h_set)
    # print(t0)
    # print(pattern)
    b = h % 2
    for p in pattern:
        t1 = [[-1] * h for _ in range(w)]
        if b:
            i = h // 2
            for j in range(w):
                t1[j][i] = t0[p[0]][j]
        for i in range(b, h, 2):
            for j in range(w):
                t1[j][i - b] = t0[p[i]][j]
                t1[j][h - 1 - i + b] = t0[p[i + 1]][j]
        # print(p)
        # print(t1)
        fin = [False] * w
        mid = (w % 2 == 1)
        br = False
        for i, k in enumerate(t1):
            if fin[i]: continue
            k0 = k[::-1]
            fin[i] = True
            for j in range(i + 1, w):
                if fin[j]: continue
                k1 = t1[j]
                if k0 == k1:
                    fin[j] = True
                    break
            else:
                if mid and k == k0:
                    mid = False
                else:
                    br = True
                    break
        if br: continue
        print("YES")
        exit()
    print("NO")

main()

Submission status: Wrong Answer

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)

def main():
    def per(s, a=[]):
        if not s:
            return [a]
        if len(s) % 2:
            cs = copy.deepcopy(s)
            res = []
            for u in cs:
                s.remove(u)
                res += per(s, [u] + a)
                s.add(u)
            return res
        u = min(s)
        s.remove(u)
        cs = copy.deepcopy(s)
        res = []
        for uu in cs:
            if uu < u: continue
            s.remove(uu)
            res += per(s, a + [u, uu])
            s.add(uu)
        s.add(u)
        return res

    ord_a = ord("a")
    h, w = map(int, input().split())
    t0 = [[ord(c) - ord_a for c in input()] for _ in range(h)]
    h_set = set(range(h))
    pattern = per(h_set)
    # print(t0)
    # print(pattern)
    b = h % 2
    for p in pattern:
        t1 = [[] for _ in range(h)]
        if b:
            t1[h // 2] = t0[p[0]]
        for i in range(b, h, 2):
            t1[i - b] = t0[p[i]]
            t1[h - 1 - i + b] = t0[p[i + 1]]
        # print(p)
        # print(t1)
        fin = [False] * w
        mid = (w % 2 == 1)
        br = False
        for j, c0 in enumerate(zip(*t1)):
            if fin[j]: continue
            fin[j] = True
            c0 = c0[::-1]
            for jj, c1 in enumerate(zip(*t1)):
                if jj <= j: continue
                if fin[jj]: continue
                if c0 == c1:
                    fin[jj] = True
                    break
            else:
                if mid and c0==c0[::-1]:
                    mid = False
                else:
                    br = True
                    break
        if br: continue
        print("YES")
        exit()
    print("NO")

main()

Submission status: Wrong Answer

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)

def main():
    def per(s, a=[]):
        if not s:
            return [a]
        if len(s) % 2:
            cs = copy.deepcopy(s)
            res = []
            for u in cs:
                s.remove(u)
                res += per(s, [u] + a)
                s.add(u)
            return res
        u = min(s)
        s.remove(u)
        cs = copy.deepcopy(s)
        res = []
        for uu in cs:
            if uu < u: continue
            s.remove(uu)
            res += per(s, a + [u, uu])
            s.add(uu)
        s.add(u)
        return res

    ord_a = ord("a")
    h, w = map(int, input().split())
    t0 = [[ord(c) - ord_a for c in input()] for _ in range(h)]
    h_set = set(range(h))
    pattern = per(h_set)
    # print(t0)
    # print(pattern)
    b = h % 2
    for p in pattern:
        t1 = [[] for _ in range(h)]
        if b:
            t1[h // 2] = t0[p[0]]
        for i in range(b, h, 2):
            t1[i - b] = t0[p[i]]
            t1[h - 1 - i + b] = t0[p[i + 1]]
        # print(t1)
        fin = [False] * w
        mid = (w % 2 == 1)
        br = False
        for j, c0 in enumerate(zip(*t1)):
            if fin[j]: continue
            fin[j] = True
            c0 = c0[::-1]
            for jj, c1 in enumerate(zip(*t1)):
                if jj <= j: continue
                if fin[jj]: continue
                if c0 == c1:
                    fin[jj] = True
                    break
            else:
                if mid:
                    mid = False
                else:
                    br = True
                    break
        if br: continue
        print("YES")
        exit()
    print("NO")

main()