Problem Statement |
| | You work as a retail dealer at a certain district, and you sell goods of several types.
Each morning you buy goods from the warehouse, set your prices for each type of goods and start your journey to the customers.
You visit houses in the district at most once per day, and customers of each house you visit might want to buy some of
your goods.
The preferences of customers of one house are described as a list of elements (GOODS_TYPE, STOP_PROB, MAX_PRICE), and their
behavior is modeled as follows:
-
starting with the first element of the list, the customer decides whether he wants to buy goods of type GOODS_TYPE;
-
he stops without buying anything (not proceeding to next elements of the list) with probability STOP_PROB, otherwise he tries to buy one unit of goods of type GOODS_TYPE;
-
if you carry at least one unit of goods of this type and your price for it is not greater than MAX_PRICE, he buys it and stops,
otherwise he proceeds to the next element of preferences;
-
if the list of preferences is over, nothing is bought.
The problem is, you don't know anything about the preferences of your customers. Your task is to maximize your average daily
profit over the time of your work.
Implementation
Your code should implement the following methods:
-
init method is called once per test case to give you:
-
the map of the district districtMap; 'X' marks a house and '.' marks a piece of street. You can walk on the streets,
and you can trade at the house only if you stand at a street cell which is horizontally or vertically adjacent to it.
-
warehouse prices per unit of goods of each type warehousePrices. You can figure out the number of distinct goods you can trade G as the number of elements in warehousePrices;
-
the number of units of goods you can carry C;
-
the number of steps you can perform per day S;
-
dayTrade method is called at the start of each day to get your decision about this day's actions.
It gives you the results of the previous day as int[] visitedHouses.
Element i*W+j of visitedHouses will describe the result of visiting the house in row i and column j
and will be -2 if no trade was attempted (or there is no house at this cell), -1 if customers of this house bought nothing, or the index of the type of goods (0..G-1) they bought otherwise.
You must return a String[], formatted as follows:
-
first G elements must be formatted as "QUANTITY PRICE" and give the (integer) quantity of units of each type of goods (in order)
that you want to purchase from the warehouse for this day and the (integer) price you are setting for one unit of this type of goods for this day.
-
the rest of the elements (at most S+1) must be formatted as "ROW COL" and describe the sequence of movements and trade actions. First element gives coordinates of the cell you want to start your day with. Next elements denote either moving to street cell (ROW, COL) or trading at house cell (ROW, COL). Each next cell must be adjacent to previous one. Trading at a house doesn't change your position. You can move only on street cells. You can trade at each house at most once.
Scoring
Your score for a test case will be your balance after 3000 days.
Your overall score will be the sum of your individual scores, divided by the greatest score achieved by anyone for
that test case. Negative individual scores are replaced with 0 when calculating the overall score.
Test Case Generation
The main part of generating test case is putting the houses on the map. This is done by choosing the type of housing - long parallel streets one house wide or small blocks of houses with houses along their borders. The chosen type of housing fills a random rectangular part of the area. The rest of the area is filled randomly with isolated houses, i.e., houses which don't have neighbors. Note that isolated houses are considered to be 'rich' when generating the customers' preferences, so their inhabitants get a bonus to MAX_PRICE.
For the details of test case generation process see visualizer source code.
Tools
A visualization tool is provided for offline testing. |
| |
Definition |
| | | Class: | StreetSales | | Method: | dayTrade | | Parameters: | int[] | | Returns: | String[] | | Method signature: | String[] dayTrade(int[] visitedHouses) | | | | Method: | init | | Parameters: | String[], int[], int, int | | Returns: | int | | Method signature: | int init(String[] districtMap, int[] warehousePrices, int C, int S) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | You can return any integer from init, it will be ignored. |
| - | Invalid parameters returned from dayTrade result in a score of 0. |
| - | The goods you trade are good for one day only, so if you haven't sold them the day you bought them, you can't sell them later. |
| - | Your starting balance is 0, and you can have negative balance during the simulation as well as at the end of the simulation (note that only positive balance will contribute to your score). |
| - | Your return must contain between G+1 and G+1+S elements. |
| - | The memory limit is 1024 MB and the time limit is 10 seconds per test case (which includes only time spent in your code). There is no explicit code size limit. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Constraints |
| - | The numbers of rows H and columns W in the area will be between 20 and 100, inclusive (except for seed=1). |
| - | The number of types of goods G will be between 2 and 10, inclusive. |
| - | The warehouse price for each type of goods will be between 70 and 100, inclusive. |
| - | The number of elements in preferences of each house will be between 1 and G, inclusive. |
| - | GOODS_TYPEs of one house will be chosen as the first elements of a random permutation of 0..G-1, so they all will be distinct. |
| - | STOP_PROB will be between 0 and 10, inclusive (in percent). |
| - | MAX_PRICE will be calculated as warehouse price for this type of goods plus random bonus 10..25. Isolated houses will get an extra bonus of 5..15. |
| - | C will be approximately from 0.5 to 1.0 of the number of houses in the area. |
| - | S will be approximately from 0.125 to 0.25 of the number of cells in the area. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
H = 15
W = 15
G = 10
C = 45
S = 34" | |
|
| 1) | |
| | | Returns: "seed = 2
H = 74
W = 86
G = 7
C = 1031
S = 925" | |
|
| 2) | |
| | | Returns: "seed = 3
H = 78
W = 74
G = 10
C = 545
S = 1379" | |
|
| 3) | |
| | | Returns: "seed = 4
H = 41
W = 65
G = 10
C = 384
S = 603" | |
|
| 4) | |
| | | Returns: "seed = 5
H = 43
W = 68
G = 8
C = 294
S = 468" | |
|
| 5) | |
| | | Returns: "seed = 6
H = 71
W = 77
G = 9
C = 728
S = 829" | |
|
| 6) | |
| | | Returns: "seed = 7
H = 80
W = 28
G = 10
C = 370
S = 364" | |
|
| 7) | |
| | | Returns: "seed = 8
H = 24
W = 35
G = 7
C = 196
S = 168" | |
|
| 8) | |
| | | Returns: "seed = 9
H = 84
W = 44
G = 4
C = 435
S = 816" | |
|
| 9) | |
| | | Returns: "seed = 10
H = 87
W = 33
G = 2
C = 580
S = 546" | |
|
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)2020, TopCoder, Inc. All rights reserved.