Connection Status:
Competition Arena > PermutationValues

PermutationValues

SRM 161 · 2003-08-28 · by lbackstrom

SRM 161 · 2003-08-28 · by lbackstrom · Advanced Math, Recursion, Search
Class Name: PermutationValues
Return Type: int[]
Method Name: getValues
Arg Types: (vector<int>, vector<int>, string, vector<string>)
Problem Statement

Problem Statement

You will be given two int[]s lows and highs describing a group of integer ranges. lows[i] and highs[i] represent the lower and upper inclusive bounds for the ith range of numbers. None of the ranges will overlap. The total group of numbers used in this problem will be the combination of the ranges given in lows and highs.

You will also be given a numeric String lexPos and a String[] retInts containing numeric Strings. Assume you listed all possible permutations of the given group of numbers in ascending lexicographical order (no repeated permutations). Find the permutation A that is in position lexPos lexicographically. Return a int[] with the same number of elements as retInts whose kth element is A[retInts[k]]. lexPos is a 0-based index into the list of possible permutations. Each element of retInts is a 0-based index into the relevant permutation.

In a lexicographical ordering, permutations are ordered by their first elements, with ties broken by their second elements, further ties broken by their third elements, and so forth. If lexPos is greater than the total possible number of lexicographical orderings (without repeats) T, then use lexPos%T instead of lexPos (% denotes mod).

Notes

  • Each element of retInts and lexPos will fit in a long.

Constraints

  • lows will contain between 1 and 50 elements inclusive
  • highs will contain the same number of elements as lows
  • lexPos will be between 0 and (2^63)-1 inclusive
  • lexPos will contain only digits (0-9), will not have extra leading zeros, and will not contain whitespace
  • lexPos will contain between 1 and 50 characters inclusive
  • retInts will contain between 1 and 50 elements inclusive
  • Each element of lows will be between -2^31 and (2^31)-1 inclusive
  • Each element of highs will be between -2^31 and (2^31)-1 inclusive
  • Element k of lows will not be greater than element k of highs
  • No two ranges will overlap
  • Each element of retInts will contain only digits (0-9), will not have extra leading zeros, and will not contain whitespace
  • Each element of retInts will contain between 1 and 50 characters inclusive
  • Each element of retInts will be between 0 and tot-1 inclusive, where tot is the total amount of numbers in all ranges combined

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{1}
{4}
"0"
{"0","1","2","3"}
Returns: { 1,  2,  3,  4 }

The 0th permutation lexicographically is the sequence 1,2,3,4.

1)
{1}
{3}
"5"
{"0","1","2"}
Returns: { 3,  2,  1 }

The 6 possible permutations, in order, are : 0) 1, 2, 3 1) 1, 3, 2 2) 2, 1, 3 3) 2, 3, 1 4) 3, 1, 2 5) 3, 2, 1 lexPos is 5 so you return the 0th, 1st, and 2nd elements of permutation 5

2)
{1,16}
{5,20}
"1000000"
{"0","1","2","3","4","5","6","7","8","9","1","2","3"}
Returns: { 3,  18,  19,  4,  20,  2,  16,  17,  1,  5,  18,  19,  4 }

Notice the repeated elements in retInts

3)
{1}
{5}
"100000000000001"
{"0","1","2","3","4"}
Returns: { 2,  4,  5,  3,  1 }

lexPos is very big.

4)
{-1000000000,500000}
{0,2000000000}
"99999999999999999"
{"2999500000","1234123","123344","9293939","2999500001","2999499950"}
Returns: { 1999999987,  -998765877,  -999876656,  -990706061,  1999999982,  1999999949 }

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

Coding Area

Language: C++17 · define a public class PermutationValues with a public method vector<int> getValues(vector<int> lows, vector<int> highs, string lexPos, vector<string> retInts) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous