Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 103
Problem: ProductInventory

Problem Statement



You have just taken over as the product inventory and ordering manager of the produce department. Your job is to maintain proper stock of fruits and vegetables for customers, while minimizing waste.

Inititally, you are given the cost of purchasing each item, the price for which you sell each item, and the number of days until each product expires. Your department always rotates product so that the oldest items are purchased first. At the beginning of each day, you receive a shipment according to what you ordered the day before. Then, throughout the day, several customers purchase products. At the end of the day, any expired products are discarded. You then have to examine the total product sold for that day, and determine what you would like to order to arrive the next morning.

On the first day, you can assume you have nothing in stock. Also, that first day you will receive purchase history information representing the previous 10 days of sales, rather than just one day.

Methods and Parameters

Your code will implement two methods:

  • int init(int[] buyPrice, int[] sellPrice, int[] expiration): This will be called once at the beginning of each test case.
  • int[] order(int[] recentPurchases): This will be called 100 times per test case, only the first N days will count towards scoring. (The value of N will not be revealed)

The init method takes three parameters, and the return value is ignored:

  • int[] buyPrice: The price of each item that you pay to have it available in store
  • int[] sellPrice: The amount of money you make for each item sold
  • int[] expiration: The number of days until each item expires (0 = good only on the day you receive it)
  • The i-th element of each array refers to the i-th item.

The order method takes one parameter and returns a int[]:

  • int[] recentPurchases: The quantity of each item purchased during the previous day
  • int[] return value: The quantity of each item you want to order for delivery the following morning
  • The i-th element of each array refers to the i-th item.


Your raw score for each test case will be the total sales to customers minus total expenditures to order inventory. If this value is negative, you will receive a score of 0. Any invalid return values, errors, time limit exceeded, etc, will score a -1.

Your overall score will be the sum of YOUR / BEST for all test cases on which you scored greater than 0, where YOUR is your score for the test case, and BEST is the best score anyone has for that test case. The resulting sum will be scaled to 1,000,000.

Test Case Generation

  • There will be between 10 and 100 items, inclusive.
  • A value of N between 10 and 100, the number of days that will be scored, will be chosen (but not provided).
  • A buyPrice for each item will be chosen between 1 and 10, inclusive.
  • A sellPrice for each item will be chosen between buyPrice / 2 and 3 * buyPrice, inclusive.
  • An expiration length for each item will be chosen between 0 and 15, inclusive.

Customer Simulation Details

There will be between 50 and 100 customers, each with a probability between 0...0.1 of buying each item on any given day. Each customer will also have an "annoyance" value between 0...0.1, indicating the probability that if an item they wish to purchase is not in stock, they will not come back in the future. Note that this value stacks, such that if multiple desired items are unavailable, that each unavailable item will carry with it the chance of losing the customer.

Limits and Test Cases

  • Runtime limit of 30s per test case
  • Memory limit of 1GB per test case
  • There are 10 example tests and 50 provisional tests
  • There will be at least 2000 system test cases.

Offline Tester

An offline tester is available to help you with developing your solution on this contest.



Parameters:int[], int[], int[]
Method signature:int init(int[] buy, int[] sell, int[] expiration)
Method signature:int[] order(int[] recentPurchases)
(be sure your methods are public)


Number of items: 5
Number of simulated customers: 5
Number of items: 10
Number of simulated customers: 10
Number of items: 15
Number of simulated customers: 15
Number of items: 20
Number of simulated customers: 20
Number of items: 83
Number of simulated customers: 83
Number of items: 34
Number of simulated customers: 65
Number of items: 98
Number of simulated customers: 97
Number of items: 49
Number of simulated customers: 74
Number of items: 55
Number of simulated customers: 95
Number of items: 84
Number of simulated customers: 51

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.