

Problem Statement 
Contest:
Marathon Match 12
Problem: AdPlacement
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 K1, ordered by visibility, from high to low. The problem is that you have N ads available, numbered from 0 to N1, and at each moment you need to decide which ones to place in each slot. Each of the advertisers offers some money M_{i} for his ad, that is paid each time the ad is clicked (the famous payperclick).
Even when you only know their prizes, each ad has the following hidden parameters:
 P_{i}: Probability of click
 D_{i}: Visibility decay value
 V_{i}: Variability through time
When you place the i^{th} ad on slot number x, it has P_{i}*(D_{i}^{x}) 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 P_{i} value by adding a random variable X with N(0,V_{i}) distribution (normal distribution with mean equal to 0 and standard deviation equal to V_{i}). So, after each minute passes, this operation is performed:
method timeAction()
for i = 0 to N1
P_{i} := P_{i} + N(0, V_{i})
if (P_{i} > 1) P_{i} := 1
if (P_{i} < 0) P_{i} := 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 K1
let i be the number of the ad placed on slot x
if (random boolean value with probability P_{i}*(D_{i}^{x}))
click the ad and finish action (your total income is increased by M_{i})
Note that at most 1 ad is clicked per user, and with probability equal to the product of each (1P_{i}*(D_{i}^{x})), 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 M_{i}s 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 i^{th} character of it will be a digit representing the slot number that was clicked on the i^{th} 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 x^{th} element of the return must be the 0based 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 N1. 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 M_{i} will be an integer chosen uniformly between 1 and 100, inclusive.
 Each initial P_{i} will be chosen following a power law distribution with exponent equal to 1/2 in [0 ; 0.25]. This means that P_{i} will be assigned the value X^{2} where X is a real number uniformly chosen in [0 ; 0.5].
 Each D_{i} will be a real number uniformly chosen in [0.7 ; 1.0].
 Each V_{i} will be assigned the value 2^{X}/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,..,K1}" at the beginning of placeAds would be a good idea.    The way the P_{i}s evolve is a Wiener Process, in case you want to read more about that.    Notice that, while the initial value of each P_{i} isno more than 0.25, it may end up being greater than 0.25 by the end of the process.   Examples  0)    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)    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)    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)    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)    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)    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)    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)    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)    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)    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. 


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.

