Problem:


Score : 600 points

Problem Statement

We have one slime.

You can set the health of this slime to any integer value of your choice.

A slime reproduces every second by spawning another slime that has strictly less health. You can freely choose the health of each new slime. The first reproduction of our slime will happen in one second.

Determine if it is possible to set the healths of our first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals a multiset S.

Here S is a multiset containing 2^N (possibly duplicated) integers: S_1,~S_2,~...,~S_{2^N}.

Constraints

All values in input are integers.

1 \leq N \leq 18

1 \leq S_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 ... S_{2^N}

Output

If it is possible to set the healths of the first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals S, print Yes; otherwise, print No.

Sample Input 1

2
4 2 3 1

Sample Output 1

Yes

We will show one way to make the multiset of the healths of the slimes that will exist in 2 seconds equal to S.

First, set the health of the first slime to 4.

By letting the first slime spawn a slime whose health is 3, the healths of the slimes that exist in 1 second can be 4,~3.

Then, by letting the first slime spawn a slime whose health is 2, and letting the second slime spawn a slime whose health is 1, the healths of the slimes that exist in 2 seconds can be 4,~3,~2,~1, which is equal to S as multisets.

Sample Input 2

2
1 2 3 1

Sample Output 2

Yes

S may contain multiple instances of the same integer.

Sample Input 3

1
1 1

Sample Output 3

No

Sample Input 4

5
4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3

Sample Output 4

No



Sample input:
2
4 2 3 1


Sample output:
Yes

Submission status: Runtime Error

Solution code:

import collections

N = int(input())
S = list(map(int, input().split()))

maxS = max(S)
tmp = []
for i in range(N):
    tmp.append((maxS-i, 2**i))
#print(tmp)

a = []
for i in range(len(tmp)):
    for j in range(tmp[i][1]):
        a.append(tmp[i][0])


c = collections.Counter(S)
c = sorted(c.items(), key=lambda x:x[0], reverse=True)
#print(c)

b = []
for i in range(len(tmp)):
    for j in range(c[i][1]):
        b.append(c[i][0])

#print(a)
#print(b)

ans = 'Yes'
if len(b) > len(a):
    ans = 'No'
else:
    

    for i in range(len(b)):
        if a[i] >= b[i]:
            pass
        else:
            ans = 'No'
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
from heapq import heappush, heappop


def solve(n, sss):
    keys = [-1] + sorted(sss.keys())
    m = keys.pop()
    if sss[m] != 1:
        return False
    k = keys[-1]
    q = [(-n, -m)]
    while k != -1:
        r, s = heappop(q)
        r = -r
        s = -s
        if r == 0:
            continue
        if k >= s:
            tmp = set()
            while q:
                tmp.add((-r, -s))
                r, s = heappop(q)
                r, s = -r, -s
                if k < s:
                    for item in tmp:
                        heappush(q, item)
                    break
            else:
                return False
        heappush(q, (-(r - 1), -k))
        heappush(q, (-(r - 1), -s))
        sss[k] -= 1
        if sss[k] == 0:
            keys.pop()
            k = keys[-1]
        # print(s, r, q, keys, sss)
    return True


n = int(input())
sss = Counter(map(int, input().split()))
print('Yes' if solve(n, sss) else 'No')

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
a = [int(i) for i in readline().split()]
a.sort(reverse=True)


from collections import deque

def check(i,x):
    c = i.bit_length()-1
    if x < res[i^(1<<c)]:
        return True
    return False

N = 1<<n
res = [0]*N
res[0] = a[0]

def dame(i):
    if not sub: return False
    c = i.bit_length()-1
    i ^= (1<<c)
    if i == sub[0]: return True
    else: return False


q = deque(range(1,N+1))
sub = deque()

for i,ai in enumerate(a):
#    print(q)
#    print(sub)
#    print(i,ai)
#    print(res)
    if i == 0: continue

    if sub and check(sub[0],ai):
        res[sub[0]]=ai
        sub.popleft()
    else:
        while q and not check(q[0],ai):
            ii = q.popleft()
            if dame(ii):
                print("No"); exit()
            sub.append(ii)
        ii = q.popleft()
#        print(ii,sub)
        if dame(ii):
            print("No"); exit()
        if ii == N: 
            print("No"); exit()
        res[ii] = ai
    
    
    
if q: print("Yes")
else: print("No")

Submission status: Runtime Error

Solution code:
import sys

if __name__ == '__main__':
    N = int(input())
    S = sorted(map(int, sys.stdin.readline().split()), reverse=True)
    used = [0] * (2**N)
    for i in range(N):
        n = 2 ** i
        for j in range(n):
            k = 0
            while not used[n+j+k] and S[j] > S[n+j+k]:
                k += 1
                if n + j + k > 2 ** N:
                    print('No')
            used[n+j+k] = 1

    print('Yes')

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
S = list(map(int, input().split()))

S.sort()

for i in range(N):
    m = int(2**(N-i-1))

    mm = int(2**(N-i-2))

    lm = m - mm - 1
    rm = m + mm

    if S[lm] == S[rm]:
        print('No')
        sys.exit()

    k = min(S[int(m+1):2*m])

    num0 = S[0:int(m)].count(k)
    num1 = S[int(m+1):2*m].count(k)

    if num0 > num1:
        print('No')
        sys.exit()

    del S[0:int(m)]

print('Yes')

Submission status: Runtime Error

Solution code:
n = int(input())
s = sorted(list(map(int, input().split())),reverse=True)
for i in range(1, n+1): 
  if len(set(s[:2**i])) <= i:
    if min(s[:2**i]) <= s[i+1]:
      print('No')
      exit()
print('Yes')

Submission status: Runtime Error

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
def gau(n):
    return (n-1)*(n-2)//2

def main():
    N = int(input())
    A = list(map(int,input().split()))
    from collections import defaultdict
    dic = defaultdict(int)
    for i in range(len(A)):
        dic[A[i]]+=1
    klis = sorted(dic.keys(),key=lambda x: -x)
    klis
    for i in len(klis):
        if i == 0 and dic[i] != 1:
            print("No")
            exit()
        elif dic[i] > N-(i-1):
            print("No")
            exit()
    print("Yes")
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

if __name__ == '__main__':
    N = int(input())
    S = sorted(map(int, sys.stdin.readline().split()), reverse=True)
    used = [0] * (2**N)
    for i in range(N):
        n = 2 ** i
        for j in range(n):
            k = 0
            while not used[n+j+k] and S[j] > S[n+j+k]:
                if n+j+k > 2**N:
                    print('No')
                k += 1
            used[n+j+k] = 1

    print('Yes')

Submission status: Runtime Error

Solution code:
n = int(input())
s = sorted(list(map(int, input().split())), reverse=True)
print(s)
string = "Yes"
for i in range(n):
    print(s[2**(i)-1], s[2**(i+1)-1], s[2**(i + 1) - 1], s[2**(i + 2) - 1])
    if s[n**(i)-1] > s[n**(i+1)-1] and s[n**(i + 1) - 1] > s[n**(i + 2) - 1]:
        string = "Yes"
    else:
        string = "No"
        break

print(string)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n =  I()
que = []
for i in LI():
    heappush(que, -i)



L = [heappop(que)]
for i in range(n):
    a = [i + 1 for i in L]
    for j in a:
        heappush(L, j)



heappop(L)
for i in range(n**2-1):
    if -heappop(L) < -heappop(que):
        print('No')
        break
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
import math

n = int(input())
S = list(map(int,input().split()))
ans = "Yes"
hp = max(S)
cnt = 0
current = 0
total = 0
for i in range(n):
    cnt = sum( i == hp for i in S)
    hp -= 1
    total += combination_count(n,i)
    if cnt  > total - current:
        ans = "No"
        break
    current = cnt
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
lists = [int(i) for i in input().split()]
"""
n = 5
lists =[1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8]"""
lists.sort(reverse=True)
#print("lists",lists)

listss = []
listssc = []

for i in range(2**5):
    if i == 0:
        listss.append(1)
    else:
        if lists[i] == lists[i-1]:
            listss.append(listss[i-1]+1)
            
        else:
            listss.append(1)
            listssc.append(listss[i-1])

listssc.append(listss[-1])


#print("listss",listss)
#print("listssc",listssc)

listssr = []
ssc_point = 0
for i in range(2**5):
    listssr.append(listssc[ssc_point]-listss[i])
    
    if listssc[ssc_point]-listss[i] == 0:
        ssc_point += 1
#print("listssr",listssr)

ans = "Yes"
tmpmin = 10**9
for i in range(n):
    tmplistmin = lists[2**i]
    if tmpmin==tmplistmin:
        ans = "No"
        break
    
    if i != 0:
        if tmpmin==lists[2**(i-1)+1]:
            if listss[2**(i-1)]<=listssr[2**(i-1)+1]:
                ans = "No"
                break
            
    tmpmin=tmplistmin

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = sorted(list(map(int, input().split(' '))))[::-1]

k = max(s)
num_index = [[0 for i in range(n + 1)] for i in range(k)]

for i in range(n + 1):
    num_index[0][i] = 1

for i in range(1, k):
    for j in range(1, n + 1):
        num_index[i][j] = num_index[i][j - 1] + num_index[i - 1][j - 1]

max_idx = [num_index[i][n] for i in range(k)]
ok = True
for i in range(k):
    maxs = max(s)
    max_now = s.count(maxs)
    if max_now > max_idx[i]:
        print('No')
        ok = False
        break
    #print(max_idx)
    if i < k - 1:
        max_idx[i + 1] += max_idx[i] - max_now
        s = [i for i in s if maxs != i]

if ok:
    print('Yes')

Submission status: Runtime Error

Solution code:
n = int(input())
s = sorted(list(map(int, input().split(' '))))[::-1]

k = max(s)
num_index = [[0 for i in range(n + 1)] for i in range(k)]

for i in range(n + 1):
    num_index[0][i] = 1

for i in range(1, k):
    for j in range(1, n + 1):
        num_index[i][j] = num_index[i][j - 1] + num_index[i - 1][j - 1]

max_idx = [num_index[i][n] for i in range(k)]

for i in range(k):
    maxs = max(s)
    max_now = s.count(maxs)
    if max_now > max_idx[i]:
        print('No')
    #print(max_idx)
    if i < k - 1:
        max_idx[i + 1] += max_idx[i] - max_now
        s = [i for i in s if maxs != i]

print('Yes')

Submission status: Runtime Error

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
used = [0] * (2 ** n)
used[0] = 1
s.sort(reverse=True)
a = 1
b = [s[0]]
for _ in range(n):
    c = b.copy()
    j = 0
    for i in b:
        while j < 2 ** n:
            if used[j] == 0 and s[j] < i:
                c.append(s[j])
                used[j] = 1
                break
            j += 1
        if j >= 2 ** n:
            print("No")
            exit()
    b = sorted(c, reverse=True)

print("Yes")

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
s=[int(i) for i in input().split()]

count=Counter(s)
count=sorted(count.items(),reverse=True)


ans='Yes'
for i in range(len(count)):
    check-=count[i][1]
    if count[i][1]>n-i+1:
        ans='No'
        break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
S = list(map(int,input().split()))

npS = np.array(sorted(S,reverse = True))

print(npS)
ans = True
if (npS[0]-npS[1]) <= 0:
    ans = False
if N>=2:
    for i in range(1,N):
        # print(npS[0:2**i],npS[2**i:2**(i*1)],npS[0:2**i]-npS[2**i:2**(i*1)])
        if min(npS[0:2**i]-npS[2**i:2**(i*1)]) <= 0:
            ans = False
            break

if ans == True:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:


N = int(input())
a = list(map(int,input().split(' ')))
a.sort(reverse=True)

before = 0
flg = True
for i in range(N + 1):
    index = 2**i - 1
    what = a[index]
    
    ab = a[0:index]
    how_many = bisect.bisect_right(ab, what) - bisect.bisect_left(ab, what)
    if  how_many > index/2:
        flg = False
    else:
        pass
  
if flg:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
n = int(input())
s = np.array(list(map(int, input().split())), dtype="int32")
s.sort()  # O(n*2^n)
flag = False
for i in range(n):
    for j in range(2 ** i):
        if s[-1 - j] <= s[-1 - 2 ** i - j]:
            flag = True
        if flag:
            break
    if flag:
        break
