UVa 11236: Grocery Store is an unusual problem for UVa Online Judge: it takes no input! There’s just a problem statement explaining the rules for finding the output. The lack of input and the mathematical nature of the problem reminds me of the problems on Project Euler. And as with Project Euler, you could cheat the time limit by calculating the output offline and just having your program print it. But if you would rather write a program to solve this problem quickly, keep reading for ideas.
The Grocery Store Problem
The core of the problem statement is straightforward if you remove the extraneous details:
Find all unique combinations of four prices where the sum of the prices is equal to their product. A price is a floating-point value with exactly two digits after the decimal, in the range €0.01 to €20.00.
In uHunt, this problem is in the section called Complete Search: Iterative (Three or More Nested Loops, Harder). The “Harder” indicator is a hint that we won’t be able to search the entire solution space.
The definition of price in this problem means there are 2000 distinct possible values for each price. Searching all permutations of those values for all four prices would take $2000^4 = 1.6 \times 10^{13}$ iterations. That’s too many iterations to finish in any amount time I want to wait, never mind the three seconds UVA OJ allows for this problem.
Units and Data Types
I’m going to describe a few optimizations that will collectively make your solution run fast. But first, let’s talk about units and data types. The real-world data type used by the problem statement is euros and cents. The simplest way to translate this real-world type to a programming language type is to use double or float. However, using floating-point types isn’t always the best choice. In this problem, we’re comparing a sum of floating-point values to a product of floating-point values. The product introduces rounding error that affects the answer. To avoid any rounding problems, I decided to do all of my calculations in cents (hundredths of a euro).
If you choose to store values as cents rather than euros, you have to think carefully about comparisons. Comparing sums of cents with products of cents is not equivalent to comparing sums of euros with products of euros. To see why, consider the four prices $\lbrace{e_1, e_2, e_3, e_4}\rbrace$ in euros. If $e_1+e_2+e_3+e_4 = e_1e_2e_3e_4$, then ${e_1, e_2, e_3, e_4}$ is a solution for this problem. Now let’s convert each price $e_i$ from euros to cents: $p_i = {100e_i}$ is the price value we’ll use in the solution code. Here’s the solution we want:
$$ e_1+e_2+e_3+e_4 = e_1e_2e_3e_4 $$
If we convert each $e_i$ value to cents and represent it as $p_i$, this is equivalent to:
$$ \frac{p_1}{100} + \frac{p_2}{100} +\frac{p_2}{100} +\frac{p_2}{100} = \frac{p_1}{100}\frac{p_2}{100}\frac{p_3}{100}\frac{p_4}{100} $$
$$ \frac{p_1+p_2+p_3+p_4}{100} = \frac{p_1p_2p_3p_4}{10^8} $$
$$ p_1+p_2+p_3+p_4 = \frac{p_1p_2p_3p_4}{10^6} $$
$$ (p_1+p_2+p_3+p_4) \times 10^6 = p_1p_2p_3p_4 $$
The purpose of the last step is to avoid using division in the code. That would get us back to the same type of rounding error we were trying to avoid by representing prices in cents.
That last equation is how we recognize a solution for values represented as cents. Let’s call it Equation 1.
Optimization 1: Calculate Lower and Upper Bounds
Now that we’re clear on how to refrain from using floating-point numbers, here’s the first optimization.
To avoid having to inspect all $2000^4 = 1.6 \times 10^{13}$ permutations, there are a few lower and upper bounds we can use to reduce the solution space.
First, the problem statement states that each solution must be printed only once. In this context, that means we’re dealing with combinations, not permutations. For example, consider the first sample output line in the problem statement: 0.50 1.00 2.50 16.00. If we also printed 1.00 0.50 2.50 16.00, the solution would not be correct. We must only print each set of prices once, regardless of ordering.
A simple way to avoid duplicate rows in the output is to have each nested loop start iterating with the number its parent loop is processing. For example, if the first price is currently 150 cents, we’ll start checking the second price at 150 cents, not 149 cents. (Note: duplicate prices are allowed in the set).
That takes care of the lower bound. To get an upper bound, we can use the fact that the four prices must sum to at most 2000 cents. Therefore, each nested loop can exit when it reaches 2000 minus the sum of the current values for the nested loops above it. To see this rule in action, here’s the pseudocode for version 1 of the solution:
for each price p1 from 1 to 2000
for each price p2 from p1 to 2000-p1
for each price p3 from p2 to 2000-p1-p2
for each price p4 from p3 to 2000-p1-p2-p3
if (p1+p2+p3+p4)*10^6 == p1*p2*p3*p4
print a line with the four prices
When implemented in Java, this solution runs on my local machine in about 5.5 minutes. That’s way over the time limit, but it’s short enough to wait for a solution I can use to check my faster implementations.
Optimization 2: Check Products Early
Optimization 1 applies the sum constraint from the problem statement to reduce the problem space we need to search. The goal of this optimization is to do the same with the product constraint. Because we’re testing the price combinations in order from smallest to largest and because the product of four positive integers grows faster than their sum, we can further reduce the problem space by stopping our search when we get to a product of €20.
Here’s how the product check works. The problem tells us that $(p_1+p_2+p_3+p_4) \leq 2000$ (€20 = 2000 cents). Plugging that value into the left side of Equation 1 above, we can calculate that $2000 \times 10^6 = 2 \times 10^9$ is the largest product we need to consider.
Because of how the loops are set up, $p_1 \leq p_2 \leq p_3 \leq p_4$ is a loop invariant. Therefore, $p_1^4 \leq p_1p_2p_3p_4$, which means $p_1^4 \leq 2 \times 10^9$. Similarly, $p_1p_2^3 \leq 2 \times 10^9$ and $p_1p_2p_3^2 \leq 2 \times 10^9$. This means we can break out of each loop as soon as the product exceeds this value. (Or equivalently, just adjust the loop maximum).
Here’s the updated algorithm:
for each price p1 from 1 to 2000
if (p1^4 > 2*10^9) break
for each price p2 from p1 to 2000-p1
if (p1*p2^3 > 2*10^9) break
for each price p3 from p2 to 2000-p1-p2
if (p1*p2*p3^2 > 2*10^9) break
for each price p4 from p3 to 2000-p1-p2-p3
if (p1+p2+p3+p4)*10^6 == p1*p2*p3*p4
print a line with the four prices
This one runs for me in about 2.4 minutes, which is more than twice as fast as Optimization 1. Not bad, but still nowhere near where it needs to be.
Optimization 3: Use More Algebra
The solutions we have seen so far all have the same asymptotic time complexity, $O(n^4)$. We can optimize the four nested loops so they run in minutes instead of years (Optimization 1), and then optimize them again so they run in fewer minutes (Optimization 2). But what if we could remove one of the loops entirely?
Take a look at Equation 1 again. It’s the equation inside the $p_4$ loop:
$$ (p_1+p_2+p_3+p_4) \times 10^6 = p_1p_2p_3p_4 $$
Once we’re in the $p_4$ loop, we already know the values of $p_1$, $p_2$, and $p_3$. So let’s collapse the sum and product of those prices into two constants:
$$ a = p_1+p_2+p_3 $$
$$ b = p_1p_2p_3 $$
Let’s also put the $10^6$ into a constant:
$$ c = 10^6 $$
So we can re-write Equation 1 as:
$$ c(a+p_4) = bp_4 $$
But this equation has only one unknown, $p_4$. Rather than looping through thousands of possible values for $p_4$, we can just solve for it!
$$ bp_4 = ca + cp_4 $$
$$ bp_4 – cp_4 = ca $$
$$ p_4(b-c) = ca $$
$$ p_4 = \frac{ca}{b-c} $$
Let’s call this Equation 2. It will give us a value of $p_4$ for any value of $a$, $b$, and $c$ as long as $b \neq c$. However, we need to do a few more checks to make sure that the calculated $p_4$ value meets the problem requirements:
- $ca$ must be divisible by $b-c$, since fractional cents are not allowed.
- $p_3$ must not exceed $p_4$, since the prices must be displayed in ascending order.
- $a+p_4$ must not exceed 2000, the sum price limit.
- $bp_4$ must not exceed $2 \times 10^9$, the equivalent product price limit.
Here’s the version of the algorithm where the innermost loop is replaced with Equation 2 and the four checks:
for each price p1 from 1 to 2000
if (p1^4 > 2*10^9) break
for each price p2 from p1 to 2000-p1
if (p1*p2^3 > 2*10^9) break
for each price p3 from p2 to 2000-p1-p2
if (p1*p2*p3^2 > 2*10^9) break
b = p1*p2*p3
c = 1000000
if b == c continue
a = p1+p2+p3
d = c*a
e = b-c
if d mod e != 0 continue
p4 = d/e
if p3 > p4 continue
if a+p4 > 2000 continue
if b*p4 > 2*10^9 continue
if we made it here, print a result
Optimizing the innermost loop makes a big difference: this runs for me locally in a median time of 518 milliseconds, and my submission ran in 446 milliseconds on UVa OJ.
Thoughts on the Grocery Store Problem
This problem reminds me of a CodeForces problem called Hot Bath. Although that one is more complex, it also involves search of a solution space too large to cover entirely in the time limit, an inner loop we can eliminate by solving an equation algebraically, and floating-point rounding issues.
The lesson from the Grocery Store problem and the Hot Bath problem: look for ways you can manipulate any equations in the problem to reduce the amount of work your program must do.
(Image credit: iluvcocacola)