AssignLabels

SRM 830 · 2022-05-27 · by misof

SRM 830 · 2022-05-27 · by misof · Greedy, Sorting, String Manipulation

Show categories

Class Name: AssignLabels

Return Type: String[]

Method Name: assign

Arg Types: (int, vector<int>)

Problem Statement

You have a collection of N objects. The objects have distinct IDs: integers that range from 0 to N-1.

The objects have one specific order, given in the int[] order. The elements of order are the IDs of your objects.

You now want to assign labels to your objects. Each label must be a string of between 1 and 12 lowercase English letters ('a'-'z'). The labels must all be distinct.

The labels must be such that if we sort the objects according to their label, we will get exactly the order given in order.

Find and return any such set of labels. More precisely, the return value of your method should be a String[] with exactly N elements, where element i (0-based index) is the label that should be given to the object with ID i.

Notes

A solution always exists. Any valid solution will be accepted.
When comparing labels, we use the standard lexicographic order: string X is smaller than a different string Y if either (X is a proper prefix of Y) or (the character X[i] is smaller than the character Y[i], where i is the smallest index at which X and Y differ).

Constraints

N will be between 1 and 200, inclusive.
order will have exactly N elements.
Elements of order will be a permutation of 0 to N-1. (I.e., they will all be from the range [0,N-1] and they will be distinct.)

Examples

5
{0, 3, 2, 1, 4}
Returns: {"cat", "monkey", "mongoose", "caterpillar", "zebra" }

According to the given order, object 0 should have the smallest label, object 3 the second smallest one, object 2 should have the middle label, then goes the label of object 1, and finally object 4. Formally: label[0] < label[3] < label[2] < label[1] < label[4]. Our five labels indeed do have this property: "cat" < "caterpillar" < "mongoose" < "monkey" < "zebra".

5
{4, 3, 2, 1, 0}
Returns: {"but", "bot", "bit", "bet", "bat" }

1
{0}
Returns: {"topcodersrm" }

30
{3,0,7,9,4,2,5,6,1,8,13,10,17,19,14,12,15,16,11,18,23,20,27,29,24,22,25,26,21,28}
Returns: {"ab", "ai", "af", "aa", "ae", "ag", "ah", "ac", "aj", "ad", "al", "as", "ap", "ak", "ao", "aq", "ar", "am", "at", "an", "av", "bc", "az", "au", "ay", "ba", "bb", "aw", "bd", "ax" }

2
{1,0}
Returns: {"ab", "aa" }

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

Coding Area

Language: C++17 · define a public class AssignLabels with a public method vector<string> assign(int N, vector<int> order) · 16 test cases · 2 s / 256 MB per case