Monday, February 16, 2015

ShoppingSurveyDiv2

Problem:

TopCoder Problem Statement - ShoppingSurveyDiv2
Single Round Match 634 Round 1 - Division II, Level Two

Overview:

Given a count of how many of each item was purchased, and the number of customers, determine the smallest number of customers that could have purchased one of each item.

Java Source:
01: public class ShoppingSurveyDiv2 {
02: 
03:     public int minValue(int N, int[] s) {
04: 
05:         int numItemsPurchased = 0;
06: 
07:         for (int i : s) {
08:             numItemsPurchased += i;
09:         }
10: 
11:         int maxItemsPurchasedWithNoBigShoppers = (s.length - 1) * N;
12: 
13:         int numBigShoppers =
14:                 numItemsPurchased - maxItemsPurchasedWithNoBigShoppers;
15: 
16:         return (numBigShoppers < 0) ? 0 : numBigShoppers;
17: 
18:     }
19: }
Notes:

First, we'll count the total number of items that have been purchased. This is stored in the variable numItemsPurchased.

Next, we calculate the number of items that could be purchased if every customer stopped just short of buying one of each. That is each customer, buys (s.length -1) items. We'll call that maxItemsPurchasedWithNoBigShoppers.

The number of BigShoppers that we'll need is now just the difference between numItemsPurchased and maxItemsPurchasedWithNoBigShoppers. This value may be negative, in which case we'll return zero.

This problem is a bit difficult to understand, but once you get it, the code is really easy.

No comments:

Post a Comment