Expensive Dinner

Problem:

There are N people going to a restaurant,  entering one at a time.   Each person is unhappy upon sitting down if the total bill does not equal a multiple of that person’s integer identifier.    So, person “3″  will not be happy unless the bill is 3, 6, 9, 12, etc.  Upon entering the restaurant, if a person is not immediately happy, they will order something to make them happy.  This could, unfortunately, make someone else unhappy, so they would order something else .  This continues until all people are happy.  When more than one person is unhappy, any of them could be the first to order.  The restaurant sells food at any price.

As the dinning guests could arrive at any order (for 4 people, they could arrive 1,2,3,4 or 3,2,4,1 or 2,1,3,4, etc), different orders could result in a different number of trips needed by the waiter.    The waiter only comes to the table when someone is unhappy, stays until everyone is happy, and then departs.  Calculate the spread of trips the waiter will take based on the order of N people entering.

For example, if there are 4 people:

If they enter 1,2,3,4

Person 1 orders something for $1, and is happy
Person 2 orders something for $1 (total $2), and is happy
Person 3 orders something for $1 (total $3) and is happy, person 2 orders something for $3 (total $6) and all are happy
Person 4 orders something for $2 (total $8), Person 3 orders something for $1 (total 9), person 2 orders something for $3 (total $12), and all are happy.

It took 4 trips for the waiter, because each person was initially unhappy.

If they enter 4,2,1,3

Person 4 orders something for $4
Person 2 is immediately happy
Person 1 is immediately happy
Person 3 calls the waiter, bill gets bumped to $12

The waiter is called twice, so the spread for 4 people is 2.

Musings

Upon the waiter leaving the table, the bill will be the least common multiple of the integers represented.  This is true regardless of the order in which the seated guests order additional food.  Each one of them is always ordering the cheapest thing to make the total bill a multiple of their number, and eventually that number becomes a multiple of all.

To find the minimum above, I front loaded the array with the highest number, and then followed it with that numbers factors.  If 16 is first, 2,4,8 and 1 can all sit down without needing to call the waiter.  Then 15 could come in, and the least common multiple is 240.  So at that point 10, 12, 6, 5, 3 can also sit down.  Then enters 14, the LCM is 1680, so 7 can enter without calling the waiter.   13 enters and the bill gets bumped to 21840, and then finally 9 enters, making the final bill 65520, and the waiter was called  6 times

Enters Can also sit LCM
16 2,4,8,1 $16
15 10,12,5,3,6 $240
14 7 1680
13 21840
11 240240
9 720720

What if they came in increasing order?

Enters Can Also Sit LCM
1 $1
2 $2
3 6 $6
4 12 $12
5 10,15 $60
7 14 $420
8 $840
9 $2520
11 $27720
13 $360360
16 $720720

Here we have 11 trips, and in the least case we had 6, so the spread for 16 people is 5.

The question we are trying to answer is “what is the spread of trips the waiter must take”.  There are other questions lurking that may try to distract from this core issue.

A person need not call the waiter if their number (n) is a factor of the current bill.  But if we have a thousand people coming,  the dinner bill (lcm) will be greater than we can track with 64 bit integers.  So it is not practical to track the bill, so what else do we have to go on?   In the second example above, how could we tell that 6 will not need to call the waiter?  When 6 comes in, the LCM(1,2,3,4,5) = 60, a multiple of 6.  How could we determine this without calculating the LCM?
My first thought is to determine if numbers have already “sat down” that multiply to equal the number in question.  That is, 6 can sit down because 2 and 3 have already sat, but this doesn’t hold true for 8.  8 has to call the waiter, even though 4 and 2 are already sitting.

One way to calculate the least common multiple of numbers is to break the number into its prime factors.  That is, 6 becomes 3^1 * 2^1, and 9 becomes 3^2.  To find the LCM, we combine these two lists.  When the two lists have a term in common (3 in this example), we drop which ever has a lower exponent.  So the LCM of 6 and 9 is (3^2 * 2*1) = 18.

Or consider 16, 15, and 14:

16 2^4
15 5^1 * 3^1
14 7^1 * 2^1

The only common prime factor is 2 between 16 and 14, so the 14′s 2^1 is dropped, and our final LCM is:

2^4 * 5^1 * 3^1 * 7^1 = 1,680

