### PROBLEM LINK:

**Setter-** Misha Chorniy

**Tester-** Misha Chorniy

**Editorialist-** Abhishek Pandey

### DIFFICULTY:

CHALLENGE

### PRE-REQUISITES:

Varying. Challenge problem is usually an application of your skills in competitive programming in general.

### PROBLEM:

Given an array A[] of randomly generated sequences, we have to add some integer D_i (need not be distinct) to each array element A_i, where 0\le D_i\le K. Our goal is to maximize \frac{1}{M}\sum_{i=1}^{M} B_i where B_i=(A_1*A_2...*A_N)\%P_i

### QUICK ANALYSIS:

It seemed that contestants faced problems in getting a good solution. Weâ€™re concluding that, because, Some of the trivial solutions got too high points than what they should have got. Majority of the contestants simply printed back the input, or used input+rand()\%K &etc.

### ANALYSIS:

The first thing I want to say is that, this editorial is incomplete. And it will remain so, until you guys dont contribute! Its impossible to have any hard and fast approach for the challenge problems, and for the editorial to be at its full potential, I want to request you guys to discuss your approach. Benefit in challenge problem is better gained by discussion, seeing flaws of your approach and analyzing otherâ€™s strengths- and seeing what worked well, and to what degree. Hence, I would request the community to put forward their approach and intuition behind the question :).

As for editorial, I will try to discuss some of the approaches I saw, in both div1 and div2. I hope you people like it

**1. Div2-**

Not even 10 minutes passed from start of contest on the historical date of 6th April,2018 when **Div2** had got the first few accepted solutions. I had a guess in mind, and I,curious as a doomed cat, decided to see what they did and confirm my intuition. And I dont know if it was fate, or destiny, or perhaps something else, but what I saw was an exact picture of what I had in my mindâ€¦

```
cin>> arr[i]; //Take array input.
cout<< arr[i];//Print it back.
```

This approach got something \approx 85-88 points. It was 88.7 when I checked last on 14th.

Further solutions were also on similar lines. Eg-

```
cin>>arr[i];
cout<< arr[i]+rand()%k;
```

This one got 85.8 points then. Sad luck for that guy

```
cin>>arr[i];
cout<< arr[i]+k;
```

This solution performed better, and got around$88-89$ points on average.

Some of the better solutions at div2 which got \ge90 involved-

- Choose one of the primes. Lets call it P Either largest, smallest, middle one or randomly any.
- Make array ideal according to that prime, i.e. add D_i so that (A_1*A_2..*A_N)\%P is maximum.
- Pray that this solution gets better points.

By roughly around 20-25 submissions, people experimented with what prime to take. Most of them settled on the median prime.

A good number of approaches used simulation and storing array and its result. Eg-

```
cin>>arr[i];
Store arr[i]+rand()%k;//Store in a vector etc.
Compute score for the just stored array.
Repeat above 250-400 times.
Print the configuration with maximum score
```

Depending on luck and number of simulation, the above approach fetched 88-94.7 points. I saw quite a few with 94.7 points.

Some of the top approaches also use the concept of simulating till just about to time-out. The contestants chosed a distribution (random, or some other) which they simulated for \approx3.8-3.95 seconds where they sought to see which choice of D_i is increasing score for a particular A_i. When about to time out, they aborted the process and printed the output they got.

**2. Div1**

The performance of Div1 was kind of similar to Div2 xD. One of the codes which got 91.1 points at pretest was-

```
cin>>A[i];
cout<< A[i]+K/2;
```

Most of the approaches were common- like simulation till best answer, or take rand() values 300-400 times. Omitting the common approaches, the approaches of top solutions were quite distinct. (However, most of them are hard to decipher due to 300+ lines of code).

Some crucial optimizations were, however, seen. For example, lets say I got some values of D_1,D_2...D_N and calculated the value of Score=(A_1+D_1)*(A_2+D_2)*...*(A_N+D_N)\%P_i. The top solutions preferred to change D_i one by one, and re-calculate Score in O(Log(A_i+D_i)) by using inverses as - NewScore=({A_i+D_{old}})^{-1}*Score*(A_i+D_{new})\%P_i. This method got 95+ points on pretest.

Some of the good top codes deserve a mention here. These codes are what one can call crisp

- Python Code by @gorre_morre
- C++ by @anoxx_23
- C++ by @mihaibunget

As usual, I want to invite everybody (yes, everybody, not just the top scorers) to discuss their approaches so that we can have an engaging and learning insights into various intuitions

### CHEF VIJJUâ€™S CORNER:

**1.** The very first solution submitted by tester to test this problem was also simply printing back the input xD. After that as many as 16 more submissions were made.

**2.**Lets discuss the setterâ€™s approach here. Lets take a random subset (serveral times) of array P[] and multiply the primes in this subset. Lets call their multiple MUL. Now, we now that MUL\%P_i=0 where P_i is a prime in the subset.Now, our aim is to get the value of (A_1+D_1)*(A_2+D_2)....*(A_N+D_N) closer to (preferably exactly equal to) MUL-x. This is because, by applying \% operation for various P_i, we will be left with MUL\%P_i-x\%P_i=(-x)\%P_i. We can go greedily and try to factorize MUL-1,MUL-2,...,MUL-x (The exact value of x can be experimented upon). The factorization will help us in manipulation of D_i values.

One thing to check is that, (A_1+K)*(A_2+K)..*(A_N+K) must have a value more than MUL else the above scenario may not be possible. We can check this by using log function, i.e. by changing expression (A_1+K)*(A_2+K)..*(A_N+K)

to-

Log(A_1+K)+Log(A_2+K)+...+Log(A_N+K).

Similarly, MUL can be expressed as (Log(P_1) +Log(P_2)+....+Log(P_N))

You can find good practice problem here

**3.**There is also a better random generator in C++ known as Mersenne Twister or mt19937. It is available from C++11 and later. Some of the advantages it has over rand() are that-

- mt19937 has much longer period than

that of rand. This means that it will

take its random sequence much longer

to repeat itself again. - It much better statistical behavior.
- Several different random number generator engines can be initiated

simultaneously with different seed,

compared with the single â€śglobalâ€ť

seed srand() provides