alibi's blog

Help me! (timus problem)
By alibi, history, 8 years ago, In English

Here is a link for the problem.

I found an approach in discussion: "You have to divide the participants into equal teams (rounded)", but I cannot understand why it's correct!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

In this problem you need to divide them into M teams, so you need to find an array a[1..M] such that its sum is N and its product is maximized.

Okay, suppose there is an optimal sequence of a[] such that there are two elements with difference greater than 1. Then, product is P * X * Y (X + 1 < Y), where P is product of other elements, while X and Y are these two elements with difference greater than 1 (X + 1 < Y).

Now, let's make X++ and Y-- and see what happens. Product becomes P * (X + 1) * (Y — 1) = P * X * Y + P * Y — P * X — P = P * X * Y + P * (Y — X — 1), we know that (Y > X + 1), thus Y — X — 1 at least 1, so answer becomes better.

→ Reply