Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Is the following solution for this greedy problem correct?

Revision en2, by xuanquang1999, 2017-03-26 20:01:40

One of my friend recently asked me the following problem:

"Given an array a 1, a 2, ..., a n and a number K ( n ≤ 105, a i ≤ 109). Is there a way split the array into K disjoint sub-arrays (don't have to be contiguous) such that sum of each sub-array is equal to each other (and equal to )?"

My teacher came up with the following greedy solution: for each sub-array, keep choosing the maximum number such that sum of sub-array with that number is still smaller or equal to S. When it's impossible to add more number from a to this sub-array, check if the current sum is equal to S.

However, both my teacher and me are unable to neither prove the correctness of the solution nor find a counter-example for it. Is this greedy solution always optimal? How to prove (or disprove) it? Thanks in advance.


  Rev. Lang. By When Δ Comment
en2 English xuanquang1999 2017-03-26 20:01:40 12 Tiny change: 'r $K$ ($n <= 10^5$, $a_i <= 10^9$). I' -> 'r $K$ ($n \leq 10^5$, $a_i \leq 10^9$). I'
en1 English xuanquang1999 2017-03-26 20:01:07 898 Initial revision (published)