HorseTicket | Topcoder Archive

Problem Statement

A horse racing event typically consists of several races, each of which contains several horses. Fans bet on one or more races, attempting to predict who will win each one. Each race has at least one horse, and no horse will run more than one race on a given day.

In this problem, there are 62 horses. They are represented by all possible letters and digits: 'A'-'Z', 'a'-'z', and '0'-'9'.

You are given String[] races, each element representing the lineup of one of the races. For example, if races[0] = "AbX3", the horses who will take part in race 0 are 'A', 'b', 'X', and '3'.

A valid ticket has the following properties:

The ticket is a string of characters that represent horses. (The horses on the ticket do not have to be in the same order as the races they appear in.)
Each horse on the ticket is actually racing that day.
No horse is repeated on the ticket.
No more than one horse is selected from each race.

Clearly, there is only a finite number of different valid tickets. Internally, each ticket is represented by a non-negative integer: its 0-based index in the lexicographically sorted list of all valid tickets.

Given the long index, return the ticket it represents, or "!" if there is no ticket with the given index.

Definition

Class:: HorseTicket
Method:: getTicket
Parameters:: String[], long
Returns:: String
Method signature:: String getTicket(String[] races, long index)
(be sure your method is public)

Notes

We use standard ASCII values for the lexicographical sorting: digits are before uppercase letters, which are before lowercase letters.
If string A is a prefix of string B, then A comes before B in lexicographic order.

Constraints

races will be non-empty.
Each element of races will only contain letters and digits ('A'-'Z', 'a'-'z', '0'-'9').
Each element of races will be non-empty.
No character will be repeated in races.
index will be between 0 and 10^15, inclusive.

Examples

```
{"B", "A"}
```
```
4
```
```
Returns: "BA"
```
All valid tickets, in order, are "", "A", "AB", "B", "BA".
```
{"B", "A"}
```
```
6
```
```
Returns: "!"
```
There is no ticket number 6 - as we saw in the previous example, the valid ticket numbers for these races are only 0 through 4.
```
{"ace","bhg","fdz"}
```
```
47
```
```
Returns: "bz"
```
The nearby tickets are 42=bez, 43=bf, 44=bfa, 45=bfc, 46=bfe, 47=bz, 48=bza, 49=bzc, 50=bze, 51=c.

{"Top","C0Der","1s","fun"}

Returns: "Cup1"

{"q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m"}

1000000000000000

Returns: "abcdefghjitoxyzrwqsmpvuln"

Here, the valid tickets are simply all strings of distinct lowercase letters.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.