Connection Status:
Competition Arena > SumOfArrays

SumOfArrays

SRM 603 · 2013-12-22 · by subscriber

SRM 603 · 2013-12-22 · by subscriber · Brute Force
Class Name: SumOfArrays
Return Type: String
Method Name: findbestpair
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

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.

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
0)
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.

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

2)
3
{1,2,0,0,1,5}
{1,2,0,0,1,5}
Returns: "2 3"
3)
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.

4)
14
{5,6,2,4,6,11}
{6,5,2,4,2,7}
Returns: "9 7"

Submissions are judged against all 31 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SumOfArrays with a public method string findbestpair(int n, vector<int> Aseed, vector<int> Bseed) · 31 test cases · 2 s / 256 MB per case

Submitting as anonymous