TopCoder problem "GetSubsequence" used in TCO05 Round 4 (Division I Level Three)



Problem Statement

    Given a String s, we will first collect all distinct positive length subsequences of s, and place them in a list L. A subsequence of s is obtained by deleting 0 or more characters. Next, sort L into ascending order by length. Where ties occur, break them lexicographically. Here uppercase letters occur before lowercase letters. Finally, return the String in position pos % k (0-based), where k is the number of elements in L, and % is the modulus operator.
 

Definition

    
Class:GetSubsequence
Method:getAt
Parameters:String, String
Returns:String
Method signature:String getAt(String s, String pos)
(be sure your method is public)
    
 

Constraints

-s will contain between 2 and 50 characters inclusive.
-Each character in s will be a letter ('A'-'Z','a'-'z').
-pos will be an integral value between 0 and 2^63 - 1 inclusive.
-pos will not have extra leading zeros.
 

Examples

0)
    
"ABCD"
"14"
Returns: "ABCD"
"ABCD" is the last of the 15 subsequences in L.
1)
    
"ABCD"
"19203410239121"
Returns: "ABD"
19203410239121 % 15 = 11.
2)
    
"AAAAAAAAAAAA"
"10"
Returns: "AAAAAAAAAAA"
3)
    
"AbcdAbcdAbcd"
"39283423984923"
Returns: "AbAbdbd"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3053

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8036&pm=3053

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Dynamic Programming