ShippingCosts | Topcoder Archive

Problem Statement

We have N potential customers, numbered 0 to N-1. Each customer is willing to purchase one piece of our product. Customer i is willing to pay up to maxPrice[i] dollars for the product. If we decide to sell a piece to customer i, we will have to pay ship[i] dollars for shipping. The difference between the price they paid and the shipping cost is our profit from this sale. (The customer is not willing to buy the product if the price is greater than their maximum. We are not willing to sell the product if the shipping cost exceeds its price.)

The price of the product must be the same for all customers. Find and return the price that maximizes our total profit. If there are multiple optimal prices, return the smallest one among them.

As we have to keep the input size small (sorry!), please use the following pseudocode to produce the input arrays:


L = length(maxPricePrefix)
state = seed

for i = 0 .. L-1:
    maxPrice[i] = maxPricePrefix[i]
    ship[i] = shipPrefix[i]

for i = L .. N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    maxPrice[i] = 1 + (state mod 10^9)
    state = (state * 1103515245 + 12345) modulo 2^31
    ship[i] = state mod maxPrice[i]

Definition

Class:: ShippingCosts
Method:: bestPrice
Parameters:: int, int[], int[], int
Returns:: int
Method signature:: int bestPrice(int N, int[] maxPricePrefix, int[] shipPrefix, int seed)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator.

Constraints

N will be between 1 and 100,000, inclusive.
maxPricePrefix will contain between 0 and min(N, 500) elements, inclusive.
shipPrefix will contain the same number of elements as maxPricePrefix.
For each i, 0 <= shipPrefix[i] < maxPricePrefix[i] <= 10^9.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

```
7
```
```
{20, 6, 9, 10, 12, 15, 20}
```
```
{18, 1, 3, 8, 4, 14, 10}
```
```
0
```
```
Returns: 9
```
Let's label the potential customers ABCDEFG in the order in which they are given. If we set the price of the product to 9, we will sell it to customers C (profit 9-3 = 6), D (profit 9-8 = 1), and E (profit 9-4 = 5), thus the total profit will be 12. If we set the price of the product to 20, we will sell it to customers A (profit 2) and G (profit 10), so the total profit is again 12. No other price gives us a better total profit, so we return the smallest of these optimal prices.

{20, 6, 9, 10, 12, 15, 20}

{17, 1, 3, 8, 4, 14, 10}

Returns: 20

Now it's more profitable to sell at 20.

```
12
```
```
{456789, 567890}
```
```
{123, 456789}
```
```
47
```
```
Returns: 502589131
```
The two arrays should look as follows: maxPrice: 456789, 567890, 325621309, 41878299, 346820649, 31250151, 507736277, 569514867, 181454401, 329587903, 176241773, 502589131 ship: 123, 456789, 263614405, 35219194, 317141784, 25224014, 118477437, 153125456, 18263474, 155042660, 140798375, 375999962

{999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998}

{314, 159, 265, 358, 979, 323, 846, 264, 338}

12345678

Returns: 999999990

The optimal selling price is 999,999,990. The optimal profit is 8,999,996,064.

```
3
```
```
{5, 5, 7}
```
```
{4, 4, 3}
```
```
22
```
```
Returns: 5
```
price | profit --------------- 4 | 1 5 | 4 6 | 3 7 | 4 If we try to sell at any other price, our profit will be 0.

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)2024, Topcoder, Inc. All rights reserved.