morozec / holahaggling

Hola haggling programming challenge. 1st place in 1st round

Ключевая идея решения - определить цену каждого товара для соперника (или максимально снизить число возможных вариантов таких цен).

Цена товаров соперника определяется на основе следующих факторов:

• Предложения, сделанные соперником. Предполагается, что соперник:
  • не будет запрашивать товары, которые не имеют для него ценности;
  • будет постепенно снижать суммарную стоимость своего предложения;
  • при снижении стоимости своего предложения будет отказываться в первую очередь от тех товаров, которые имеют для него меньшую цену. Особняком стоит рассмотреть случай, когда товар не имеет ценности для меня. Умный соперник, определив это, не будет снижать свой запрос на этот товар.
• Предложения, сделанные мной. Предполагается, что соперник не будет выдвигать предложение, которое имеет для него стоимость, не превышающую стоимость моего предложения на предыдущем шаге.

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

Торговля первым игроком ведется более агрессивно (жадно), поскольку на последнем шаге он может выдвинуть практически любое предложение, с которым сопернику, вероятно, придется согласиться, чтобы не остаться вообще с нулем.