Connection Status:
Competition Arena > HorseTicket

HorseTicket

TCO20 Round 3B · 2020-04-13 · by misof

TCO20 Round 3B · 2020-04-13 · by misof · Dynamic Programming, Math
Class Name: HorseTicket
Return Type: String
Method Name: getTicket
Arg Types: (vector<string>, long long)
Problem Statement

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.

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
0)
{"B", "A"}
4
Returns: "BA"

All valid tickets, in order, are "", "A", "AB", "B", "BA".

1)
{"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.

2)
{"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.

3)
{"Top","C0Der","1s","fun"}
673
Returns: "Cup1"
4)
{"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.

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

Coding Area

Language: C++17 · define a public class HorseTicket with a public method string getTicket(vector<string> races, long long index) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous