Statistics

Problem Statement for "AssignLabels"

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.

Definition

Class:
AssignLabels
Method:
assign
Parameters:
int, int[]
Returns:
String[]
Method signature:
String[] assign(int N, int[] order)
(be sure your method is public)

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

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

  2. 5

    {4, 3, 2, 1, 0}

    Returns: {"but", "bot", "bit", "bet", "bat" }

  3. 1

    {0}

    Returns: {"topcodersrm" }

  4. 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" }

  5. 2

    {1,0}

    Returns: {"ab", "aa" }

  6. 2

    {0,1}

    Returns: {"aa", "ab" }

  7. 196

    {42,94,41,96,168,89,37,149,19,164,47,26,172,6,154,151,170,16,138,25,22,33,166,144,103,0,155,131,110,126,81,128,145,58,150,146,120,195,129,56,101,39,9,79,14,158,87,61,114,70,78,3,2,35,36,90,159,21,124,105,63,117,119,102,185,11,60,62,104,64,112,29,65,107,148,153,20,121,133,67,69,30,76,136,75,135,50,97,77,7,191,100,111,157,12,66,182,118,116,125,40,192,8,88,68,193,169,183,95,175,142,171,141,45,190,162,85,72,194,106,32,46,189,23,15,167,122,51,181,147,160,48,99,71,163,140,115,53,186,54,49,143,73,123,86,127,91,82,156,84,187,93,130,38,177,184,173,17,55,13,134,44,92,161,108,180,165,176,188,27,139,109,98,10,28,137,5,132,179,74,59,174,152,34,83,43,1,80,52,113,18,57,31,178,24,4}

    Returns: {"az", "he", "ca", "bz", "hn", "gu", "an", "dl", "dy", "bq", "gr", "cn", "dq", "gd", "bs", "eu", "ar", "gb", "hi", "ai", "cy", "cf", "au", "et", "hm", "at", "al", "gn", "gs", "ct", "dd", "hk", "eq", "av", "hb", "cb", "cc", "ag", "fx", "bp", "dw", "ac", "aa", "hd", "gf", "ej", "er", "ak", "fb", "fk", "di", "ex", "hg", "fh", "fj", "gc", "bn", "hj", "bh", "gy", "co", "bv", "cp", "ci", "cr", "cu", "dr", "db", "ea", "dc", "bx", "fd", "en", "fm", "gx", "dg", "de", "dk", "by", "br", "hf", "be", "fr", "hc", "ft", "em", "fo", "bu", "dz", "af", "cd", "fq", "gg", "fv", "ab", "ee", "ad", "dj", "gq", "fc", "dn", "bo", "cl", "ay", "cq", "ch", "ep", "cv", "gi", "gp", "bc", "do", "cs", "hh", "bw", "fg", "du", "cj", "dt", "ck", "bk", "cz", "ew", "fn", "cg", "dv", "bd", "fp", "bf", "bm", "fw", "bb", "gv", "da", "ge", "dh", "df", "gt", "as", "go", "ff", "ei", "eg", "fl", "ax", "bg", "bj", "ez", "cw", "ah", "bi", "ap", "ha", "cx", "ao", "ba", "fs", "dp", "bt", "ce", "fa", "gh", "el", "fe", "aj", "gk", "aw", "ev", "ae", "ec", "aq", "eh", "am", "ga", "gz", "ef", "gl", "fy", "hl", "gw", "gj", "ey", "ds", "ed", "fz", "cm", "fi", "fu", "gm", "es", "ek", "dm", "dx", "eb", "eo", "bl" }

  8. 197

    {194,174,123,28,171,83,122,153,50,196,15,73,131,87,134,186,121,57,2,69,10,162,179,144,143,103,41,21,120,124,59,150,82,158,17,173,190,98,25,136,36,135,157,4,18,35,80,45,64,60,99,126,167,46,7,113,49,16,176,189,53,30,81,6,138,32,152,77,58,56,188,178,149,52,37,33,90,44,72,47,195,94,5,93,39,151,115,68,112,169,42,105,29,111,54,148,110,89,159,1,118,55,91,161,71,11,27,48,96,155,193,13,133,3,26,14,145,19,166,109,22,141,85,177,129,43,154,74,181,9,127,184,142,172,78,104,61,164,139,119,20,183,156,117,168,128,137,165,101,107,84,40,180,125,106,108,79,76,63,192,67,65,95,31,146,191,97,175,75,8,185,38,163,92,100,116,88,12,132,34,130,114,170,70,86,51,102,23,140,0,160,182,24,187,66,147,62}

    Returns: {"hh", "dv", "as", "ej", "br", "de", "cl", "cc", "gn", "ez", "au", "eb", "gv", "eh", "el", "ak", "cf", "bi", "bs", "en", "fk", "bb", "eq", "hf", "hk", "bm", "ek", "ec", "ad", "do", "cj", "gh", "cn", "cx", "gx", "bt", "bo", "cw", "gp", "dg", "fv", "ba", "dm", "ev", "cz", "bv", "cb", "db", "ed", "ce", "ai", "hd", "cv", "ci", "dq", "dx", "cr", "ar", "cq", "be", "bx", "fg", "ho", "gc", "bw", "gf", "hm", "ge", "dj", "at", "hb", "ea", "da", "al", "ex", "gm", "gb", "cp", "fe", "ga", "bu", "ck", "bg", "af", "fu", "es", "hc", "an", "gu", "dt", "cy", "dy", "gr", "df", "dd", "gg", "ee", "gk", "bl", "by", "gs", "fs", "he", "az", "ff", "dn", "fy", "ft", "fz", "ep", "ds", "dp", "dk", "cd", "gz", "di", "gt", "fn", "dw", "fj", "bc", "aq", "ag", "ac", "bd", "fx", "bz", "fa", "fp", "eu", "gy", "am", "gw", "ei", "ao", "bp", "bn", "fq", "cm", "fi", "hg", "er", "fc", "ay", "ax", "em", "gi", "hn", "dr", "cu", "bf", "dh", "co", "ah", "ew", "ef", "fm", "bq", "bh", "du", "hi", "dz", "av", "gq", "fh", "fr", "eo", "ca", "fo", "dl", "ha", "ae", "fd", "bj", "ab", "gl", "cg", "et", "ct", "aw", "fw", "ey", "hj", "fl", "fb", "go", "ap", "hl", "cs", "ch", "bk", "gj", "gd", "eg", "aa", "dc", "aj" }

  9. 198

    {61,179,187,156,165,9,190,83,191,107,130,54,44,150,88,118,49,48,35,23,108,123,51,75,140,135,57,117,14,116,98,170,132,193,153,115,63,86,4,77,171,78,38,129,31,183,16,176,24,8,175,58,178,30,136,181,137,17,69,5,158,128,105,122,146,186,121,177,166,138,101,50,13,141,85,59,155,41,196,64,185,0,111,81,133,55,71,33,188,149,104,174,47,80,169,119,180,182,163,113,68,22,91,6,84,94,197,45,79,43,27,40,60,125,93,144,56,82,1,73,10,120,110,161,72,96,106,97,11,29,15,192,151,39,2,92,159,67,112,160,189,74,25,36,26,157,100,90,95,76,167,194,145,42,139,147,173,162,12,102,46,168,65,131,154,126,134,19,103,184,62,172,37,124,87,114,20,143,18,109,21,28,164,34,99,127,66,3,152,89,52,142,148,70,32,53,7,195}

    Returns: {"dd", "eo", "fe", "hf", "bm", "ch", "dz", "ho", "bx", "af", "eq", "ey", "gc", "cu", "bc", "fa", "bu", "cf", "gw", "gl", "gu", "gy", "dx", "at", "bw", "fm", "fo", "eg", "gz", "ez", "cb", "bs", "hm", "dj", "hb", "as", "fn", "gq", "bq", "fd", "eh", "cz", "fx", "ef", "am", "ed", "ge", "do", "ar", "aq", "ct", "aw", "hi", "hn", "al", "dh", "em", "ba", "bz", "cx", "ei", "aa", "go", "bk", "db", "gg", "he", "fh", "dw", "cg", "hl", "di", "eu", "ep", "fl", "ax", "ft", "bn", "bp", "ee", "dp", "df", "en", "ah", "ea", "cw", "bl", "gs", "ao", "hh", "fr", "dy", "ff", "ek", "eb", "fs", "ev", "ex", "be", "hc", "fq", "cs", "gd", "gm", "dm", "ck", "ew", "aj", "au", "gx", "es", "de", "fi", "dv", "gt", "bj", "bd", "bb", "ap", "dr", "er", "co", "cl", "av", "gr", "ej", "gj", "hd", "cj", "br", "ak", "gh", "bg", "dg", "gk", "az", "cc", "ce", "cr", "fy", "ay", "cv", "hj", "gv", "el", "fw", "cm", "fz", "hk", "dl", "an", "fc", "hg", "bi", "gi", "cy", "ad", "fp", "ci", "fg", "fj", "et", "gb", "du", "ha", "ae", "cq", "fu", "gf", "dq", "bf", "bo", "gp", "ga", "dn", "by", "bv", "cp", "ca", "ab", "ds", "cd", "dt", "bt", "gn", "dc", "cn", "ac", "dk", "fk", "ag", "ai", "fb", "bh", "fv", "hp", "da", "ec" }

  10. 199

    {194,112,145,25,62,15,33,117,175,56,51,64,118,164,192,14,36,21,129,131,153,30,12,152,18,98,70,72,31,180,3,197,147,111,132,11,1,57,9,86,0,80,76,123,34,105,71,179,45,157,163,94,158,46,52,42,5,97,2,134,6,75,188,196,168,65,171,68,116,81,113,128,99,63,148,43,120,24,19,133,77,82,17,184,93,170,102,121,135,35,37,144,161,136,137,83,104,44,79,178,124,155,140,183,108,141,22,142,85,126,114,182,185,39,190,40,193,176,159,41,78,60,53,10,101,181,49,119,189,151,27,172,32,191,50,110,7,23,154,88,138,26,165,29,58,150,73,48,195,107,66,100,90,16,115,174,8,59,28,96,55,67,122,91,61,95,38,187,173,47,169,4,20,89,139,143,149,167,109,84,177,106,160,166,13,198,127,125,87,186,156,69,146,103,92,130,54,162,74}

    Returns: {"bo", "bk", "cg", "be", "gp", "ce", "ci", "fg", "ga", "bm", "et", "bj", "aw", "hc", "ap", "af", "fx", "de", "ay", "da", "gq", "ar", "ec", "fh", "cz", "ad", "fl", "fa", "gc", "fn", "av", "bc", "fc", "ag", "bs", "dl", "aq", "dm", "gk", "ej", "el", "ep", "cd", "cx", "dt", "bw", "cb", "gn", "fr", "ew", "fe", "ak", "cc", "es", "ho", "ge", "aj", "bl", "fo", "gb", "er", "gi", "ae", "cv", "al", "cn", "fu", "gf", "cp", "hj", "ba", "bu", "bb", "fq", "hq", "cj", "bq", "dc", "eq", "du", "bp", "cr", "dd", "dr", "gx", "ee", "bn", "hg", "fj", "gr", "fw", "gh", "hm", "dg", "bz", "gj", "gd", "cf", "az", "cu", "fv", "eu", "di", "hl", "ds", "bt", "gz", "ft", "ea", "gw", "ff", "bh", "ab", "cs", "eg", "fy", "cq", "ah", "am", "ex", "cy", "dj", "gg", "br", "dw", "hf", "ef", "he", "ct", "as", "hn", "at", "bi", "db", "ch", "dk", "dp", "dq", "fk", "gs", "dy", "eb", "ed", "gt", "dn", "ac", "hk", "bg", "cw", "gu", "fp", "ez", "ax", "au", "fi", "dx", "hi", "bx", "ca", "eo", "ha", "do", "hp", "by", "an", "fm", "hb", "gv", "cm", "go", "dh", "co", "fb", "gm", "fz", "ai", "en", "gy", "dv", "bv", "bd", "ev", "eh", "dz", "df", "ei", "hh", "gl", "ck", "ey", "ek", "fd", "ao", "em", "aa", "fs", "cl", "bf", "hd" }

  11. 200

    {70,175,160,78,192,58,106,128,184,99,125,48,110,170,56,45,5,23,24,129,178,136,34,171,6,61,157,3,71,147,97,167,4,145,32,135,198,181,30,100,89,151,134,104,156,92,7,144,122,159,96,126,93,12,53,52,191,116,10,194,16,37,138,69,13,82,41,35,40,25,42,59,79,119,28,9,155,90,64,101,179,2,57,172,112,107,18,87,153,130,132,193,177,21,29,190,161,63,88,83,1,62,154,36,186,43,163,141,114,139,113,65,118,8,185,67,68,152,111,169,0,133,76,150,120,80,142,182,33,123,22,124,103,117,84,173,54,26,27,115,85,162,11,72,189,195,47,168,164,49,77,165,17,31,14,158,180,176,38,50,98,95,143,19,75,66,146,55,108,127,140,183,188,137,102,149,86,199,94,148,15,39,196,20,73,131,60,81,174,187,105,109,121,44,46,197,74,91,51,166}

    Returns: {"eq", "dw", "dd", "bb", "bg", "aq", "ay", "bu", "ej", "cx", "cg", "fm", "cb", "cm", "fy", "gy", "ci", "fw", "di", "gh", "hb", "dp", "fa", "ar", "as", "cr", "fh", "fi", "cw", "dq", "bm", "fx", "bi", "ey", "aw", "cp", "dz", "cj", "gc", "gz", "cq", "co", "cs", "eb", "hl", "ap", "hm", "fq", "al", "ft", "gd", "hq", "cd", "cc", "fg", "gl", "ao", "de", "af", "ct", "he", "az", "dx", "dt", "da", "eh", "gj", "el", "em", "cl", "aa", "bc", "fn", "hc", "ho", "gi", "es", "fu", "ad", "cu", "ev", "hf", "cn", "dv", "fe", "fk", "gu", "dj", "du", "bo", "cz", "hp", "bt", "ca", "gw", "gf", "by", "be", "ge", "aj", "bn", "db", "gs", "fc", "br", "hi", "ag", "dh", "gm", "hj", "am", "eo", "dg", "eg", "ee", "fj", "cf", "fd", "ei", "cv", "eu", "hk", "bw", "ez", "fb", "ak", "bz", "gn", "ah", "at", "dl", "hd", "dm", "er", "bq", "bj", "av", "gr", "ck", "ef", "go", "ed", "ew", "gg", "bv", "bh", "gk", "bd", "gx", "gt", "et", "bp", "en", "dk", "dy", "cy", "bs", "ba", "fz", "bx", "ac", "ds", "fl", "ec", "fs", "fv", "hr", "bf", "fr", "ep", "an", "ax", "df", "ff", "hg", "ab", "gb", "do", "au", "dc", "ga", "bl", "ex", "gp", "ai", "ek", "ea", "hh", "gq", "fo", "dr", "ce", "ae", "dn", "ch", "fp", "ha", "hn", "bk", "gv" }

  12. 5

    {4, 3, 2, 1, 0 }

    Returns: {"but", "bot", "bit", "bet", "bat" }

  13. 200

    {199, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 0 }

    Returns: {"hr", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak", "al", "am", "an", "ao", "ap", "aq", "ar", "as", "at", "au", "av", "aw", "ax", "ay", "az", "ba", "bb", "bc", "bd", "be", "bf", "bg", "bh", "bi", "bj", "bk", "bl", "bm", "bn", "bo", "bp", "bq", "br", "bs", "bt", "bu", "bv", "bw", "bx", "by", "bz", "ca", "cb", "cc", "cd", "ce", "cf", "cg", "ch", "ci", "cj", "ck", "cl", "cm", "cn", "co", "cp", "cq", "cr", "cs", "ct", "cu", "cv", "cw", "cx", "cy", "cz", "da", "db", "dc", "dd", "de", "df", "dg", "dh", "di", "dj", "dk", "dl", "dm", "dn", "do", "dp", "dq", "dr", "ds", "dt", "du", "dv", "dw", "dx", "dy", "dz", "ea", "eb", "ec", "ed", "ee", "ef", "eg", "eh", "ei", "ej", "ek", "el", "em", "en", "eo", "ep", "eq", "er", "es", "et", "eu", "ev", "ew", "ex", "ey", "ez", "fa", "fb", "fc", "fd", "fe", "ff", "fg", "fh", "fi", "fj", "fk", "fl", "fm", "fn", "fo", "fp", "fq", "fr", "fs", "ft", "fu", "fv", "fw", "fx", "fy", "fz", "ga", "gb", "gc", "gd", "ge", "gf", "gg", "gh", "gi", "gj", "gk", "gl", "gm", "gn", "go", "gp", "gq", "gr", "gs", "gt", "gu", "gv", "gw", "gx", "gy", "gz", "ha", "hb", "hc", "hd", "he", "hf", "hg", "hh", "hi", "hj", "hk", "hl", "hm", "hn", "ho", "hp", "hq", "aa" }

  14. 28

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 }

    Returns: {"aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak", "al", "am", "an", "ao", "ap", "aq", "ar", "as", "at", "au", "av", "aw", "ax", "ay", "az", "ba", "bb" }

  15. 27

    {26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }

    Returns: {"ba", "az", "ay", "ax", "aw", "av", "au", "at", "as", "ar", "aq", "ap", "ao", "an", "am", "al", "ak", "aj", "ai", "ah", "ag", "af", "ae", "ad", "ac", "ab", "aa" }

  16. 61

    {2, 3, 4, 5, 6, 7, 8, 9, 0, 10, 11, 12, 13, 14, 1, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }

    Returns: {"ai", "ao", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "aj", "ak", "al", "am", "an", "ap", "aq", "ar", "as", "at", "au", "av", "aw", "ax", "ay", "az", "ba", "bb", "bc", "bd", "be", "bf", "bg", "bh", "bi", "bj", "bk", "bl", "bm", "bn", "bo", "bp", "bq", "br", "bs", "bt", "bu", "bv", "bw", "bx", "by", "bz", "ca", "cb", "cc", "cd", "ce", "cf", "cg", "ch", "ci" }

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.
This problem was used for: