Statistics

Problem Statement for "TupleLine"

Problem Statement

An "n-dimensional grid of size k" contains k^n cells. Each cell can be represented as an n-tuple of values from the set {0,1,...,k-1}. For example a 2-dimensional grid of size 3 is just a 3 x 3 square, with cells (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) and (2,2). A 3-dimensional grid of size 5 is a cube containing 125 cells. Cell (0,2,2) is the cell in row 0, column 2, layer 2.

Higher dimensions get a little harder to describe geometrically, but not algebraically! Every cell in an n-dimensional grid can be uniquely represented by an n-tuple specifying the "row" "column" "layer" "plane" "hyper-row" etc. (English fails us at about the same point as geometry fails us). We can define a straight line in an n-dimensional grid algebraically. It is a set of distinct cells that can be placed in a sequence such that the difference between each pair of adjacent cells is the same throughout the sequence. Of course, the difference between two n-tuples is an n-tuple. A maximal line in an n-dimensional grid of size k is a line containing k cells.

In a 3-dimensional grid of size 4, one example of a maximal straight line is (3,0,1),(2,1,1),(1,2,1),(0,3,1) which is a straight line of length 4. The difference between each pair of adjacent cells in the sequence is (-1,1,0).

You want to create a maximal line in your n-dimensional grid by adding to a collection of cells that have already been chosen. Create a class TupleLine that contains the method quickLine that takes an int size and a String[] chosen as inputs and returns the smallest number of additional cells that you could choose to form a maximal line in the grid.

Each String in chosen is a sequence of digits indicating a particular cell. For example, "410" would indicate the cell at row 4, column 1, layer 0 in a 3-dimensional grid whose size is at least 5 (since it has a row 4). The dimension of the grid is always the same as the length of each String in chosen.

Definition

Class:
TupleLine
Method:
quickLine
Parameters:
int, String[]
Returns:
int
Method signature:
int quickLine(int size, String[] chosen)
(be sure your method is public)

Constraints

  • size is between 3 and 9 inclusive
  • chosen contains between 1 and 50 elements inclusive
  • each character in each element of chosen is a digit whose value is less than size
  • each element in chosen contains the same number of characters, n. n is the dimension of the grid and is between 2 and 9 inclusive

