Discount aux Galeries Lafayette and NP-completeness

Hero image: Gifts to Myself
Hero image: Gifts to Myself

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:

Product Price per piece (yuan) Quantity
soap 480 2
shower gel 330 1
foam cleanser 505 1
blue serum 890 1

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 intersting. 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+2n+2 natural numbers I,m,w1,...,wnI,m,w_1,...,w_n where 1mn1\leq m\leq n, let II be the initial amount of points. Find a partition X1,...,XmX_1,...,X_m of {1,...,n}\left\{{1,...,n}\right\} along with mm numbers p1,...,pmp_1,...,p_m that minimises the output of the following program:

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

Here mm 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+3n+3 natural numbers I,m,w1,...,wn,QI,m,w_1,...,w_n,Q, decide whether the minimised value in OPT-DISCOUNT is no greater than QQ.

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 nn natural numbers x1,...,xnx_1,...,x_n, decide whether there exists B{1,...,n}B\subseteq\left\{{1,...,n}\right\} such that 122iBxi=100xi122\sum_{i\in B}{x_i}=100\sum{x_i}.

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

Proof Let x1,...,xnx_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 x10x_1\neq 0, put yi=22xiy_i=22x_i for i=1,...,ni=1,...,n and yn+1=39xiy_{n+1}=39\sum{x_i} and form a SUBSET-SUM-22-100 instance with yy.

  • If the SUBSET-SUM instance has a solution BB, one possible solution to the SUBSET-SUM-22-100 instance is B{n+1}B\cup\left\{{n+1}\right\}.
  • If the SUBSET-SUM-22-100 instance has a solution BB', it must be the case that n+1B{n+1}\in B', because the sum without yn+1y_{n+1} would be too small. Now one can easily verify that B{n+1}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=100122xim=2,I=0,Q=\frac{100}{122}\sum{x_i}, is exactly SUMSET-SUM-22-100, excluding those whose QQ is not an integer thus the answer is immediate.

Real-world scenarios

For real-world scenarios, m=3m=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.

Please enable JavaScript to view the comments powered by Disqus.