Блог

Я участвую в Google Code jam. Прежде всего я хочу сказать, что я не хочу, чтобы кто-либо решал мне задачу «на победу» или что-то в этом роде. Мне просто нужна помощь, чтобы понять проблему, которую я не смог решить в уже завершившемся раунде.

Вот ссылка на проблему, называемую разделением конфет. Я не буду объяснять это здесь, потому что это nosense, я не смогу объяснить это лучше, чем Google.

Я хотел бы знать какое-нибудь «хорошее» решение проблемы, например, я скачал первое решение на английском языке и увидел, что в коде всего 30 строк!!! Это потрясающе! (Любой может скачать ее, поэтому я думаю, что нет проблем с тем, чтобы сказать это: решение theycallhimtom отсюда). Я не могу понять решение, даже просматривая код. (Мое незнание Java не помогает.)

Спасибо!

Сами Google предоставляют обсуждения проблем и решения

Смотрите эту ссылку для решения проблемы разделения конфет:http://code.google.com/codejam/contest/dashboard?c=975485#s=aamp;a=2

В принципе, конфеты можно разделить на две стопки одинакового значения (с точки зрения Патрика), если

 C[0] xor C[1] xor C[2] xor ... xor C[N] == 0.
  

Одним из таких разделений является сумма всех значений candy, кроме одного. Чтобы максимизировать ценность одной стопки, возьмите конфету с наименьшей стоимостью и положите ее в отдельную стопку.

Почему это так?

Я думал об этом так, что по определению добавление Патрика фактически равно значениям xoring. Исходя из определения проблемы, мы хотим

 C[i] xor C[j] xor ... xor C[k] == C[x] xor C[y] xor ... xor C[z]
  

для некоторых элементов с каждой стороны.

Добавление RHS как к LHS, так и к RHS приводит

 C[i] xor C[j] xor ... xor C[k] xor C[x] xor C[y] xor ... xor C[z] == 0
  

Поскольку преобразование значения в xor само по себе дает 0, а порядок операций xor не важен, значение RHS становится равным 0.

Любой из элементов в LHS можно переместить в правую часть, и равенство останется в силе. Выбор элемента с наименьшим значением обеспечивает наилучшее разделение между стопками.