BearEats | Topcoder Archive

Problem Statement

Bear Limak and deer Evil have N cookies with various flavors. Cookies are numbered 0 through N-1. Bears and deer are natural enemies so Limak and Evil don't want to eat together. They decided to divide cookies by playing a simple game. They will alternately take one cookie. Limak starts. The game ends when there are no more cookies.

As you can guess, bears and deer prefer different flavors. The i-th cookie has value A[i] for Limak and value B[i] for Evil. We define Limak's score as sum of A[i] of his cookies and Evil's score as sum of B[i] of his cookies.

Limak knows his opponent's strategy. Evil always takes a cookie with the biggest B[i]. In case of tie he takes a cookie with the biggest A[i] (from cookies with the biggest B[i]).

Limak wants to maximize the difference between his and Evil's score. Help him and find the maximum possible value of L-E, where L denotes Limak's score and E denotes Evil's score.

The description of cookies is provided in the form of a pseudorandom generator. You are given the ints N, R, C, D, A_MAX, and B_MAX. As defined above, N is the number of cookies. The flavors of cookies are generated by the pseudocode below. Watch out for integer overflow when implementing it.

for i between 0 and N-1, inclusive:
    R = (C * R + D) modulo (10^9+7);
    A[i] = R % A_MAX;
    R = (C * R + D) modulo (10^9+7);
    B[i] = R % B_MAX;

Note that A[i] will be between 0 and A_MAX-1, inclusive. And B[i] will be between 0 and B_MAX-1, inclusive.

Definition

Class:: BearEats
Method:: getDifference
Parameters:: int, int, int, int, int, int
Returns:: long
Method signature:: long getDifference(int N, int R, int C, int D, int A_MAX, int B_MAX)
(be sure your method is public)

Notes

N will be between 1 and 200,000, inclusive.
R, C and D will be between 0 and 1,000,000,000, inclusive.
A_MAX and B_MAX will be between 1 and 1,000,000,000, inclusive.

Constraints

Examples

```
3
```
```
4
```
```
4
```
```
1
```
```
11
```
```
15
```
```
Returns: -3
```
A = {6,2,4}, B = {9,14,4}. Limak should take the second cookie - (2,14). It has value A[i]=2 for him. Evil wants a cookie with the bigest B[i] so he takes (6,9). Limak can take the last cookie (4,4) and his score is 2+4=6. Evil's score is 9 so difference is 6-9 = -3. Limak can't achieve a better difference.
```
5
```
```
2
```
```
3
```
```
0
```
```
14
```
```
40
```
```
Returns: 4
```
A = {6, 12, 10, 6, 12}, B = {18, 2, 18, 2, 18}. Optimal start for Limak is to take the cookie (12,18). There are two cookies with the biggest B[i] now and Evil takes the one with bigger A[i] - (10, 18). Limak takes (6,18), Evil (12,2) and Limak (6,2). Limak has score 12+6+6 = 24. Evil has score 18+2 = 20.
```
4
```
```
938593858
```
```
538591850
```
```
384025833
```
```
885912358
```
```
3405
```
```
Returns: 1452754016
```
A = {224250140, 715072124, 737687500, 357608742}, B = {2859, 908, 1144, 2749}. Evil wants first cookie and the last one and Limak should allow him to do it. Limak ends with score 737687500 + 715072124 and Evil with 2859 + 2749.

999998741

999997411

64592149

Returns: 462494

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.