Problem Statement |
| | Introduction
You are running a website that uses online advertising as its main support. You have K slots available to place a different ad in each of them, numbered from 0 to K-1, ordered by visibility, from high to low. The problem is that you have N ads available, numbered from 0 to N-1, and at each moment you need to decide which ones to place in each slot. Each of the advertisers offers some money Mi for his ad, that is paid each time the ad is clicked (the famous pay-per-click).
Even when you only know their prizes, each ad has the following hidden parameters:
- Pi: Probability of click
- Di: Visibility decay value
- Vi: Variability through time
When you place the ith ad on slot number x, it has Pi*(Dix) probability of being clicked if none of the above ads was clicked first. See below for details on this.
After each minute, each ad changes its Pi value by adding a random variable X with N(0,Vi) distribution (normal distribution with mean equal to 0 and standard deviation equal to Vi). So, after each minute passes, this operation is performed:
method timeAction()
for i = 0 to N-1
Pi := Pi + N(0, Vi)
if (Pi > 1) Pi := 1
if (Pi < 0) Pi := 0
where N(a,b) is a function that gives a random normal number with mean equal to a and standard deviation equal to b.
When a user shows up it is presented the list of K ads and then he/she acts in the following way:
method userAction()
for x := 0 to K-1
let i be the number of the ad placed on slot x
if (random boolean value with probability Pi*(Dix))
click the ad and finish action (your total income is increased by Mi)
Note that at most 1 ad is clicked per user, and with probability equal to the product of each (1-Pi*(Dix)), no ad will be clicked and therefore you get no income for this user.
The system will be simulated in the following way:
- You are asked to place the ads for the next 20 minutes
- totalT := totalT + 20, if totalT > 50000 finish test case
- for t := 1 to 20: call timeAction and then userAction
Protocol
At the beginning a method init will be called with an int[] M describing the Mis and an int K, the number of slots you have. That method may return any int, but not crash. After that, a method placeAds will be called at most 2500 times with two parameters:
- timeLeft: an int that indicates the time left for execution, in milliseconds. This parameter is only provided for your convenience, and is always a positive number.
- prevClicks: a String that is empty on the first call and in the following calls it has exactly 20 characters: The ith character of it will be a digit representing the slot number that was clicked on the ith minute of the last interval or 'X' if no ad was clicked during that minute.
placeAds must return an int[] with exactly K elements, the xth element of the return must be the 0-based index of the ad you want to place at slot number x.
Scoring
You will receive a 0 for a test case
if your program crashes, uses more than 64 MB of memory, or exceeds 30 seconds of total execution time. You will also receive a 0 if placeAds returns a null result, a result that does not contain exactly K elements or one that contains a repeated element or an element less than 0 or greater than N-1. Otherwise, your score will be the amount of money you earned at the end of time. Your total score will be the sum of your normalized scores for each test case. A normalized score is your score divided by the best score in that test case.
Input Generation
All inputs will be generated with this constraints and generation method:
- N will be an integer uniformly chosen between 10 and 30, inclusive.
- K will be an integer uniformly chosen between 2 and 5, inclusive.
- Each Mi will be an integer chosen uniformly between 1 and 100, inclusive.
- Each initial Pi will be chosen following a power law distribution with exponent equal to -1/2 in [0 ; 0.25]. This means that Pi will be assigned the value X2 where X is a real number uniformly chosen in [0 ; 0.5].
- Each Di will be a real number uniformly chosen in [0.7 ; 1.0].
- Each Vi will be assigned the value 2X/10000 where X is a real number uniformly chosen in [0 ; 5].
There are 10 example test cases and 100 system test cases, so your score will be between 0 and 100 when you submit.
|
| |
Definition |
| | | Class: | AdPlacement | | Method: | init | | Parameters: | int[], int | | Returns: | int | | Method signature: | int init(int[] M, int K) | | | | Method: | placeAds | | Parameters: | int, String | | Returns: | int[] | | Method signature: | int[] placeAds(int timeLeft, String prevClicks) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | To avoid exceeding time limit, a line like "if (timeLeft<50) return {0,1,..,K-1}" at the beginning of placeAds would be a good idea. |
| - | The way the Pis evolve is a Wiener Process, in case you want to read more about that. |
| - | Notice that, while the initial value of each Pi isno more than 0.25, it may end up being greater than 0.25 by the end of the process. |
| |
Examples |
| 0) | |
| | | Returns:
"N=10
K=3
M={
50,49,15,19,20,
26,91,9,24,14}
P={
0.1409,0.0012,0.0375,0.0321,0.0104,
0.0077,0.1438,0.0269,0.2361,0.0117}
D={
0.7533,0.8280,0.8739,0.9127,0.9550,
0.7974,0.7482,0.9848,0.8941,0.9659}
V={
0.0002,0.0006,0.0004,0.0002,0.0014,
0.0009,0.0031,0.0003,0.0001,0.0011}
" | | If an oracle told you the values of the hidden variables (each P and each D) before you decided on the order in each iteration, the best expected profit you could make would be a little under two million. |
|
|
| 1) | |
| | | Returns:
"N=15
K=5
M={
63,79,25,57,41,
61,18,48,16,22,
16,9,12,40,39}
P={
0.0002,0.0008,0.0900,0.0015,0.0643,
0.0970,0.1348,0.1755,0.0020,0.1974,
0.0066,0.0193,0.0256,0.0112,0.0000}
D={
0.8898,0.9298,0.7114,0.8124,0.8147,
0.7252,0.9838,0.7928,0.9419,0.7765,
0.9206,0.8749,0.8901,0.9974,0.7960}
V={
0.0001,0.0012,0.0001,0.0007,0.0012,
0.0001,0.0002,0.0002,0.0016,0.0004,
0.0001,0.0004,0.0008,0.0005,0.0008}
" | | Here the best you could hope for, knowing the hidden variables is about 1.14 million. |
|
|
| 2) | |
| | | Returns:
"N=27
K=2
M={
42,41,63,9,77,
53,68,72,23,71,
27,90,63,71,39,
98,27,54,94,12,
92,28,84,90,44,
40,24}
P={
0.2362,0.0507,0.0895,0.1330,0.1867,
0.0043,0.0772,0.0713,0.0222,0.2080,
0.1857,0.0843,0.0111,0.1929,0.0505,
0.0133,0.0735,0.1875,0.2176,0.1510,
0.0694,0.0289,0.0002,0.1016,0.0273,
0.0219,0.0005}
D={
0.7300,0.8590,0.8073,0.9994,0.8464,
0.7727,0.8610,0.7151,0.7430,0.9208,
0.7951,0.8956,0.9590,0.8743,0.7723,
0.7005,0.8881,0.8968,0.8337,0.9046,
0.8318,0.8995,0.9950,0.8137,0.7077,
0.9720,0.8664}
V={
0.0011,0.0011,0.0019,0.0007,0.0015,
0.0008,0.0001,0.0005,0.0029,0.0003,
0.0004,0.0029,0.0008,0.0005,0.0012,
0.0015,0.0022,0.0020,0.0001,0.0006,
0.0007,0.0023,0.0005,0.0003,0.0004,
0.0009,0.0017}
" | | Best expected is about 2.28 million. |
|
|
| 3) | |
| | | Returns:
"N=14
K=4
M={
58,24,45,93,42,
59,56,49,24,56,
40,32,57,28}
P={
0.1535,0.0690,0.1694,0.0305,0.2202,
0.0305,0.1151,0.2252,0.1957,0.0722,
0.2483,0.1819,0.1829,0.0930}
D={
0.8561,0.9637,0.7928,0.9529,0.9494,
0.9928,0.8391,0.8044,0.7179,0.8028,
0.8255,0.7496,0.7314,0.9299}
V={
0.0005,0.0005,0.0002,0.0001,0.0025,
0.0007,0.0004,0.0003,0.0010,0.0002,
0.0020,0.0006,0.0029,0.0004}
" | | Best expected is about 1.74 million. |
|
|
| 4) | |
| | | Returns:
"N=22
K=5
M={
53,68,78,27,13,
26,53,52,53,33,
64,7,16,63,69,
53,9,94,29,98,
60,68}
P={
0.0212,0.0033,0.0385,0.2287,0.0747,
0.0210,0.0656,0.0797,0.0058,0.0067,
0.1298,0.0683,0.0205,0.1231,0.0590,
0.1308,0.0133,0.1894,0.1083,0.0217,
0.0398,0.0408}
D={
0.7993,0.9238,0.7239,0.7923,0.9390,
0.9632,0.8225,0.7353,0.8612,0.9692,
0.7220,0.7481,0.8686,0.8693,0.7585,
0.9019,0.9381,0.7528,0.8767,0.8491,
0.9080,0.9543}
V={
0.0010,0.0012,0.0001,0.0010,0.0002,
0.0011,0.0002,0.0030,0.0001,0.0011,
0.0001,0.0020,0.0006,0.0014,0.0009,
0.0001,0.0016,0.0031,0.0010,0.0002,
0.0002,0.0004}
" | | Best expected is about 2.25 million. |
|
|
| 5) | |
| | | Returns:
"N=18
K=4
M={
85,44,98,61,16,
18,12,3,84,88,
6,93,7,95,43,
99,95,96}
P={
0.1286,0.0629,0.0208,0.1423,0.1756,
0.0956,0.1056,0.0343,0.0154,0.0052,
0.0477,0.0084,0.0199,0.0890,0.0942,
0.1573,0.0460,0.1294}
D={
0.7937,0.7580,0.9455,0.9000,0.9903,
0.8390,0.8380,0.7986,0.7243,0.8809,
0.7086,0.7400,0.8422,0.7552,0.9542,
0.9015,0.8238,0.9858}
V={
0.0016,0.0007,0.0001,0.0011,0.0002,
0.0002,0.0007,0.0003,0.0003,0.0002,
0.0007,0.0007,0.0006,0.0011,0.0001,
0.0003,0.0016,0.0007}
" | | Best expected is about 2.05 million. |
|
|
| 6) | |
| | | Returns:
"N=21
K=2
M={
76,23,41,85,31,
23,81,12,94,61,
88,52,52,6,48,
77,97,26,59,83,
54}
P={
0.0001,0.0453,0.0025,0.0059,0.0001,
0.0155,0.0788,0.0021,0.0977,0.0260,
0.1285,0.0336,0.0073,0.0752,0.1066,
0.1341,0.1778,0.0069,0.0632,0.2056,
0.0069}
D={
0.8480,0.9871,0.8328,0.8807,0.8779,
0.9265,0.9865,0.9336,0.7813,0.7395,
0.7311,0.8926,0.8497,0.8661,0.9665,
0.8520,0.7816,0.8657,0.7427,0.8445,
0.7030}
V={
0.0012,0.0003,0.0002,0.0002,0.0002,
0.0027,0.0002,0.0015,0.0003,0.0011,
0.0001,0.0030,0.0007,0.0015,0.0029,
0.0003,0.0003,0.0005,0.0003,0.0004,
0.0006}
" | | Best expected is about 2.02 million. |
|
|
| 7) | |
| | | Returns:
"N=10
K=4
M={
67,7,24,34,95,
63,86,33,69,25}
P={
0.1426,0.0782,0.0337,0.0787,0.0921,
0.0802,0.1099,0.0523,0.0034,0.0041}
D={
0.9681,0.8808,0.8480,0.8514,0.7773,
0.9400,0.9328,0.9123,0.7418,0.9097}
V={
0.0010,0.0016,0.0001,0.0002,0.0005,
0.0006,0.0006,0.0022,0.0002,0.0010}
" | | Best expected is about 1.64 million. |
|
|
| 8) | |
| | | Returns:
"N=22
K=3
M={
86,50,31,4,88,
79,20,37,29,2,
29,8,66,41,62,
33,29,42,61,29,
44,3}
P={
0.0241,0.0087,0.0046,0.0782,0.0395,
0.2401,0.0801,0.0188,0.2470,0.0630,
0.0286,0.0557,0.1913,0.0285,0.0557,
0.0653,0.1282,0.0012,0.0017,0.1340,
0.1603,0.0004}
D={
0.7790,0.8386,0.8902,0.7090,0.8549,
0.7993,0.9393,0.7331,0.8225,0.7523,
0.8205,0.9757,0.9604,0.9495,0.7399,
0.9487,0.9342,0.7095,0.9518,0.9129,
0.7205,0.8979}
V={
0.0021,0.0001,0.0013,0.0004,0.0001,
0.0002,0.0004,0.0001,0.0011,0.0021,
0.0001,0.0008,0.0003,0.0003,0.0020,
0.0004,0.0016,0.0006,0.0003,0.0013,
0.0005,0.0012}
" | | Best expected is about 2.68 million. |
|
|
| 9) | |
| | | Returns:
"N=16
K=4
M={
62,95,1,38,74,
71,97,99,86,39,
18,74,41,45,24,
86}
P={
0.2130,0.1697,0.0148,0.0456,0.0477,
0.2360,0.0079,0.2356,0.0155,0.0553,
0.1163,0.0059,0.0144,0.0194,0.0285,
0.1431}
D={
0.7305,0.7016,0.8318,0.7431,0.9564,
0.7601,0.9144,0.7235,0.9610,0.9638,
0.9911,0.7158,0.8764,0.9255,0.9550,
0.7956}
V={
0.0002,0.0004,0.0004,0.0008,0.0009,
0.0001,0.0017,0.0014,0.0009,0.0005,
0.0015,0.0011,0.0005,0.0025,0.0003,
0.0022}
" | | Best expected is about 2.50 million. |
|
|