Блог пользователя jetbeans

Need help for a problem from ONTAK2014
Автор jetbeans, 10 лет назад, По-английски

This is a problem from ONTAK 2014 and you can find the polish statment here Sumy.

You are given a sequence A = {a1, a2, ..., an}, every element in A is different.

You should construct another sequence B = {b1, b2, ..., bm} which meets the following conditions:

  1. m ≤ n
  2. sum of all elements in each subset (there are 2k subset in total) of B should be different
  3. every element in A can be represented as sum of some elements of B

n ≤ 21, 1 ≤ ai ≤ 1017

can someone provide some ideas?

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I suggest asking Swistakk (by PM or something) — it was his problem. Sadly, I do not remember the solution, but what I do remember is that the problem was really cool (and hard :)).

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

:>. Indeed nice problem, though I have to admit that it wasn't fully mine, I've just adapted math version of that problem to an algorithmic one.

One can firstly think of some criterion which will imply that all sums of subsets are different. I suggest you thinking about it in terms of binary expressions.

→ Ответить