DiversePairsDiv1 | Topcoder Archive

Problem Statement

You are given the ints a ≤ b. Consider the set of integers between a and b, inclusive. You want to use some of these integers to construct a set of pairs of integers. A set that consists of k pairs is said to be diverse if all of the following conditions are met.

All 2k integers used in the pairs are distinct.
The sum of each pair is strictly smaller than a + b.
The sums of the k pairs are k distinct integers.

For instance, suppose that a=2 and b=4, which means that we are allowed to use the integers from the set {2, 3, 4}. Then:

{(2, 2)} is a set that contains one pair of numbers, but it is not a diverse set because it violates condition #1.
{(3, 3)} does also violate condition #1
{(2, 4)} violates condition #2, as 2 + 4 is not strictly smaller than a + b.
{(3, 4)} does also violate condition #2.
{(2, 4), (3, 3)} is a set that contains two pairs of numbers; this set violates conditions #1 and #3.
{(2, 3)} is a diverse set.
{(3, 2)} is another diverse set.

In the above example it is obvious that there is no diverse set with two or more pairs of integers, hence {(2, 3)} and {(3, 2)} are the largest diverse sets.

You are interested in finding the largest possible diverse set of pairs for the given a and b. That is, among all diverse sets of pairs you can construct, you want to find one that contains the maximum number of pairs.

Return a int[] that describes a maximum diverse set of pairs as follows: If {(x₁, y₁), (x₂, y₂), ..., (x_k, y_k)} is the set of pairs you found, return { x₁, y₁, x₂, y₂, ..., x_k, y_k }.

If multiple answers exist, you may return any one of them. If the maximum set of pairs is an empty set, then you must return an empty int[].

Definition

Class:: DiversePairsDiv1
Method:: findMaxDiversePairs
Parameters:: int, int
Returns:: int[]
Method signature:: int[] findMaxDiversePairs(int a, int b)
(be sure your method is public)

Constraints

a will be between 1 and 10^9, inclusive.
b will be between 1 and 10^9, inclusive.
b-a will be between 0 and 2,000, inclusive.

Examples

```
1
```
```
1
```
```
Returns: { }
```
```
1
```
```
2
```
```
Returns: { }
```
The only pairs of distinct integers we can construct are (1, 2) and (2, 1), but both sets {(1, 2)} and {(2, 1)} violate condition #2.
```
2
```
```
4
```
```
Returns: {2, 3 }
```
This example was discussed in the problem statement. {3, 2} is another correct return value.
```
5
```
```
9
```
```
Returns: {5, 6 }
```
There is no diverse set with two pairs of integers. In particular, the set {(5, 8), (6, 7)} does satisfy conditions #1 and #2 (all integers are distinct and all pairwise sums are small enough) but 5+8 = 6+7, so this set violates condition #3.
```
15
```
```
21
```
```
Returns: {15, 20, 16, 18 }
```
```
20
```
```
27
```
```
Returns: {21, 25, 22, 23, 20, 24 }
```

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.