Connection Status:
Competition Arena > DiversePairsDiv1

DiversePairsDiv1

TCO18 Poland · 2018-04-20 · by ltdtl

TCO18 Poland · 2018-04-20 · by ltdtl · Greedy, Math
Class Name: DiversePairsDiv1
Return Type: int[]
Method Name: findMaxDiversePairs
Arg Types: (int, int)
Problem Statement

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.

  1. All 2k integers used in the pairs are distinct.
  2. The sum of each pair is strictly smaller than a + b.
  3. 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 {(x1, y1), (x2, y2), ..., (xk, yk)} is the set of pairs you found, return { x1, y1, x2, y2, ..., xk, yk }.


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[].

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

This example was discussed in the problem statement. {3, 2} is another correct return value.

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

4)
15
21
Returns: {15, 20, 16, 18 }

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

Coding Area

Language: C++17 · define a public class DiversePairsDiv1 with a public method vector<int> findMaxDiversePairs(int a, int b) · 222 test cases · 2 s / 256 MB per case

Submitting as anonymous