Statistics

Problem Statement for "SumOfArrays"

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

  1. 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.

  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. 3

    {1,2,0,0,1,5}

    {1,2,0,0,1,5}

    Returns: "2 3"

  4. 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. 14

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

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

    Returns: "9 7"

  6. 100000

    {1,2,3,4,5,6}

    {1,2,3,4,5,6}

    Returns: "100000 5"

  7. 100000

    {1,2,3,4,5,100000}

    {1,2,4,3,2,100000}

    Returns: "12418 99987"

  8. 100000

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

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

    Returns: "3027 102148"

  9. 100000

    {1,2,1,0,2,100000}

    {1,2,1,0,2,100000}

    Returns: "99998 100000"

  10. 100000

    {99999,99999,0,0,99999,100000}

    {99999,99999,0,0,99999,100000}

    Returns: "100000 199998"

  11. 100000

    {0,3,1,0,3,99999}

    {12,15,1,0,3,99999}

    Returns: "99999 99996"

  12. 100000

    {0,3,1,0,3,99999}

    {0,4,1,0,4,100000}

    Returns: "25003 99996"

  13. 100000

    {0,4,1,0,4,100000}

    {0,4,1,0,4,100000}

    Returns: "100000 99996"

  14. 100000

    {0,4,1,0,4,100000}

    {0,5,1,0,5,100000}

    Returns: "20000 100011"

  15. 100000

    {0,5,1,0,5,100000}

    {0,6,1,0,6,99996}

    Returns: "16670 99995"

  16. 100000

    {0,6,1,0,6,99996}

    {0,8,1,0,8,100000}

    Returns: "25003 99998"

  17. 100000

    {0,9,1,0,9,99999}

    {0,2,1,0,2,100000}

    Returns: "11112 99998"

  18. 100000

    {0,9,1,0,9,99999}

    {0,10,1,0,10,100000}

    Returns: "10009 99990"

  19. 99999

    {11,22,1,0,11,99990}

    {0,12,1,0,12,99996}

    Returns: "8339 100039"

  20. 100000

    {0,12,1,0,12,99996}

    {0,13,1,0,13,99996}

    Returns: "7693 100019"

  21. 100000

    {0,13,1,0,13,99996}

    {0,13,1,0,13,99996}

    Returns: "99996 99983"

  22. 100000

    {0,14,1,0,14,99988}

    {0,14,1,0,14,99988}

    Returns: "99988 99974"

  23. 100000

    {0,15,1,0,15,99990}

    {0,15,1,0,15,99990}

    Returns: "99990 99975"

  24. 100000

    {0,16,1,0,16,100000}

    {0,16,1,0,16,100000}

    Returns: "100000 99984"

  25. 100000

    {0,20,1,0,20,100000}

    {0,20,1,0,20,100000}

    Returns: "100000 99980"

  26. 99734

    {1251,2734,252,14544,5252,98765}

    {12416,6146,73432,1231,74234,89991}

    Returns: "20489 91657"

  27. 100000

    {1241,12512,23121,51241,32532,67777}

    {21311,12414,12412,53122,12321,68888}

    Returns: "8944 68977"

  28. 100000

    {15724,19169,26500,6334,18467,99959}

    {28145,5705,24464,26962,29358,98522}

    Returns: "36132 98908"

  29. 99999

    {26841,30145,18979,23135,19544,93007}

    {29136,11787,3752,29833,25884,95238}

    Returns: "347 93596"

  30. 100000

    {20206,21023,19481,28953,16930,92958}

    {29797,9568,9835,15362,14743,91320}

    Returns: "19900 91461"

  31. 100000

    {1791,13726,13328,13947,14839,92919}

    {30325,7793,1594,16893,12384,99506}

    Returns: "33094 99407"

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.
This problem was used for: