Connection Status:
Competition Arena > StoreDB

StoreDB

SRM 134 · 2003-02-08 · by LunaticFringe

SRM 134 · 2003-02-08 · by LunaticFringe
Class Name: StoreDB
Return Type: int[]
Method Name: bestBrands
Arg Types: (vector<string>, string)
Problem Statement

Problem Statement

Many grocery stores use a technique called "data mining" to find interesting and useful relationships between customers and purchased items. (For example, one supermarket using this technology noted that customers tended to buy beer and diapers together on Thursdays and Saturdays.) Information gained in this manner can then be used to determine optimal placement of items in the store, or to decide when certain items should go on sale.

One very basic and necessary ability of data mining is that of prediction. More specifically, given a particular customer and a product type, the program should be able to predict which brand the customer is most likely to buy. Obviously, some assumptions need to be made to achieve this goal. We can assume that the customer has a strict ordering of favorite brands (i.e. he will always prefer one brand to another), and will always purchase the brand dictated by his ordering.

You will be given a String[] pastVisits, representing the customer's past outings to the store. Each element of pastVisits will consist of a series of characters, indicating the status of the various brands available that day. A period ('.') represents an available brand, an 'X' character represents a brand that was sold out, and a dollar sign ('$') represents the brand that the customer purchased on that outing. The customer will have always purchased one and exactly one of the available brands.

You will also be given a String available, indicating which brands are currently on store shelves. (available will contain only period ('.') and 'X' characters.) For each available brand, your program should decide whether or not it is possible that the customer will purchase this brand today, under the assumptions outlined above. Return a int[] containing the zero-based indices of every potential purchased brand, in ascending order.

Constraints

  • pastVisits will contain between 0 and 50 elements, inclusive.
  • Each element of pastVisits will consist of only the characters in the string "$.X" (quotes for clarity).
  • Each element of pastVisits will contain exactly one '$' character.
  • available will contain between 1 and 50 characters, inclusive.
  • Each element of pastVisits will contain the same number of characters as available.
  • available will consist of only the period ('.') and 'X' characters, and will contain at least one period character.
  • There will always be at least one valid ordering of brand preferences.
Examples
0)
{".X$X."}
"....."
Returns: { 1,  2,  3 }

There is only one record in the database corresponding to this customer and item type. On the outing in question, brands 1 and 3 were sold out. The customer purchased brand 2 over the alternatives (brands 0 and 4). Today, every brand is available and on store shelves. You know that the customer will not buy brand 0 or brand 4, since they clearly prefer brand 2 to either of those options. However, you know nothing about his opinion on brands 1 and 3. Therefore, brands 1, 2, and 3 are all potential candidates for purchase.

1)
{".X$X.","X$X.X"}
"....."
Returns: { 1,  2 }

The second element of pastVisits tells us that the customer prefers brand 1 to brand 3. Combined with the previous example, this removes brand 3 from the list of candidates for purchase today, leaving only brands 1 and 2.

2)
{".....$."}
".X...X."
Returns: { 0,  2,  3,  4,  6 }

Brand 5 is the customer's favorite, but it's not in stock today, and you have no information about the other brands. Therefore they should all be returned as possibilities (with the exception of brand 1, since it's unavailable today as well).

3)
{".$X","X.$"}
".X."
Returns: { 2 }

The customer prefers brand 1 to brand 0, and prefers brand 2 to brand 1. Therefore, he must prefer brand 2 to brand 0.

4)
{}
"...XXX..."
Returns: { 0,  1,  2,  6,  7,  8 }

There is no previous data relating to this customer and this type of item. Any of the six brands available today could be his preferred brand.

Submissions are judged against all 39 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StoreDB with a public method vector<int> bestBrands(vector<string> purchases, string available) · 39 test cases · 2 s / 256 MB per case

Submitting as anonymous