With this formula, we can look at the question in a new way.  When someone enters the room that has a prime factor who’s power is greater than the power of that prime already (compared to those already sitting), the waiter needs to come.

Going back to 1 through 16

1 1^1
2 2^1
3 3^1
4 2^2
5 5^1
6 2^1*3^1
7 7^1
8 2^3
9 3^2
10 2^1*5^1
11 11^1
12 2^2 * 3^1
13 13^1
14 7^1 * 2^1
15 5^1 * 3^1
16 2^4

The highest powers of each prime are:

2^4
3^2
5^1
7^1
11^1
13^1

We are ultimately calculating the difference between the maximum  and the minimum waiter trips.  The maximum trips will occur when the guests enter in such a way as the lowest prime exponents come first.  That is, the number with factor 3^1 comes before that with 3^2,  and 2^1 comes before any other 2s.  Each exponent increase will cause a trip, and the total trips is the sum of the exponents.  All numbers have a 1 factor as well, omitted for clarity above, but in the maximum scenario, person 1 would enter first, causing an additional trip: 1+  4 +2 +1 +1 +1 +1 = 11.  The minimum occurs when the guests with the highest power of each prime enter first.  2^4 comes in before 2^3.  In this situation, we have as many trips as we have prime factors, in this case, 6.  So the spread is 5.

 

This has shifted the problem to one of factorization.  It is possible to brute force smaller inputs.  That is, calculate the prime exponents with something like this:

HashMap<Long, Integer> factors = new HashMap<Long, Integer>();

factors.put(1l, 1);

Long number = i;

outer:

while (number > 1){

   for (Long prime : primes){

      if (number % prime == 0){

      int newUsages = 1;

      if (factors.containsKey(prime)){

      newUsages += factors.get(prime);

   }

   factors.put(prime, newUsages);

   number = number / prime;

   continue outer;

}

savedFactors.put(i, factors);

We divide the number by the first found prime factor, and add an exponent to the prime factor by which we divided.

So if we have the number 36:

36 /2 = 18 2^1
18/2 = 9 2^2
9/3 = 3 2^2 * 3^1
3/3 = 1 2^2 * 3^2

But this method will not work for larger primes.  The larger input will contain guest counts up to 10^12. So we need to go back to the formulas one more time and look for another shortcut.    The number that we want to calculate is the difference between maximum and minimum trips.  The maximum is the sum of the exponents, and the minimum is the count of the prime bases.   When would a number count towards the maximum, but not the minimum?

The difference will always be the number of integers that have a single prime factor with a power other than 1.  For N = 16, we have

1^0
2^2
2^3
2^4
3^2

Each of these terms count toward the sum of exponents, but not the count, as prime base is already present.  2^2 causes the sum to go up, but not the count, as we already had a 2 factor.  2^3 does the same thing.

 

Solution

 

The number of waiter trips is equal to the number of exponents greater than 1 of prime numbers less than the square root of the number of guests that are less than or equal to the number of guests.  That is, the number of times you can multiply a prime number by itself and have a sum less than the guest count.    IF we have 16 guests, we iterate through prime numbers starting with 2.  2^2, 2^3, 2^4 are all less than or equal to 16.  Then we move on to 3, 3^2 is less than 16.  We need to add one more to account for the prime ^ 0 factor.  We don’t need to test any primes greater than the square root of 16, because the square of this term would be greater than 16, and it wouldn’t be counted.

 

For the large input, we have guest counts up to 10^12, so we need to enumerate through all of the primes less than 10^6.    One of the fastest ways to do this is to use the Sieve of Eratosthenes.  We start with 2, and eliminate all multiples thereof from the prime list.  Then we go to 3, and do the same.  Once we have all the primes, we check how many powers of that prime fit under each N, and this produces the final result.

boolean[] prime = new boolean[1000001];
Arrays.fill(prime, true);
for (int i = 2; i<prime.length; i++){
   if (prime[i]){
	for (int j = 2*i; j<1000001; j+=i){ //eliminate all numbers with this as a factor
	    prime[j] = false;
	}
   }
}

for (int i = 0; i < numTests; i++){
   Long numberOfGuests = Long.parseLong(reader.readLine());
   long count = numberOfGuests == 1 ? 0 : 1;
   for (int j = 2; j 0){
	thisCount++;
	sum *= j;
   }
   count += thisCount -1;
   }
}

results.add(count);

Leave a Reply