if flag:
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
S=[int(i) for i in input().split()]
SS=collections.Counter(S)
SK=sorted(list(SS.keys()))

  
n_max=20
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))
def comb(x,y):
  return (F[x]//F[y]//F[x-y])

SK=SK[::-1]
tot=0
cur=0
room=0
chk=True
for sk in SK:
  tot+=SS[sk]
  room+=comb(n,cur)
  if tot>room:
    chk=False
  cur+=1
print("Yes" if chk==True else "No")

Submission status: Runtime Error

Solution code:
n = int(input())
list_s = list(map(int, input().split()))

maxIndex = [i for i, x in enumerate(a) if x == max(a)]
if len(maxIndex) > 1:
  print("No")
else:
  print("Yes")

Submission status: Runtime Error

Solution code:
n = int(input())
k = [int(i) for i in input().split()]
d = collections.Counter(k)
od = collections.OrderedDict(sorted(d.items(), reverse=True))

current = 0
gf = True
for i in od.keys():
    if od[i] > 2**current:
        gf = False
    current += 1
if gf:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
S=[int(i) for i in input().split()]
SS=collections.Counter(S)
SK=sorted(list(SS.keys()))
SSS=collections.defaultdict(int)
cur=1
for sk in SK:
  SSS[cur]+=SS[sk]
  cur+=1
  
n_max=20
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))
def comb(x,y):
  return (F[x]//F[y]//F[x-y])

SK=SK[::-1]
tot=0
cur=0
room=0
chk=True
for sk in SK:
  tot+=SSS[sk]
  room+=comb(n,cur)
  if tot>room:
    chk=False
  cur+=1
print("Yes" if chk==True else "No")

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
b = [a[i] for i in sorted(a.keys(), reverse=True)] 

for i in range(1,n):
    cnt = b.pop()
    tmp = 0
    while b and cnt + tmp < 2**i:
        cnt += tmp
        tmp = b.pop()
    if cnt + tmp > 2**i and cnt <= tmp - (2**i - cnt):
        print('No')
        break
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(map(int, input().split(" ")))
# n = 18
# s = list(reversed(range(1, 262145)))

s = sorted(s, reverse=True)
from collections import deque

# def merge(x, y):

#     i = 0
#     j = 0

#     new = []
#     k = 0
#     l = 0
#     while k < len(x):
#         if x[k] > y[l]:
#             k += 1
#             l += 1
#         else:
#             print("No")
#             exit(0)

#         if x[i] > y[j]:
#             new.append(x[i])
#             i += 1
#         else:
#             new.append(y[j])
#             j += 1

#     new.extend(x[i:])
#     new.extend(y[j:])
#     return new

def solve():
    Q = deque()
    Q.appendleft((s[0], 0))
    s.pop(0)
    while s:
        x, j = Q.pop()
        for i in range(j, n):
            if x > s[0]:
                Q.appendleft((s[0], j + 1))
                s.pop(0)
            else:
                print("No")
                exit(0)
    print("Yes")
solve()
# slimes = [s[0]]
# s = s[1:]
# for i in range(n):
#     newslimes = []
#     m = len(slimes)
#     slimes = merge(slimes, s[:m])
#     print(slimes)
#     s = s[m:]
#     # print(len(slimes), len(s))

# print("Yes")

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
b = [a[i] for i in sorted(a.keys(), reverse=True)] 

for i in range(1,n):
    cnt = b.pop()
    tmp = 0
    while cnt + tmp < 2**i:
        cnt += tmp
        tmp = b.pop()
    if cnt + tmp > 2**i and cnt < tmp - (2**i - cnt):
        print('No')
        break
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    n = int(input())
    s = list(map(int, input().split()))

    s.sort(reverse=True)

    x = 2

    if s[0] > s[1]:

        for i in range(n):
            a = s[0: x]
            b = s[x:x*2]

            for y in range(x):
                if a[y] > b[y]:
                    pass
                else:
                    print('No')
                    sys.exit()

        x = x * 2

    else:
        print('No')
        sys.exit()

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

    
if __name__ == '__main__':
    N = int(input())
    S = InputToInt()
    S.sort(reverse=True)

    if S[0] == S[1]:
        print('No')
        sys.exit()
    
    for i in range(1, N):
        for j in range(2**(i-1)):
            if S[2**i+j-1] > S[2**i*2+j-1]:
                pass
            else:
                print('No')
                sys.exit()
    print('Yes')

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(int, input().split()))
        
S.sort(reverse = 1)
father = S[0]
if S[2**(N-1)+1] >= father - 1:
  print("No")
else:
  print("Yes")

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
a.sort(reverse=True)

for d in range(n):
    for i in range(1<<d):
        if a[i] <= a[i+(1<<i)]:
            print("No")
            sys.exit(0)
print("Yes")