SumOfArrays | Topcoder Archive

Problem Statement

Please note that this problem has non-standard time limit: 4 seconds.

Hero has two arrays of integers: A and B. Each of the arrays contains exactly n elements.

Hero will do two things with his arrays: First, he will permute the elements in each of his arrays somehow. (He is allowed to put the elements of each array into any order he likes, including their original order. He is not allowed to swap elements between A and B, each array has to be rearranged separately.) Afterwards, he will produce a new array C of n elements such that for all i, C[i] = A[i] + B[i].

Hero likes equal numbers. His goal is to produce as many equal numbers in C as possible. Formally, for a given C he is interested in integers X and Y such that the array C contains X occurrences of the value Y, and X is as large as possible.

You are given the int n and int[]s Aseed and Bseed. You will use these to generate the arrays A and B using a procedure that is explained below. Once you have the arrays A and B, your task is to compute the best possible pair (X,Y). That is, X must be as large as possible, and if there are multiple such pairs, then Y must also be as large as possible.

Return a String containing two numbers, separated with one space, first number should be the largest possible X, and the second should be the largest possible Y for that X.

The array A is generated from the int[] Aseed using the following procedure: Aseed will contain exactly 6 elements. Let's denote them a0, a1, a2, a3, a4, and a5, in order. The array A is defined using the following pseudocode:

A[0] = a0
A[1] = a1
for i = 2 to n-1:
    A[i] = (A[i-1] * a2 + A[i-2] * a3 + a4) mod a5

The array B is generated from the int[] Bseed in the same way.

Definition

Class:: SumOfArrays
Method:: findbestpair
Parameters:: int, int[], int[]
Returns:: String
Method signature:: String findbestpair(int n, int[] Aseed, int[] Bseed)
(be sure your method is public)

Constraints

n will be between 3 and 100,000, inlusive.
Aseed and Bseed will contain exactly 6 elements.
Aseed[5] and Bseed[5] will be between 2 and 100,000, inclusive.
Aseed[0], Aseed[1], Aseed[2], Aseed[3], Aseed[4], will be between 0 and Aseed[5]-1, inclusive.
Bseed[0], Bseed[1], Bseed[2], Bseed[3], Bseed[4], will be between 0 and Bseed[5]-1, inclusive.

Examples

```
3
```
```
{1,1,1,1,1,2}
```
```
{1,1,1,1,1,2}
```
```
Returns: "3 2"
```
Arrays are {1,1,1} and {1,1,1}, any permutation gives array {2,2,2} so answer is 3 occurrences of 2.
```
3
```
```
{1,1,1,1,1,4}
```
```
{1,1,1,1,1,4}
```
```
Returns: "2 4"
```
Arrays are {1,1,3} and {1,1,3}. If two arrays stay unchanged array of sums will be {2,2,6}, it have two occurrences of 2. But if we permute elements in first array and get array {1,3,1} then array of sums will be {2,4,4}, it have also two occurrences, but in this case second value is 4 which is better.
```
3
```
```
{1,2,0,0,1,5}
```
```
{0,1,0,0,1,5}
```
```
Returns: "3 2"
```
Arrays are {1,2,1} and {0,1,1}. Its possible to permute elements to get array {2,2,2}, so answer is pair 3 2.

{5,6,2,4,6,11}

{6,5,2,4,2,7}

Returns: "9 7"

{6274,99908,61138,86540,56297,100000}

{28275,25494,65423,61118,64925,100000}

Returns: "3027 102148"

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.