Problem:


Score : 400 points

Problem Statement

We have an H-by-W matrix.
Let a_{ij} be the element at the i-th row from the top and j-th column from the left.
In this matrix, each a_{ij} is a lowercase English letter.

Snuke is creating another H-by-W matrix, A', by freely rearranging the elements in A.
Here, he wants to satisfy the following condition:

Every row and column in A' can be read as a palindrome.

Determine whether he can create a matrix satisfying the condition.

Note

A palindrome is a string that reads the same forward and backward.
For example, a, aa, abba and abcba are all palindromes, while ab, abab and abcda are not.

Constraints

1 ≤ H, W ≤ 100

a_{ij} is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}

Output

If Snuke can create a matrix satisfying the condition, print Yes; otherwise, print No.

Sample Input 1

3 4
aabb
aabb
aacc

Sample Output 1

Yes

For example, the following matrix satisfies the condition.

abba
acca
abba

Sample Input 2

2 2
aa
bb

Sample Output 2

No

It is not possible to create a matrix satisfying the condition, no matter how we rearrange the elements in A.

Sample Input 3

5 1
t
w
e
e
t

Sample Output 3

Yes

For example, the following matrix satisfies the condition.

t
e
w
e
t

Sample Input 4

2 5
abxba
abyba

Sample Output 4

No

Sample Input 5

1 1
z

Sample Output 5

Yes



Sample input:
3 4
aabb
aabb
aacc


Sample output:
Yes

Submission status: Accepted

Solution code:
import collections, itertools

h, w = map(int, input().split())
a = [input() for _ in range(h)]

b = [[None] * w for _ in range(h)]
count = 0
for x in range(h):
    for y in range(w):
        if b[x][y] is not None:
            continue
        b[x][y] = count
        b[h-x-1][y] = count
        b[x][w-y-1] = count
        b[h-x-1][w-y-1] = count
        count += 1

d1 = collections.Counter(a[x][y] for x, y in itertools.product(range(h), range(w)))
d2 = collections.Counter(b[x][y] for x, y in itertools.product(range(h), range(w)))

for k2 in sorted(d2, key=lambda k: d2[k], reverse=True):
    ok = False
    v2 = d2[k2]
    for k1 in sorted(d1, key=lambda k: d1[k], reverse=True):
        v1 = d1[k1]
        if v2 <= v1:
            d1[k1] -= v2
            ok = True
            break
    if not ok:
        print('No')
        exit(0)

print('Yes')

Submission status: Accepted

Solution code:
from collections import Counter

