Problem Statement |
| | After years of research and development, your firm has developed a new product; one so fantasic that everyone will have to have one once they realize how great it is. Unfortunately for you, a competing company is also bringing a similar product to market. There is no reason for anyone to have both your product and your competitor's and market research suggests that people slightly prefer your competitor's product, so you will need to out-manuever them if you want to be successful.
Lucky for you, your competitor thinks their product is so amazing that they don't need to advertise. If you play your cards right, you may be able to turn a handy profit yet.
In this problem, you need to dynamically determine where to locate ads to maximize your profit. Each person will be located at a point in two dimensions. A simulation will then occur over a number of time steps. At the beginning of each time step, you may place advertisements at particular locations, which will have an effect for that timestep only. Each person will be influenced by three factors: the prior preference for your competitor's product, the influence of your advertising, and the influence of other people who have already purchased one product or the other.
More specifically, a person P will start with a weight wP = competitor < 0. For every other person who has purchased a product, the distance d from that person to P will be computed. The weight will then be adjusted up or down by C*(d+500)-2 (up if the person uses your product, down if he uses your competitor's). Next, for each advertisement you place, the distance d from that ad to P will be computed and the weight will be increased by D*(d+500)-2. At each time step, each person P will select a value xP as -ln(1/r-1), where r is a uniform random variable in (0,1). Each person with a difference between xP and wP greater than 8 will be selected. If xP is smaller than wP, the person will buy your product, otherwise the person will buy your competitor's product. The result of all this is that the higher the magnitude of a person's weight, the more likely that person is to buy a product in the next timestep. For instance, a person with a weight of 0 will buy your product with probability 3.4E-4 and your competitor's with the same probability, while a person with weight 2 will buy your product with probability 2.5E-3 and your competitors with probability 4.54E-5.
The initial locations of the N people will be chosen from K normal distributions, each with a weight si chosen as r2, where r is a uniform random variable in (0,1). Each distribution will have independently chosen standard deviations in the x and y directions from the range (200,1200), along with means chosen independently in (0,10000) for each coordinate. A person will be chosen from distribution i with probability proportional to si.
You will first be given the locations of all the people in the simulation, along with some of the parameters of the simulation, and you should return an int (which will be ignored). The update method will then be called repeatedly, telling you which people bought which products. Element i of index gives the 0-based index into x and y, and element i of product tells which one they purchased (1 for your's, -1 for your competitor's). You should then return your advertising scheme for the next time step. Each element of the returned String[]'s should be formatted as "<x> <y>". The first time the update function is called, the arrays will have size 0, as no one has bought either product before the start of the simulation.
For each ad you place in each timestep, a cost $adCost will be incurred. For each person that buys your product, you will make a profit of $1. Your goal, naturally, is to maximize your overall profit. Your overall score will simply be the average of you profit on all the test cases.
A visualizer provided to help you develop your solution. |
| |
Definition |
| | | Class: | Advertising | | Method: | update | | Parameters: | int[], int[] | | Returns: | String[] | | Method signature: | String[] update(int[] index, int[] product) | | | | Method: | init | | Parameters: | double, double, double[], double[] | | Returns: | int | | Method signature: | int init(double competitor, double adCost, double[] x, double[] y) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | Ads only last one timestep. |
| - | If no one buys any product during one step of the simulation, the simulation will be rerun for that timestep, until at least one person purchases a product. |
| - | Negative scores will be increased to 0. |
| - | If you place more than N/adCost ads, the simulation will terminate, and you will receive a 0. |
| - | While you can test the examples in the visualizer by entering the seeds 1..10, you may also download the locations of the people from http://www.topcoder.com/contest/problem/Advertising/ex0, http://www.topcoder.com/contest/problem/Advertising/ex1 ... |
| - | The time limit is 60 seconds, and the memory limit is 1024MB. |
| |
Constraints |
| - | All parameters except N and K are chosen as real numbers. |
| - | competitor will be chosen uniformly at random in (-2,-0.2) |
| - | adCost will be chosen uniformly at random in (1,10) |
| - | K will be chosen uniformly at random in [1,10] |
| - | N will be chosen uniformly at random in [1000,10000] |
| - | C will be chosen uniformly at random in (1000,10000) |
| - | D will be chosen uniformly at random in (10000,100000) |
| |
Examples |
| 0) | |
| | | Returns:
"N = 7391
K = 9
competitor = -1.3996769602268109
adCost = 4.382947278105306
C = 6301.356583692691
D = 45932.296033727725
" | |
|
| 1) | |
| | | Returns:
"N = 5472
K = 9
competitor = -1.0045314816459034
adCost = 8.902017566435216
C = 4963.193236302646
D = 12305.219227908448
" | |
|
| 2) | |
| | | Returns:
"N = 2957
K = 2
competitor = -1.0124084785466487
adCost = 8.486097310432115
C = 8352.767238144268
D = 20771.48561706445
" | |
|
| 3) | |
| | | Returns:
"N = 1919
K = 4
competitor = -0.9458449941876446
adCost = 2.801237217217649
C = 8844.189389597545
D = 25647.04548673069
" | |
|
| 4) | |
| | | Returns:
"N = 5140
K = 1
competitor = -0.5652464571554352
adCost = 9.541264833756037
C = 4899.988907012099
D = 14373.876861986962
" | |
|
| 5) | |
| | | Returns:
"N = 2405
K = 7
competitor = -1.3993566754565898
adCost = 5.066824826451321
C = 9852.743130232526
D = 65726.35643776048
" | |
|
| 6) | |
| | | Returns:
"N = 8827
K = 1
competitor = -1.0003950048572934
adCost = 7.1222354960475
C = 4269.086656520765
D = 37525.0749757682
" | |
|
| 7) | |
| | | Returns:
"N = 7707
K = 1
competitor = -1.624774126161923
adCost = 2.5832086712621076
C = 4693.371585706174
D = 55541.24266699317
" | |
|
| 8) | |
| | | Returns:
"N = 9239
K = 7
competitor = -0.3999948330662635
adCost = 3.18788302929607
C = 7088.008974203557
D = 84879.89527259486
" | |
|
| 9) | |
| | | Returns:
"N = 7933
K = 10
competitor = -0.46486861795146006
adCost = 8.54999748312766
C = 3455.1239532547734
D = 11926.436040241912
" | |
|