Можно понять что ограничение 500 на самом деле это просто запутывание. В массиве можно оставить только 46 наименьших а дальше meet-in-the-middle.

Просто генерируем рэндомный вектор из 10 чисел из набора и так до тех пор, пока не найдем две одинаковые суммы. Я зафейлил эту задачу, считывал числа как int :) Но, когда заметил — оутпут на large генерирует где-то за полторы минуты.

У меня зашла такая байда: генерим около 10^7 рандомных подмножеств из первых 250 чисел и запихиваем полученные суммы в хэш-таблицу. Потом рандомно выбираем подмножества из других 250 чисел, пока не найдем с какой нить суммой, что есть в хэш-таблице.

Ну, какой нить механизм восстановления подмножеств по сумме придумать не сложно. Я, например, сохранял 40000 случайных перестановок в массивчиках, а в хэш-таблицу складывал суммы по всем префиксам вместе с номером перестановки.

Оно искало ответы чуть больше 5 минут.

Я делал так: возьмём два простых числа p и q, p чуть меньше 2^20, q чуть меньше 2^25. Разобьём исходный массив на 25, по 20 элементов в каждом. В каждом таком маленьком массиве найдутся две одинаковые суммы по модулю p. Получаем массив из 25 пар. Посмотрим теперь на них по модулю q. Посчитаем 2^25 сумм (из каждой пары берём одно число). Получим две одинаковые по модулю q. Ясно, что эти суммы совпадают по модулю pq. pq несколько меньше, чем 500 * 10^12, но и этого хватает.

А я генерировал в порядке возрастания все возможные суммы и ждал пока повториться хоть одна — за минуту все 10 тестов успело сделать :)

Моё решение (см. комментарий ниже) отработало меньше чем за секунду.

Я тоже довольно долго думал над этой задачей, и в итоге пришел к решению. Понятно, что из 48 чисел есть 2^48 возможных подмножеств, а их максимальная сумма 48*10^12 т.е. подмножеств в несколько раз больше(в 5.6 раз), чем максимальная сумма. Я рандомно перемешал массив, для первых 24 чисел сгенерил всевозможные маски, посортил по сумме пары (сумма, маска), для чисел с 25-ое по 48-ое проделал тоже самое. теперь генерим случайно два индекса в обоих массивах, и пытаемся двумя указателями найти эту сумму в массивах, если нашли и индексы не совпали, то мы молодцы, иначе снова генерим индексы. Такое решение у меня зафейлилось на чем-то, я успел отдебажить и закончить тесты до окончания времени, время работы было около минуты, у меня 4гб оперативы на ноуте, прога должна была жрать около гига, но все влезло. Интересно было почитать другие варианты решений, потому привёл свой.

может залазил туда, где нельзя залезть(типа места мало, но сильно выше уровня моря). А вообще проще было это тудаже внутрь дейкстры пихнуть

Потому что там время перехода может зависеть от глубины. Кроме того, для каждого перехода нужно вычислять момент времени, когда по нему можно начинать идти. Обход в ширину не умеет решать такую задачу. Я думаю, что простейшее решение всё-таки будет с Дейкстрой.

Просто добавь воды зайди в контест

http://code.google.com/codejam/contests.html

Мне сейчас вспомнилось Ваше решение задачи про разбиение гиперпространства гиперплоскостью (Петрозаводск, контест MIT). Как у Вас получается постоянно придумывать решения из серии "а оно ведь работает"?

Отправил не тот исходник на маленькую задачу и вовремя об этом сообщил.