Discount aux Galeries Lafayette and NP-completeness

Finally, the discount I love most, duovigintuple points, is back aux Galeries Lafayette Xidan (Beijing). I decided bien en profiter, treating myself with some CHANEL products.

Simple rules here:

1. For each yuan spent on cosmetics, 22 points are rewarded to your account after the payment. Only whole yuan produces points.
2. Every 100 points count as 1 yuan for payment. Only multiples of 100 points can be redeemed for payment.

Important hints:

1. You cannot spend points earned by a purchase on the purchase itself.
2. You cannot cash points, which makes points less valuable than cash.

I planned to buy the following things:

Suppose initially I have no points in my account, a good sequence of purchases is:

• 1 soap, 1 gel, 1 foam and 1 serum;
• 1 soap.

The first purchase costs 2205 yuan, and produces 48510 points. The second purchase costs 0 yuan and 48000 points. At last, I have 510 points in my account.

The sequence is by no means guaranteed to be optimal, as I just used some heuristics: the nominal price is 2685 yuan, and the perfect price is 2685÷(1+22%)≈2200.82 yuan, where the reduction is 484.18 yuan, near to the price of soap.

If everything had happened as planned, this wouldn’t be interesting. The soap is out of stock. It is, in fact, limited, and most major CHANEL cosmetics stores are out of stock of it. Neither is the product available from its official website in China. Using again the heuristics, I found a good sequence for the modified order: first the foam and the serum, then the gel.

Formalisation

On a first thought, a generalised version of finding the best sequence of purchases should be intractable, as many other notoriously hard combinatorial optimisation problems. Let’s formulate the problem formally and prove its intractability.

Problem OPT-DISCOUNT Given $n+2$ natural numbers $I,m,w_1,...,w_n$ where $1\leq m\leq n$, let $I$ be the initial amount of points. Find a partition $X_1,...,X_m$ of $\left\{{1,...,n}\right\}$ along with $m$ numbers $p_1,...,p_m$ that minimises the output of the following program:

1. Set $P\leftarrow 0$ and use the initial value of $I$.
2. For $i=1,...,m$:
   1. Set $x=-p_i+\sum_{j\in X_i}{w_j}$.
   2. If $I<100p_i$ or $x<0$, set $P\leftarrow +\infty$ and terminate the loop.
   3. Otherwise, set $P\leftarrow P+x$ and $I\leftarrow I-100p_i+22x$.
3. Output $P$.

Here $m$ models the maximum number of payments one can stand to make. Splitting the order takes more effort when paying! The decision version of the above problem is:

Problem DISCOUNT Given $n+3$ natural numbers $I,m,w_1,...,w_n,Q$, decide whether the minimised value in OPT-DISCOUNT is no greater than $Q$.

Anyone with basic computer science knowledge (稍有常识的人) will immediately see that DISCOUNT is NP-complete. Let’s prove its NP-hardness.

Problem SUBSET-SUM-22-100 Given $n$ natural numbers $x_1,...,x_n$, decide whether there exists $B\subseteq\left\{{1,...,n}\right\}$ such that $122\sum_{i\in B}{x_i}=100\sum{x_i}$.

Lemma SUBSET-SUM-22-100 is NP-hard.

Proof Let $x_1,...,x_n$ be a regular subset sum problem (asking whether there exists a subset that sums to half of the total sum) and suppose WLoG that $x_1\neq 0$, put $y_i=22x_i$ for $i=1,...,n$ and $y_{n+1}=39\sum{x_i}$ and form a SUBSET-SUM-22-100 instance with $y$.

• If the SUBSET-SUM instance has a solution $B$, one possible solution to the SUBSET-SUM-22-100 instance is $B\cup\left\{{n+1}\right\}$.
• If the SUBSET-SUM-22-100 instance has a solution $B'$, it must be the case that ${n+1}\in B'$, because the sum without $y_{n+1}$ would be too small. Now one can easily verify that $B'\setminus\left\{{n+1}\right\}$ is a solution to the SUBSET-SUM instance.

Corollary DISCOUNT is NP-hard.

Proof A portion of DISCOUNT, namely that restricted to $m=2,I=0,Q=\frac{100}{122}\sum{x_i}$, is exactly SUMSET-SUM-22-100, excluding those whose $Q$ is not an integer thus the answer is immediate.

Real-world scenarios

For real-world scenarios, $m=3$ seems to be enough for a super-near-optimum. The strategy is:

1. Make a big purchase below the ‘perfect price’ (nominal price divided by 1.22) without redeeming points.
2. Make a small purchase, the nominal price of which plus the previous one exceeds the ‘perfect price’, redeeming a carefully-chosen amount of points so that the cash paid on the first two purchases is the ‘perfect price’.
3. Make a final purchase, redeeming as many points as possible and paying the residual amount.

By the way, the formalised model does not take the value of points into account. A returning customer surely benefits from the points left in the account.