h,w = map(int, input().split())
e_mod4 = (h//2) * (w//2)
e_mod2 = (h%2) * w//2 + (w%2) * h//2
e_mod1 = (h%2) * (w%2)

ca = Counter([j for i in range(h) for j in list(input())])

mod4, mod2, mod1 = 0, 0, 0
for i in ca.values():
     mod4 += i // 4
     i %= 4
     mod2 += i // 2
     i %= 2
     mod1 += i

if mod4 > e_mod4:
    mod2 += (mod4 - e_mod4) * 2
    mod4 = e_mod4

print("Yes" if e_mod4 == mod4 and e_mod2 == mod2 and e_mod1 == mod1 else "No")

Submission status: Accepted

Solution code:
from collections import defaultdict
H,W=map(int,input().split())
A="".join([input() for _ in range(H)])
cnts = defaultdict(lambda: 0)
for c in A:
    cnts[c]+=1
    
n4 = ((H-H%2)*(W-W%2))//4
n2 = (H%2)*(W//2)+(W%2)*(H//2)
n1 = 1 if H%2+W%2 == 2 else 0

for _,cnt in cnts.items():
    n4 -= (cnt//4)
    n2 -= (cnt%4)//2
    n1 -= (cnt%2)

if n4==0 and n2==0 and n1==0:
    print("Yes")
elif n4<0 and n2>0 and (-4)*n4==2*n2:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import string
string.ascii_lowercase

H,W = map(int,input().split())
A = ''
for i in range(H):
  A += input()
#print(A)

S = {}
for s in string.ascii_lowercase:
  if A.count(s) > 0:
    S[s] = A.count(s)
#print(S)

h1 = H//2
w1 = W//2
h2 = H - h1*2
w2 = W - w1*2
for i in range(h1*w1):
  flag = True
  for s in S.keys():
    if S[s] >= 4:
      S[s] -= 4
      flag = False
      break
  if flag:
    print('No')
    exit()
for i in range(h1*w2+w1*h2):
  flag = True
  for s in S.keys():
    if S[s] >= 2:
      S[s] -= 2
      flag = False
      break
  if flag:
    print('No')
    exit()
print('Yes')

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())

a = ''.join(input() for _ in range(H))
c = collections.Counter(a)

if H % 2 == 0 and W % 2 == 0:
    if all(v % 4 == 0 for v in c.values()):
        print('Yes')
    else:
        print('No')

elif H % 2 == 1 and W % 2 == 1:
    d = (H-1)//2+(W-1)//2
    if sum(v % 2 for v in c.values()) <= 1 and sum(1 if v % 4 >= 2 else 0 for v in c.values()) <= d:
        print('Yes')
    else:
        print('No')

else:
    if H % 2 == 0:
        d = H//2
    else:
        d = W//2

    if sum(v % 2 for v in c.values()) >= 1:
        print('No')
        exit()

    if sum(1 if v % 4 == 2 else 0 for v in c.values()) <= d:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
words = "abcdefghijklmnopqrstuvwxyz"
def make_palindrome(instr):
    chara_list = [ 0 for i in range(26) ]
    outstr = []
    for i in instr:
        chara_list[words.index(i)] += 1

    chara_list_2 = [ i % 2 for i in chara_list ]
    if len(instr) % 2 == 1:
        if chara_list_2.count(1) > 1:
            outstr = "NG"
        else:
            m = chara_list_2.index(1)
            for j, v in enumerate(chara_list):
                if j != m and v != 0:
                    outstr.append(words[j]*(v//2))
            outstr.append(words[m])
            outstr +=  outstr[:len(outstr)-1][::-1]

    else:
        if chara_list_2.count(1) > 0:
            outstr = "NG"
        else:
            for j, v in enumerate(chara_list):
                if v != 0:
                    outstr.append(words[j]*(v//2))
            outstr +=  outstr[::-1]
    outstr = "".join(outstr)
    return outstr

h, w = [ int(v) for v in input().split() ]
words_list = [0 for i in range(26)]
ans = "No"
if h == 1:
    if make_palindrome(input()) != "NG":
        ans = "Yes"
elif w == 1:
    tate = [ input() for i in range(h) ]
    if make_palindrome(tate) != "NG":
        ans = "Yes"
else:
    for i in range(h):
        for j in input():
            words_list[words.index(j)] += 1

    if h % 2 == 0 and w % 2 == 0:
        if all([ i % 4 == 0 for i in words_list ]):
            ans = "Yes"
    elif h % 2 == 1 and w % 2 == 0:
        if all([ i % 2 == 0 for i in words_list ]):
            if [ i % 2 == 0 and i % 4 != 0 for i in words_list ].count(True) <= w//2:
                ans = "Yes"
    elif h % 2 == 0 and w % 2 == 1:
        if all([ i % 2 == 0 for i in words_list ]):
            if [ i % 2 == 0 and i % 4 != 0 for i in words_list ].count(True) <= h//2:
                ans = "Yes"
    elif h % 2 == 1 and w % 2 == 1:
        if [ i % 2 for i in words_list ].count(1) == 1:
            words_list = [ i // 2 * 2 for i in words_list ]
            if [ i % 2 == 0 and i % 4 != 0 for i in words_list ].count(True) <= h//2 + w//2:
                ans = "Yes"

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ns = {}
for i in range(H):
  As = input()
  for a in As:
    if a not in ns: ns[a] = 0
    ns[a] += 1
ns4 = [0, 0, 0, 0]
for a in ns:
  n = ns[a]
  ns4[n%4] += 1
#print(ns4)
if H%2 == 0 and W%2 == 0:
  if ns4[1] > 0 or ns4[2] > 0 or ns4[3] > 0:
    print("No")
  else:
    print("Yes")
if H%2 == 1 and W%2 == 0:
  if ns4[1]+ns4[3] > 0:
    print("No")
  elif ns4[2] > W//2:
    print("No")
  else:
    print("Yes")
if H%2 == 0 and W%2 == 1:
  if ns4[1]+ns4[3] > 0:
    print("No")
  elif ns4[2] > H//2:
    print("No")
  else:
    print("Yes")
if H%2 == 1 and W%2 == 1:
  if ns4[1]+ns4[3] > 1:
    print("No")
  elif ns4[2]+ns4[3] > H//2+W//2:
    print("No")
  else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import Counter
from heapq import heappop,heappush,heapify

H,W = map(int,input().split())
A = ''.join(input().rstrip() for _ in range(H))

q = list(-x for x in Counter(A).values())
heapify(q)

pop = lambda: -heappop(q)
push = lambda x: heappush(q,-x)

tasks = [4] * (H//2) * (W//2)
tasks += [2] * ((H%2) * (W//2) + (W%2) * (H//2))
tasks += [1] * ((H%2) * (W%2))

bl = True
for k in tasks:
    n = pop()
    if n < k:
        bl = False
        break
    push(n-k)

answer = 'Yes' if bl else 'No'
print(answer)

tasks

Submission status: Accepted

Solution code:
d = dict()
for i in range(26):
  d[chr(97+i)] = 0
h,w = map(int, input().split())
for _ in range(h):
  for x in input():
    d[x] +=1
cno = 0
cn2 = 0
for x in d:
  if d[x]%2:
    cno +=1
  elif d[x]%4:
    cn2 += 1
ans = ["No","Yes"]
print(ans[(cno<=(h*w%2))&(cn2<=((h%2)*w//2+(w%2)*h//2))])

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools





def main():

    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    count_dic = defaultdict(int)

    for i in range(high):
        for j in range(width):
            count_dic[data[i][j]] += 1

    odd, even = 0, 0
    if high % 2 and width % 2:
        odd += 1
    if high % 2:
        even += width // 2
    if width % 2:
        even += high // 2

    for key, value in count_dic.items():
        value %= 4
        # print(even, odd, value)
        if value % 2:
            odd -= 1
            value -= 1
        if value == 2:
            even -= 1
        if even < 0 or odd < 0:
            break

    if even < 0 or odd < 0:
        print('No')
    else:
        print('Yes')





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# code-festival-2017-qualaC - Palindromic Matrix
from collections import Counter


def main():
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    single = H & W & 1
    double = (H >> 1 if W & 1 else 0) + (W >> 1 if H & 1 else 0)
    C_mod4 = [i % 4 for i in Counter("".join(A)).values()]
    flg = C_mod4.count(1) + C_mod4.count(3) <= single and C_mod4.count(2) <= double
    print("Yes" if flg else "No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2017-qualaC - Palindromic Matrix
def main():
    H, W, *A = open(0).read().split()
    H, W, C = int(H), int(W), {}
    for i in "".join(A):
        if i not in C:
            C[i] = 0
        C[i] += 1
    single = H & W & 1
    double = (H >> 1 if W & 1 else 0) + (W >> 1 if H & 1 else 0)
    C_mod4 = [i % 4 for i in C.values()]
    flg = C_mod4.count(1) + C_mod4.count(3) <= single and C_mod4.count(2) <= double
    print("Yes" if flg else "No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2017-qualaC - Palindromic Matrix
from collections import defaultdict


def main():
    H, W, *A = open(0).read().split()
    H, W, C = int(H), int(W), defaultdict(int)
    for i in "".join(A):
        C[i] += 1
    single = H & W & 1
    double = (H >> 1 if W & 1 else 0) + (W >> 1 if H & 1 else 0)
    C_mod4 = [i % 4 for i in C.values()]
    flg = C_mod4.count(1) + C_mod4.count(3) <= single and C_mod4.count(2) <= double
    print("Yes" if flg else "No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2017-qualaC - Palindromic Matrix
from collections import Counter


def main():
    H, W, *A = open(0).read().split()
    H, W, C = int(H), int(W), Counter("".join(A)).values()
    single = H & W & 1
    double = (H >> 1 if W & 1 else 0) + (W >> 1 if H & 1 else 0)
    C_mod4 = [i % 4 for i in C]
    flg = C_mod4.count(1) + C_mod4.count(3) <= single and C_mod4.count(2) <= double
    print("Yes" if flg else "No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2017-qualaC - Palindromic Matrix
from collections import Counter


def main():
    H, W, *A = open(0).read().split()
    H, W, C = int(H), int(W), Counter("".join(A)).values()
    single = H & W & 1
    double = (H >> 1 if W & 1 else 0) + (W >> 1 if H & 1 else 0)
    C_mod4, C_div4 = zip(*[(i % 4, i // 4) for i in C])
    flg = C_mod4.count(1) + C_mod4.count(3) <= single and C_mod4.count(2) <= double
    print("Yes" if flg else "No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2017-qualaC - Palindromic Matrix
from collections import Counter


def main():
    H, W, *A = open(0).read().split()
    H, W, C = int(H), int(W), Counter("".join(A)).values()
    g4 = H * W // 4
    if H % 2 and W % 2:
        g1, g2 = 1, H // 2 + W // 2
    elif H % 2 or W % 2:
        g1, g2 = 0, (W // 2 if H % 2 else H // 2)
    else:
        g1, g2 = 0, 0
    for i in C:
        x = min(i // 4, g4)
        i -= x * 4
        g4 -= x
        y = min(i // 2, g2)
        i -= y * 2
        g2 -= y
        if i % 2 and g1:
            i -= 1
            g1 -= 1
        if i:
            print("No")
            return
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [input() for i in range(h)]

memo = {}
for i in range(h):
    for j in range(w):
        if a[i][j] not in memo:
            memo[a[i][j]] = 1
        else:
            memo[a[i][j]] += 1

used = [[False]*w for i in range(h)]
cnt_4 = 0
cnt_2 = 0
cnt_1 = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        cnt = 4
        if 2 * i + 1 == h:
            cnt = cnt // 2
        if 2 * j + 1 == w:
            cnt = cnt // 2
        if cnt == 4:
            cnt_4 += 1
        if cnt == 2:
            cnt_2 += 1
        if cnt == 1:
            cnt_1 += 1
        used[i][j] = True
        used[-i-1][j] = True
        used[i][-j-1] = True
        used[-i-1][-j-1] = True

for i in memo:
    tmp = memo[i] // 4
    if tmp < cnt_4:
        memo[i] -= tmp * 4
        cnt_4 -= tmp
    elif tmp >= cnt_4:
        memo[i] -= cnt_4 * 4
        cnt_4 = 0
        break

for i in memo:
    tmp = memo[i] // 2
    if tmp < cnt_2:
        memo[i] -= tmp * 2
        cnt_2 -= tmp
    elif tmp >= cnt_2:
        memo[i] -= cnt_2 * 2
        cnt_2 = 0
        break

for i in memo:
    tmp = memo[i]
    if tmp < cnt_1:
        memo[i] -= tmp * 1
        cnt_1 -= tmp
    elif tmp >= cnt_1:
        memo[i] -= cnt_1 * 1
        cnt_1 = 0
        break

if cnt_4 + cnt_2 + cnt_1 == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import Counter

H, W = map(int, input().split())

SS = []
for _  in range(H):
    for a in list(input()):
        SS.append(a)

S = Counter(SS)


cwh = 0
ok = True
corner = 0
for c in S.values():
    if c >= 4:
        corner += c // 4
        c = c % 4
    if c == 0:
        continue
    elif c == 3:
        if H % 2 == 1 and W % 2 == 1:
            cwh += 1
        else:
            ok = False
    elif c == 1:
        if H % 2 == 1 and W % 2 == 1:
            cwh += 1
        else:
            ok = False

if cwh >= 2 or not ok:
    ans = 'No'
else:
    ans = 'Yes'
    if corner < (W//2)*(H//2):
            ans = 'No'
    if H % 2 == 1 and W % 2 == 1:
        if cwh != 1:
            ans = 'No'
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    H, W = map(int, input().split())
    chars = []

    for _ in range(H):
        chars += list(input().strip())

    cnt = Counter(chars)

    if H % 2 == 0 and W % 2 == 0:
        for _, c in cnt.items():
            if c % 4 != 0:
                print('No')
                return
        print('Yes')
        return
    elif H % 2 == 0 or W % 2 == 0:
        twoCount = 0
        if H % 2 == 0:
            twoCount = H // 2
        else:
            twoCount = W // 2
        for _, c in cnt.items():
            if c % 4 == 0:
                continue
            if c % 2 == 0:
                twoCount -= 1
            else:
                print('No')
                return
        if twoCount >= 0:
            print('Yes')
        else:
            print('No')
        return
    else:
        oneCount = 0
        twoCount = H // 2 + W // 2
        for _, c in cnt.items():
            if c % 4 == 1:
                oneCount += 1
                continue
            if c % 4 == 3:
                oneCount += 1
                twoCount -= 1
                continue
            if c % 4 == 0:
                continue
            if c % 2 == 0:
                twoCount -= 1
                continue
            print('No')
            return
        if oneCount == 1 and twoCount >= 0:
            print('Yes')
        else:
            print('No')


sol()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#CODEFESTIVAL2017 qual A C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
s = [input() for _ in range(h)]
cnt = defaultdict(lambda : 0)
for i in range(h):
    for j in range(w):
        cnt[s[i][j]] += 1
g1,g2,g4 = (w%2)&(h%2),(w%2)*h//2 + (h%2)*w//2,h//2 * w//2
for k in cnt.keys():
    if (g1 > 0) and cnt[k] % 4 == 1 or cnt[k] % 4 == 3:
        g1 -= 1
        cnt[k] -= 1
    while (g4 > 0) and cnt[k] >= 4:
        g4 -= 1
        cnt[k] -= 4
    while (g2 > 0) and cnt[k] >= 2:
        g2 -= 1
        cnt[k] -= 2
for i,j in cnt.items():
    if j == 0:
        continue
    print('No')
    quit()
print('Yes')

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
alp = [0]*26
for i in range(H):
    for c in input():
        alp[ord(c)-97] += 1
m4 = [0]*4
for i in alp:
    m4[i%4] += 1
if m4[1]+m4[3] <= H%2*W%2 and m4[2] <= (H//2)*(W%2)+(W//2)*(H%2):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
	a.extend(list(input()))

from collections import Counter
a=Counter(a)
a=[i%4 for i in a.values()]
l=(h*(w%2)+w*(h%2)-(h*w)%2)
if sum(a)<=l:
	a=[i%2 for i in a]
if (h*w)%2==sum(a):
	print('Yes')
else:
	print('No')

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[input() for i in range(H)]
from collections import Counter
count=Counter(''.join(A))
c4,c2=0,0
for c in count.most_common():
    e=c[1]
    if e>=4:
        c4+=e//4
        e=e%4
    if e>=2:
        c2+=e//2
a=1
if (H//2)*(W//2)>c4:
    a=0
else:
    c2+=(c4-(H//2)*(W//2))*2
if (H%2)*(W//2)+(W%2)*(H//2)>c2:
    a=0
print(['No','Yes'][a])

Submission status: Accepted

Solution code:
from collections import Counter

H, W = map(int, input().split())
a = ''
for _ in range(H):
    a += input()

a_count = list(Counter(a).values())

H_odd = H % 2
W_odd = W % 2
ans = 'Yes'
if H_odd and W_odd:
    free_space = 1
    sym_space = H + W - 2
    for count in a_count:
        if count % 4 == 2:
            sym_space -= 2
        elif count % 4 == 1:
            free_space -= 1
        elif count % 4 == 3:
            sym_space -= 2
            free_space -= 1
        if sym_space < 0 or free_space < 0:
            ans = 'No'
            break
elif H_odd and not W_odd:
    sym_space = W
    for count in a_count:
        if count % 4 == 2:
            sym_space -= 2
        if count % 2 == 1:
            ans = 'No'
            break
        if sym_space < 0:
            ans = 'No'
            break
elif not H_odd and W_odd:
    sym_space = H
    for count in a_count:
        if count % 4 == 2:
            sym_space -= 2
        if count % 2 == 1:
            ans = 'No'
            break
        if sym_space < 0:
            ans = 'No'
            break
else:
    for count in a_count:
        if count % 4 != 0:
            ans = 'No'
            break

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())

D = {}

for i in range(H) :
    for s in input() :
        if s not in D :
            D[s] = 1
        else :
            D[s] += 1
cnt4 = 0
cnt2 = 0
for v in D.values() :
    d,r = divmod(v, 4)
    cnt4 += d
    cnt2 += 1 if r >= 2 else 0

cnt4 -= (W//2) * (H//2)

if cnt4 < 0 :
    ans = "No"
else :
    cnt2 += cnt4*2
    if H % 2 == 0 and W % 2 == 0 :
        ans = "Yes"
    elif H % 2 == 1 and W % 2 == 0 :
        if cnt2 >= W//2 :
            ans = "Yes"
        else :
            ans = "No"
    elif H % 2 == 0 and W % 2 == 1 :
        if cnt2 >= H//2 :
            ans = "Yes"
        else :
            ans = "No"
    else :
        if cnt2 >= H//2 + W//2 :
            ans = "Yes"
        else :
            ans = "No"
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

def judge(cnts, h, w):
    odd_cnt = 0
    mod4_2_cnt = 0
    mod4_0_cnt = 0

    for key, val in cnts.items():
        if val % 2 == 1:
            odd_cnt += 1

        elif val % 4 == 2:
            mod4_2_cnt += 1

        else:
            mod4_0_cnt += 1


    if h == 1 and w == 1:
        return True

    elif h == 1:
        if w % 2 == 1:
            return True if odd_cnt == 1 else False
        else:
            return True if odd_cnt == 0 else False

    elif w == 1:
        if h % 2 == 1:
            return True if odd_cnt == 1 else False
        else:
            return True if odd_cnt == 0 else False

    elif h % 2 == 1 and w % 2 == 1:
        return True if mod4_2_cnt == (w//2 + h//2) and odd_cnt == 1 else False

    elif h%2 == 1:
        return True if mod4_2_cnt == (w//2) and odd_cnt == 0 else False

    elif w%2 == 1:
        return True if mod4_2_cnt == (h//2) and odd_cnt == 0 else False

    else:
        return True if mod4_2_cnt == 0 and odd_cnt == 0 else False


h, w = li()
a = [ns() for _ in range(h)]

char_cnt = defaultdict(int)

for ai in a:
    for aij in ai:
        char_cnt[aij] += 1

print("Yes" if judge(char_cnt, h, w) else "No")

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = "".join(input() for _ in [0]*H)
n = {}
for s in S: n[s] = n.get(s,0)+1
c = [0]*2
for i in n.values():
    if i%2:c[0]+=1
    if i%4>1:c[1]+=1
if H%2 and W%2: ans = c[0]==1 and (c[1]<=(H+W-2)//2)
elif H%2: ans = c[0]==0 and (c[1]<=W//2)
elif W%2: ans = c[0]==0 and (c[1]<=H//2)
else: ans = c[0]==c[1]==0
print("Yes" if ans else "No")

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    space = {}
    space[1] = (H % 2) * (W % 2)
    space[2] = (H % 2) * (W//2*2) + (W % 2) * (H//2*2)
    space[4] = (H//2*2) * (W//2*2)
    cnt = Counter("".join(A))
    for alpha in cnt:
        c = cnt[alpha]
        for k in (4, 2, 1):
            while c//k >= 1 and space[k]:
                y = min(c//k*k, space[k])
                space[k] -= y
                c -= y
        if c:
            print("No")
            return
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
char={}
for _ in range(h):
  s=input()
  for c in s:
    if c not in char:
      char[c]=1
    else:
      char[c]+=1
cnt4=(h//2)*(w//2)
cnt2=0
cnt1=0
if h%2==1 and w%2==1:
  cnt1=1
  cnt2=h//2+w//2
elif h%2==1:
  cnt2=w//2
elif w%2==1:
  cnt2=h//2
flag=True
for _ in range(cnt4):
  for c in char.keys():
    if char[c]>=4:
      char[c]-=4
      if char[c]==0:
        del char[c]
      break
  else:
    flag=False
for _ in range(cnt2):
  for c in char.keys():
    if char[c]>=2:
      char[c]-=2
      if char[c]==0:
        del char[c]
      break
  else:
    flag=False
for _ in range(cnt1):
  for c in char.keys():
    if char[c]>=1:
      char[c]-=1
      if char[c]==0:
        del char[c]
      break
  else:
    flag=False
if flag==True:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=[['']*w for _ in range(h)]
char={}
for _ in range(h):
  s=input()
  for c in s:
    if c not in char:
      char[c]=1
    else:
      char[c]+=1
ch=h//2
cw=w//2
fh=False
fw=False
if h%2==1:
  ch+=1
  fh=True
if w%2==1:
  cw+=1
  fw=True
for i in range(ch):
  for j in range(cw):
    if (i==ch-1 and fh==True) and (j==cw-1 and fw==True):
      for c in char.keys():
        if char[c]%2==1:
          ans[i][j]=c
          char[c]-=1
          if char[c]==0:
            del char[c]
          break
    elif i==ch-1 and fh==True:
      for c in char.keys():
        if char[c]%4==2:
          ans[i][j]=c
          ans[i][w-j-1]=c
          char[c]-=2
          if char[c]==0:
            del char[c]
          break
      else:
        for c in char.keys():
          if char[c]>=2:
            ans[i][j]=c
            ans[i][w-j-1]=c
            char[c]-=2
            if char[c]==0:
              del char[c]
            break
    elif j==cw-1 and fw==True:
      for c in char.keys():
        if char[c]%4==2:
          ans[i][j]=c
          ans[h-i-1][j]=c
          char[c]-=2
          if char[c]==0:
            del char[c]
          break
      else:
        for c in char.keys():
          if char[c]>=2:
            ans[i][j]=c
            ans[h-i-1][j]=c
            char[c]-=2
            if char[c]==0:
              del char[c]
            break
    else:
      for c in char.keys():
        if char[c]>=4:
          ans[i][j]=c
          ans[i][w-j-1]=c
          ans[h-i-1][j]=c
          ans[h-i-1][w-j-1]=c
          char[c]-=4
          if char[c]==0:
            del char[c]
          break
fy=True
for i in range(ch):
  for j in range(cw):
    if ans[i][j]=='':
      fy=False
if fy==True:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
from collections import Counter
h,w=map(int,input().split())
s=[]
for i in range(h):
    s+=input()
c=sorted([j%4 for i,j in Counter(s).items()])[::-1]
c=Counter(c)
rh=h%2
rw=w%2
k=0
od=c[1]+c[3]
non4=c[2]+od
if rh*rw==1:
    if od!=1:
        k=1
    if c[1]+c[2]*2+c[3]*3>w+h-1:
        k=1
elif rh==0 and rw==0:
    if non4>0:
        k=1
elif rh==1:
    if od>0:
        k=1
    if c[2]*2>w:
        k=1
else:  # rw==1
    if od>0:
        k=1
    if c[2]*2>h:
        k=1
ans=['Yes','No']
print(ans[k])

Submission status: Accepted

Solution code:
h,w = map(int, input().split())

b = [0]*26

for i in range(h):
    a=input()
    for j in range(w):
        b[ord(a[j])-97]+=1

c = [0]*4
for i in range(len(b)):
    c[b[i] % 4] += 1

d = 1

if h%2==1 and w%2==1:
    if c[1]+c[3]!=1:
        d = 0
    elif c[2]+c[3]>h//2+w//2:
        d = 0
elif h%2==1:
    if c[1]+c[3]>0:
        d = 0
    elif c[2]>w//2:
        d = 0
elif w%2==1:
    if c[1]+c[3]>0:
        d = 0
    elif c[2]>h//2:
        d = 0
else:
    if c[1]+c[2]+c[3]>0:
        d = 0
print('Yes' if d else 'No')

Submission status: Accepted

Solution code:
from collections import Counter
h, w = [int(item) for item in input().split()]
cnt = Counter()
for i in range(h):
    cnt.update(input().rstrip())
odds = 0
two_mod4 = 0
for key in cnt.keys():
    if cnt[key] % 2 == 1:
        odds += 1
        if cnt[key] - 1 % 4 == 2:
            two_mod4 += 1
    else:
        if cnt[key] % 4 == 2:
            two_mod4 += 1

if w % 2 == 0 and h % 2 == 0:
    if odds > 0 or two_mod4 > 0:
        print("No")
    else:
        print("Yes")
elif w % 2 == 0:
    if odds > 0 or two_mod4 > w // 2:
        print("No")
    else:
        print("Yes")
elif h % 2 == 0:
    if odds > 0 or two_mod4 > h // 2:
        print("No")
    else:
        print("Yes")
else:
    if odds > 1 or two_mod4 > (h - 1) // 2 + (w - 1) // 2:
        print("No")
    else:
        print("Yes")

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
da = {}
for _ in range(h):
  a = input().strip()
  for _a in a:
    if _a in da:
      da[_a] += 1
    else:
      da[_a] = 1

if h%2==1 and w%2==1:
  oddc = 1
  div2 = w-1 + h-1
  div4 = h*w-1-div2
elif h%2==0 and w%2==0:
  oddc = 0
  div2 = 0
  div4 = h*w
elif h%2==1:
  oddc = 0
  div2 = w
  div4 = w*h-div2
else:
  oddc = 0
  div2 = h
  div4 = w*h - div2

for _, v in da.items():
  while v > 0:
    if v % 2 == 1:
      oddc -= 1
      v -= 1
    elif v % 4 == 0:
      div4 -= v
      v = 0
    else:
      div2 -= 2
      v -= 2

if h%2==1 and w%2==1 and div2>0 and div2%4==0:
  print('Yes')
elif h%2==1 and w%2==0 and div2>0 and div2%4==0:
  print('Yes')
elif h%2==0 and w%2==1 and div2>0 and div2%4==0:
  print('Yes')
elif oddc == 0 and div2 == 0 and div4 == 0:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
H,W= map(int,input().split())

li = [ input() for i in range(H) ]
from itertools import chain
li = list(chain.from_iterable(li))
import collections as col
cc = col.Counter(li)

flag = True
if ( H%2==0 and W%2==0 ):
  for k,v in cc.items():
    if (v%4!=0):
      flag = False
if ( H%2==1 and W%2==0 ):
  p=0
  for k,v in cc.items():
    if (v%4!=0):
      if (v%4!=2):
        flag = False
      else:
        p+=v%4
  if ( p > W ):
    flag = False
if ( H%2==0 and W%2==1 ):
  p=0
  for k,v in cc.items():
    if (v%4!=0):
      if (v%4!=2):
        flag = False
      else:
        p+=v%4
  if ( p > H ):
    flag = False
if ( H%2==1 and W%2==1 ):
  p=0
  q=0
  for k,v in cc.items():
    if (v%4==1):
      q += 1
    if (v%4==2):
      p += 2
    if (v%4==3):
      p += 2
      q += 1
  if ( q > 1 ):
    flag = False
  if ( p > (H//2 + W//2)*2 ):
    flag = False
print ( "Yes" if flag else "No" )

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())
As = collections.defaultdict(int)
for _ in range(H):
    for a in input():
        As[a] += 1
flag = True
if H%2 == 0 and W%2 == 0:
    for i in As.values():
        if i % 4 != 0:
            flag = False
            break
elif H%2 == 0:
    odd = 0
    for i in As.values():
        if i%2 == 1:
            odd += 1
    if odd:
        flag = False
    else:
        four = 0
        for i in As.values():
            four += i//4
        if four >= H*(W-1)//4:
            flag = True
        else:
            flag = False
elif W%2 == 0:
    odd = 0
    for i in As.values():
        if i%2 == 1:
            odd += 1
    if odd:
        flag = False
    else:
        four = 0
        for i in As.values():
            four += i//4
        if four >= W*(H-1)//4:
            flag = True
        else:
            flag = False
else:
    odd = 0
    even = 0
    for i in As.values():
        if i%2 == 0:
            even += 1
        else:
            odd += 1
    if odd >= 2:
        flag = False
    else:
        four = 0
        for i in As.values():
            four += i//4
        if four >= (H*W-(H+W-1))//4:
            flag = True
        else:
            flag = False
if flag:
    print('Yes')
else:
    print('No')