Lost Permutation (Codeforces 1759B)
Tags: Math, math

A sequence of $$$n$$$ numbers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once. For example, the sequences [$$$3, 1, 4, 2$$$], [$$$1$$$] and [$$$2,1$$$] are permutations, but [$$$1,2,1$$$], [$$$0,1$$$] and [$$$1,3,4$$$] — are not.Polycarp lost his favorite permutation and found only some of its elements — the numbers $$$b_1, b_2, \dots b_m$$$. He is sure that the sum of the lost elements equals $$$s$$$.Determine whether one or more numbers can be appended to the given sequence $$$b_1, b_2, \dots b_m$$$ such that the sum of the added numbers equals $$$s$$$, and the resulting new array is a permutation?

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) —the number of test cases. Then the descriptions of the test cases follow.The first line of each test set contains two integers $$$m$$$ and $$$s$$$ ($$$1 \le m \le 50$$$, $$$1 \le s \le 1000$$$)—-the number of found elements and the sum of forgotten numbers.The second line of each test set contains $$$m$$$ different integers $$$b_1, b_2 \dots b_m$$$ ($$$1 \le b_i \le 50$$$) — the elements Polycarp managed to find.

Output: Print $$$t$$$ lines, each of which is the answer to the corresponding test set. Print as the answer YES if you can append several elements to the array $$$b$$$, that their sum equals $$$s$$$ and the result will be a permutation. Output NO otherwise.You can output the answer in any case (for example, yEs, yes, Yes and YES will be recognized as positive answer).

Note: In the test case of the example, $$$m=3, s=13, b=[3,1,4]$$$. You can append to $$$b$$$ the numbers $$$6,2,5$$$, the sum of which is $$$6+2+5=13$$$. Note that the final array will become $$$[3,1,4,6,2,5]$$$, which is a permutation.In the second test case of the example, $$$m=1, s=1, b=[1]$$$. You cannot append one or more numbers to $$$[1]$$$ such that their sum equals $$$1$$$ and the result is a permutation.In the third test case of the example, $$$m=3, s=3, b=[1,4,2]$$$. You can append the number $$$3$$$ to $$$b$$$. Note that the resulting array will be $$$[1,4,2,3]$$$, which is a permutation.

Sample Inputs:
5
3 13
3 1 4
1 1
1
3 3
1 4 2
2 1
4 3
5 6
1 2 3 4 5

Sample Outputs:
YES
NO
YES
NO
YES

Solution (Python):
def i():
    (n, c) = map(int, input().split())
    s = list(map(int, input().split()))
    mm = max(s)
    tp = set([x for x in range(1, mm + 1)]) ^ set(s)
    c -= sum(list(tp))
    if c < 0:
        return 'NO'
    else:
        mm += 1
        while c >= mm:
            c -= mm
            mm += 1
        if c == 0:
            return 'YES'
        return 'NO'
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
import math

def ps(x):
    if x >= 0:
        sr = int(math.sqrt(x))
        return sr * sr == x
    return False
for _ in range(int(input())):
    (m, s) = map(int, input().split())
    arr = list(map(int, input().split()))
    ss = sum(arr) + s
    maxi = max(arr)
    ss = 8 * ss + 1
    if ps(ss):
        n = (int(math.sqrt(ss)) - 1) // 2
        if n < maxi:
            print('NO')
        else:
            print('YES')
    else:
        print('NO')

Solution (Python):
R = lambda : map(int, input().split())
(t,) = R()
while t:
    t -= 1
    (m, s) = R()
    b = (*R(),)
    i = 0
    while s > 0 or i < max(b):
        i += 1
        s -= (i not in b) * i
    print('YNEOS'[s < 0::2])