CHEFSETC - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Misha Chorniy
Tester: Tuan Anh Tran Dang
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Tuan Anh Tran Dang

DIFFICULTY

CAKEWALK

PREREQUISITE

NONE

PROBLEM

Given 4 distinct numbers check if there is exist a sub-set of numbers with sum equals zero.

SOLUTION

4 is small enough for us to just consider all possible sub-sets. I think most of the contestant will choose bitmask to implement the solution. Each sub-set can be represented by a 4-bit number where each bit 1 corresponding to a number that is chosen. You can refer to the pseudo code below:

    result = "No"
    for s 1 -> 15:
        sum = 0;
        for i 0 -> 3
            if bit ith of s is 1 then sum += a[i]
        if sum = 0:
            result = "Yes";
            break;

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

2

When will DEC16’s editorials will be posted?

3

Can a bitmask be used if there was more than 4 elements ?

4

i dont understand what a bitmask is…
please explain further

5

if there were n elements, the number of subsets is 2^n. Bitmask can be used if 2^n is small enough. Modern computers can calculate up to 10^8 iterations per second. So usually, if n \leq 24 it’s practical since 2^{24} \approx 10^7 iterations

1 Like
6

Bit masking implementation in python. It is the same logic. zfill(4) is used to make all binary numbers of length 4. e.g 1 = 0001 and 13 = 1101.
Since bin() gives a mask like ‘0b0001’ I sliced it.
Now simply check if the bit is 1. choose that from list and add to sum. Just check if any one sum is zero.

# cook your dish here
t = int(input())
while(t > 0):
    fg = 0
    l = list(map(int, input().split()))
    for i in range(1, 16):
        binary_mask = bin(i)[2:].zfill(4)
        sum_= 0
        for nu, ms in zip(l, binary_mask):
            if(ms == '1'):
                sum_ += nu
        
        if(sum_ == 0):
            fg = 1
            break
    
    if(fg == 1):
        print("Yes")
    else:
        print("No")
    t -= 1
7

thing to keep in mind is — outer loop iterations * inner loop <= 10 ^ 7 or 10 ^ 8 …
bcoz that many instruction could be executed in 1 second …
for upper bound
inner iteration at max = … n
outer iteration at max = … 2^n
so statement becomes = n * ( 2 ^ n ) <= 10 ^ 7 …ie n <= 19 it’ll work extremely fine …