PairwiseSums

SRM 182 · 2004-02-07 · by dgarthur

SRM 182 · 2004-02-07 · by dgarthur · Brute Force, Math

Show categories

Class Name: PairwiseSums

Return Type: int[]

Method Name: reverse

Arg Types: (vector<string>)

Problem Statement

Given a list of numbers, A = {a₀, a₁, ..., a_n-1}, its pairwise sums P are defined to be all numbers of the form a_i + a_j for 0 <= i < j < n. For example, if

A = {1,2,3,4},

then

P = {1+2, 1+3, 1+4, 2+3, 2+4, 3+4} = {3, 4, 5, 5, 6, 7}.

The order of the terms in P is ignored, and both A and P may contain duplicates.

In general, it is very easy to compute the pairwise sums of a list, but it is much more difficult to perform this operation in reverse, extracting the original list given its pairwise sums. That is where you come in. Create a class PairwiseSums that contains a method reverse, which takes a String[] sums. Each element in sums will consist of space-separated integers. The method should consider the list P containing all the integers in all the elements of sums. If there is exactly one non-decreasing int[] of non-negative integers, A, such that P contains precisely the pairwise sums for A, the method should return A. Otherwise, it should return an empty int[].

Constraints

sums will contain between 1 and 50 elements inclusive.
Each element of sums will contain between 1 and 50 characters inclusive.
There will be a total of at least three integers in sums.
Each element of sums will contain at least one integer.
Each character in sums will either be a space (' '), or a digit ('0'-'9').
Each integer in sums will be between 0 and 1000 inclusive, and will have no leading 0's.
Each element of sums will have precisely one space between consecutive integers, and will have no leading or trailing spaces.

Examples

{"3 5 4 7 6 5"}
Returns: { 1,  2,  3,  4 }

This is the example from the problem statement.

{"0", "1000", "1000"}
Returns: { 0,  0,  1000 }

Note that A can contain 0 and duplicates, but it cannot contain negative integers or fractions.

{"15 30 45 60"}
Returns: { }

There exists no A whose collection of pairwise sums contains precisely four elements.

{"5 6 7 9 10 11"}
Returns: { }

A could be either {1,4,5,6} or {2,3,4,7}, so {} is returned.

{"910 689 882 565 922 815 457 674 495 653 755 948",
 "631 988 881 523 740 561 719 727 410 767 660 302",
 "519 340 498 603 960 853 495 712 533 691 643 536",
 "178 395 216 374 893 535 752 573 731 428 645 466",
 "624 287 108 266 325 483 304"}
Returns: { 35,  73,  143,  231,  252,  267,  393,  422,  460,  488,  500 }

100)

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

49 rows of 50 in sums, generating an answer of length 50. Maximal number of elements.

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

Coding Area

Language: C++17 · define a public class PairwiseSums with a public method vector<int> reverse(vector<string> sums) · 104 test cases · 2 s / 256 MB per case