ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1005. Куча камней

WA( I not underdstand why)
Послано ZiDo 17 сен 2012 20:39
[code deleted]

Edited by moderator 29.01.2022 19:44
Re: WA( I not underdstand why)
Послано Bogatyr 18 сен 2012 13:36
The short explanation is that the greedy algorithm is wrong.   A simple example: it always places the largest and 2nd largest stones in different piles.   Understanding this, it's not hard to come up with input that fails, e.g.,:
5
4 6 6 7 9
(sum of the largest and next largest stones = sum of remaining smaller stones)

Optimization problems like this generally require that all combinations be examined.  Either in brute force generate and test, or smarter "try all" schemes like recursion with backtracking (and memo-ization) or dynamic programming, to reduce redundant work.
Re: WA( I not underdstand why)
Послано gogreen 27 мар 2013 13:21
Hello,
Thanks a lot. I was searching for a test case which would fail the greedy algorithm. But still donot understand why the greedy algorithm fails. I am a begineer to algorithms. Could you just explain.

with regards
gogreen.
Re: WA( I not underdstand why)
Послано Lars Chung 22 май 2013 07:29
Hi,

I was using greedy algorithm and found out the flaw. Because there are 2 buckets, and you put one stone after another (this is the major flaw), regardless of its way to keep it minimum difference, there is still a possibility that the combination is not the optimal solution.

For example, I believe that 1,1,1,3 would cause problem. The first step, 1 on bucket1, second step, 1 on bucket2. This equals to the difference to be 0. Third step, 1 on bucket1 or bucket2, fourth step, 3 on opposite of what you did in third step,

However, as you can see the most optimal solution is 1,1,1 in bucket1, 3 in bucket2. Greedy would work if the number of stones on both buckets are equal or have difference of 1 (due to odd numbers).

Edited by author 22.05.2013 07:30