Examples

  1. 4

    {"00","02","21"}

    Returns: 2

    X - X - X X X X - - - - - - - - - X - - - X - - - - - - - - - - The left-hand picture shows the original situation. The right-hand picture shows the only way of completing a maximal line by adding two X's.

  2. 4

    {"00","32","21","32"}

    Returns: 3

    X - - - - - - - - X - - - - X - There are lots of ways to form a maximal line with 3 more cells. Note that the cell "32" appears twice in chosen but, of course, this does not help us to form a maximal line.

  3. 3

    {"0022","0202","0112","0000","0112"}

    Returns: 0

    These first three cells already form a maximal line in this 4-dimensional grid.

  4. 3

    {"10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10","10"}

    Returns: 2

  5. 9

    {"010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000000","010000003","010000000","010000000","010000000","010000000"}

    Returns: 7

  6. 9

    {"3658","5638","1234","8608"}

    Returns: 6

  7. 9

    {"2355846","6355842","3355848"}

    Returns: 7

  8. 5

    {"333333","313331","343334","303334"}

    Returns: 2

  9. 5

    {"131","222","133","044"}

    Returns: 2

  10. 7

    {"133","400","044","222","311","421","422"}

    Returns: 5

  11. 9

    {"8211","8011","7011","8811","6211","6112","3123","3333"}

    Returns: 6

  12. 8

    {"611613","677013","655213","633413","611713","611213","777777"}

    Returns: 4

  13. 8

    {"30434","44552","01475","65111","66405","12653","43712","35626","52244","46636","74302","01500","24045","74727","74640","12365","37017","07734","47464","70624"}

    Returns: 7

  14. 8

    {"424","710","747","144","465","405","605","053","541","232","515","503","003","473","002","711","742","753","563","313","200","032","670","441","515","707","603","620","671","265","337","057","461","650","411","101","226","217","640","113","721","714","630","676","112","636","747","277","026","737"}

    Returns: 3

  15. 7

    {"0100","0100","0100","0100"}

    Returns: 6

  16. 5

    {"4014","3443","2334","2013","1303","1310","3030","3134","4124","3244","2314","2403","2042","4113","3032","3440","3134","3440","1021","0322","3030","3242","4412","0100","2231","4000","0223","1441","2413","2110","3022","2244","4132","0203","4141","2213","0022","0331","4020","4323","4310","2041","2322","3304","0343","2030","0223","3204","3342","0123"}

    Returns: 2

  17. 7

    {"2345","0345","6323","6360","6345","6060"}

    Returns: 4

  18. 5

    {"14131202", "14434112", "23240443", "03312340", "41221324", "22111214", "31410412", "40303044"}

    Returns: 4

  19. 3

    {"12220", "12100", "01102", "10011"}

    Returns: 2

  20. 3

    {"1000000", "1012020", "1211121", "1222202", "1111221", "0121222", "2000011", "2200111", "1211000", "1110000", "1000012", "1210212", "0200020", "1210201", "1201112", "2101020", "2010210", "0002020", "2200211", "2200211"}

    Returns: 1

  21. 4

    {"002302031", "322013003", "220330010", "230111131", "320121331", "303321203", "032221321", "002303302", "003101230", "012102301", "213301011", "123331011", "221312120", "133321221", "031122013", "330231223", "101233112", "132011232", "123313023", "023012003", "300221001", "010221222", "133112112", "121101123", "210012023", "131312001", "132233033", "000210013", "123331300", "111011310", "201020033", "201321033", "121003212", "010132232", "330303300", "033130121", "021311120", "312201223", "131310311", "022222233", "320211013", "110021300", "133213101", "130202301", "131301123", "131323112", "230333322", "332230333", "012202223", "120020000"}

    Returns: 3

  22. 5

    {"132", "411", "202", "204", "230", "120", "304", "134", "101", "430", "343", "012", "241", "320", "441", "324", "224", "313", "213", "312", "343", "212", "232", "310", "124", "413", "424", "032", "403"}

    Returns: 1

  23. 4

    {"03123", "31231", "32132", "33212", "30223", "30333", "00230", "13210", "33201", "03302", "11012", "13232", "20221"}

    Returns: 2

  24. 7

    {"54", "12", "11", "03", "25", "32", "44", "11", "22"}

    Returns: 4

  25. 3

    {"20112222", "20222202", "20121101", "12110022", "10101011", "22011111", "00020010", "11211110", "11020000", "11012221", "11220002", "11011012", "00202120", "22111102", "11220200", "10220100", "21021012", "22022122", "12201120", "02121021", "11102000", "11012110", "21221111", "21002220", "22220012", "01221220", "20202212", "20111201", "02220002", "22110110", "21102010", "00011202", "12200212", "00011002", "01202011", "00000012", "21011101", "12012021", "20121210", "12120101", "02010210", "20022101", "10122211", "02021210", "22200122", "11021202", "21200010", "11000220"}

    Returns: 1

  26. 9

    {"817153", "623880", "772847", "606331", "110557", "807038", "531800", "643667", "853056", "101750", "701117", "366737", "008845", "115213", "856856", "004374", "327615", "726756", "626747", "812865", "826236", "602341", "708758", "262260", "283235", "266255", "881185", "272718", "886520", "028632", "176618", "642768", "403341", "323027", "454115", "786031", "312221", "736033", "631047", "621208", "141536", "414070"}

    Returns: 7

  27. 5

    {"2300343", "0440210", "4434200", "2030031", "0334024", "3214231", "4200411", "2331142", "0212033", "3023243", "0131340", "4204130", "1123324", "1402143", "1131143", "4422120", "1210412", "3222444", "4020434", "2142124", "0403424", "4401042", "3340113", "0110044", "3224012", "2420313", "0312144", "3041141", "0030331", "4020041", "2310202", "4010003", "3121321", "3043031", "4340303", "2222304", "0130443", "0023141", "0102042", "3204413", "3441244", "0103144", "1331021", "2241114", "0314413", "0443443", "0224334", "2033404", "3020022", "3003433"}

    Returns: 4

  28. 8

    {"4406514", "4001746", "3107072", "1661565", "6350146", "5461514", "4160516", "6175525", "0163767", "5542015", "2042114", "3540265", "6405212", "2125302", "0036052", "7513235", "6547230", "2343057", "6505074", "2223417", "1235507", "3462501", "3225561", "4664226", "0742444", "2405672", "1510445", "3335261", "2312121", "7557727", "3122412", "4525103", "1561651", "7422220", "4565754", "1514726", "0267665", "2644372", "7614367"}

    Returns: 7

  29. 9

    {"13", "42", "64", "36", "46", "74", "73", "32", "45", "37", "15", "80", "84", "55", "68", "54", "20", "28", "78", "24", "55", "31", "43", "01", "47", "18", "64"}

    Returns: 4

  30. 6

    {"1005", "3203", "4510", "3521", "3202", "5301", "4424"}

    Returns: 4

  31. 4

    {"32203122", "03003201", "11231030", "21231102", "30122301", "23331220", "22122331", "11120300", "31101120", "23002313", "32312111", "02113010", "03123321", "30001012", "30321323", "20332312", "03003101", "22112131", "11320031", "31220002", "31033200", "11321103", "10212133", "22331033", "02200121", "00002222", "22323123", "31330120", "10030123", "20203013", "30011320", "31130133", "20021101", "03331221", "00103003", "33003011", "20203220", "22100022", "30003121", "11102203", "32311202", "03230103", "23331010", "03211301", "11233011", "00301223", "20201300"}

    Returns: 2

  32. 6

    {"05", "15", "14", "53", "12", "21", "24", "14", "03", "31", "11", "05", "03", "00", "10", "13", "01", "44", "24", "40", "00", "15", "25", "23", "54", "05", "02", "02", "42", "05", "50", "00", "34", "40", "22", "10"}

    Returns: 0

  33. 6

    {"234413420", "055322430", "004322022", "320244131", "054315503", "524013544", "324045021", "004520002", "301244423", "055225311", "202413140", "214304322", "133515012", "554023213", "135422444", "143315512", "412021020", "145542251", "553131305", "343200411"}

    Returns: 4

  34. 3

    {"011", "020", "020", "110", "220", "002", "201", "121", "012", "020", "111", "100", "210", "001", "222", "212", "210", "111", "102", "022", "120", "202", "220", "022", "220"}

    Returns: 0

  35. 4

    {"323201101", "002113330", "000321320", "333000322", "123010332", "013031033", "103213120", "102020231", "003311300", "300300021", "303220211", "200021313", "022010200", "022101031", "123222203", "221220021", "223112331", "021333211", "031330133", "231230122", "311000212", "003222221", "222103232", "003031322", "002201212", "303333100", "320113301", "213212001", "023310333", "133331111", "322132301", "122201312", "110223313", "200123313", "112113310", "010000203"}

    Returns: 2

  36. 8

    {"343656533", "353403062", "660773010", "325054323", "504152740", "722026611", "577775314", "627677225", "335557534", "402212704", "543110377", "241532502", "556476516", "573745274", "427354707", "362523310", "337635206", "531116146", "207166737", "170072465", "033344325", "072460037", "716347642", "626342136", "513260757", "200746076", "623632604", "225304567", "310612730", "103623227", "711373345", "464757013", "123734021", "234317267"}

    Returns: 7

  37. 4

    {"03", "22", "02", "30", "31", "00", "20", "32", "03", "30", "20", "02", "33", "10", "03", "03", "01", "01", "22", "22", "01", "33", "13", "31", "21", "11", "33", "01", "20", "03", "02", "10", "31", "11", "12", "33", "00", "23", "10", "20", "02", "12", "12", "32"}

    Returns: 0

  38. 4

    {"0002320", "3301210", "2113200", "3003113", "3331001", "0112130", "0222303", "3333310", "2123332", "1311313", "3322033", "2102202", "1230100", "0312223"}

    Returns: 3

  39. 9

    {"035364661", "360740734", "344418071", "620731104", "784366812", "721244477", "002155203", "210614815", "032680702", "144724162", "201746051", "757051161", "861086110", "546537341", "336343477", "363223421", "410848555", "801063616", "503735370", "758885674", "635341504", "133053038", "380062775", "208613257", "057425414", "752734336", "806717348", "333712662", "350522537", "123034255", "654813064", "153116811", "402158717", "406331613", "327664566", "307121552"}

    Returns: 8

  40. 5

    {"42222043", "22030011", "30300021", "12210300", "11234004", "04313043", "03014412", "33402331", "12312244", "23330024", "33104134", "31133024", "00221233", "34340342", "03101441", "44341102", "21404123", "01443023", "04112343", "04310432", "01302013", "32312100", "13201031", "04424131", "30022422", "03403203", "44234131", "11114031", "22212111", "32412011", "40234344", "22022113", "41110040", "00132311", "24023303", "10031443", "13342223", "32411304", "32042431", "14124102", "41312030", "22400421"}

    Returns: 4

  41. 3

    {"21211112", "10110111", "10120220", "11111122", "12011012", "01000011", "00021110", "11000002", "12200210", "20110010", "10010001", "11102102", "00012002", "00112100", "12100000", "01211000", "22120222", "12121102", "20112111", "12012221", "02100122", "11020211", "00000121", "21002022", "01120122", "21101221", "02201110", "20011000", "21200102", "02002002", "02121021", "22122220", "10011121", "20111211", "01222221", "10211222", "01211020", "21220211", "22102111", "12212201", "02110120", "01120021", "20101012", "20111012"}

    Returns: 1

  42. 9

    {"666778465", "516863770", "610423068", "140817663", "785462045", "612162525", "223474574", "877818805", "150308336", "738411760", "817571524", "318242543"}

    Returns: 8

  43. 9

    {"35"}

    Returns: 8

  44. 7

    {"16"}

    Returns: 6

  45. 8

    {"77", "57", "61", "47", "17", "70", "31", "52", "62", "70", "25", "32", "21", "32", "67", "16", "44", "61", "67", "50", "15", "70", "21", "32", "75", "17", "51", "32", "64", "24", "41", "34", "73", "17", "32", "23"}

    Returns: 2

  46. 5

    {"0011104", "1100440"}

    Returns: 4

  47. 9

    {"7166277", "5551533", "6018686", "3131518", "4687705", "5008180", "0726523", "3820827", "6428751", "6604210", "6538087", "3255354", "8223041", "3067668", "0323840", "8852481", "8701446", "4588015", "3857538", "5412122", "3151838", "8661176", "2178704"}

    Returns: 8

  48. 6

    {"545505014", "523112003", "023433502", "244140423"}

    Returns: 5

  49. 8

    {"1307757", "6745747", "5577354", "0723136", "2510021", "5760766", "0125435", "3026214", "2240125", "2546547", "2127416", "4317373", "5717406", "0635261", "2607404", "7041515", "3402124", "5360737", "6442326", "2561073", "6776115", "0071124", "1436741", "2175377", "3462461", "3744434", "7544736", "7272376", "1242141", "3776707"}

    Returns: 7

  50. 7

    {"255560533", "652213412", "200415430", "301301053", "622621535", "501003303", "335235143", "524302113", "136665634", "634042412", "122103426", "642350155", "431211460", "101026253", "315654155", "422556423", "100160340"}

    Returns: 6

  51. 3

    {"20201", "02122", "01222", "12212", "10020", "20000", "12111", "21220", "20021", "02202", "02101", "11000", "02011", "22111", "01211", "02220", "00122", "20021", "00210", "12122", "00202", "20120", "20102", "22210", "22222", "10011", "11222", "10200", "01110", "12221", "11221", "21012", "02110"}

    Returns: 0

  52. 4

    {"13131", "00132", "11110", "20131", "32330", "03222", "10203", "01002", "02110", "20311", "13002", "12023", "03023", "13231", "31320", "10022", "21010", "12123", "02210", "02323", "13321", "02123"}

    Returns: 2

  53. 9

    {"407160", "236117", "214267", "827525", "218206", "624104", "012043", "306515", "283456", "214086", "287368", "288568", "434164", "167722", "761675", "304640", "548663", "505501", "527064", "002883", "015717", "623314", "773885", "227785", "727237", "726637", "642845", "108747", "582535", "487471", "587827", "378401", "332205", "845548", "856684", "212646", "721426", "226040", "752561"}

    Returns: 8

  54. 3

    {"10", "12", "01", "21", "21", "01", "12", "21", "12", "22", "12", "10", "00", "22", "00", "22", "20"}

    Returns: 0

  55. 4

    {"2330132", "0120102", "3020300", "2130111"}

    Returns: 3

  56. 6

    {"54", "02", "14", "13", "00", "40", "55", "22", "24", "12", "30", "22", "24", "25", "02", "30", "02", "15", "21", "25", "04", "12", "35", "13", "12", "44", "00", "22", "05", "44", "54", "30", "04", "43", "12", "41", "50", "25"}

    Returns: 1

  57. 8

    {"0555145", "6206431", "0122275", "5060762", "2321644", "0502611", "7566142", "3074103", "6114217", "1402741", "4002701", "6117602", "2244403", "2354344", "0053037", "3327406", "4401525", "1627660", "2773760", "1422052", "2776103", "6416106"}

    Returns: 7

  58. 9

    { "2355846", "6355842", "3355848" }

    Returns: 7

  59. 3

    { "0022", "0202", "0112", "0000", "0112" }

    Returns: 0

  60. 8

    { "00" }

    Returns: 7

  61. 3

    { "00", "01", "11" }

    Returns: 1

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: