MinimizeAbsoluteDifferenceDiv1

SRM 733 · 2018-04-13 · by ltdtl

SRM 733 · 2018-04-13 · by ltdtl · Brute Force, Simple Math

Show categories

Class Name: MinimizeAbsoluteDifferenceDiv1

Return Type: int[]

Method Name: findTuple

Arg Types: (vector<int>)

Problem Statement

You are given a int[] x that contains exactly five positive integers. You want to put four of them instead of the question marks into the following expression: | (?/?) - (?/?) |. Which numbers should you put there and in what order, if your goal is to make the value of the expression as small as possible?

More formally, you have the following expression: | (x_a / x_b) - (x_c / x_d) |. Here, "/" denotes real division (e.g., 7/2 = 3.5) and "||" denotes absolute value. You want to find the four distinct subscripts a, b, c, d for which the value of the expression is minimized.

Return a int[] with four elements: the optimal subscripts {a, b, c, d}. If there are multiple optimal answers, return the lexicographically smallest one among them.

Notes

Given two distinct arrays A and B with the same number of elements, we say that A is lexicographically smaller than B if A has a smaller value at the first index at which they differ.

Constraints

x will contain exactly five elements.
Each element of x will be between 1 and 10,000, inclusive.

Examples

{1,1,1,1,1}
Returns: {0, 1, 2, 3 }

Regardless of our choice of subscripts, the expression always evaluates to | (1/1) - (1/1) | = |1-1| = 0. The lexicographically smallest optimal solution is {0, 1, 2, 3}.

{2,3,5,7,11}
Returns: {0, 3, 1, 4 }

Both {0, 3, 1, 4} ans {1, 4, 0, 3} would minimize the given expression, but {0, 3, 1, 4} comes lexicographically first, so that is the only correct answer. The corresponding expression is |(2/7) - (3/11)| = 0.012987

{8, 2, 4, 2, 6}
Returns: {1, 0, 3, 4 }

There are four sets of subscripts that minimize the given expression: {1, 0, 3, 4}, {1, 4, 3, 0}, {3, 0, 1, 4}, and {3, 4, 1, 0}.

{124, 182, 9, 33, 70}
Returns: {2, 4, 3, 1 }

{9947, 3, 7, 11, 13}
Returns: {1, 4, 3, 0 }

{10000, 4, 10, 4, 10}
Returns: {1, 2, 3, 4 }

The smallest possible value of our expression is |(4/10) - (4/10)| = 0.

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

Coding Area

Language: C++17 · define a public class MinimizeAbsoluteDifferenceDiv1 with a public method vector<int> findTuple(vector<int> x) · 170 test cases · 2 s / 256 MB per case