# CHEFSETC - Editorial

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

CAKEWALK

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:

When will DEC16’s editorials will be posted?

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

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

i dont understand what a bitmask is…