Statistics

Problem Statement for "Revmatching"

Problem Statement

You have a weighted bipartite graph. Each partition contains n vertices numbered 0 through n-1. You are given the weights of all edges encoded into a String[] A with n elements, each containing n characters. For each i and j, A[i][j] is '0' if there is no edge between vertex i in the first partition and vertex j in the second partition. Otherwise, A[i][j] is between '1' and '9', inclusive, and the digit represents the weight of the corresponding edge.

A perfect matching is a permutation p of 0 through n-1 such that for each i there is an edge (of any positive weight) between vertex i in the first partition and vertex p[i] in the second partition.

Your goal is to have a graph that does not contain any perfect matching. You are allowed to delete edges from your current graph. You do not care about the number of edges you delete, only about their weights. More precisely, you want to reach your goal by deleting a subset of edges with the smallest possible total weight. Compute and return the total weight of deleted edges in an optimal solution.

Definition

Class:
Revmatching
Method:
smallest
Parameters:
String[]
Returns:
int
Method signature:
int smallest(String[] A)
(be sure your method is public)

Constraints

  • A will contain exactly n elements.
  • Each element in A will be n characters long.
  • n will be between 1 and 20, inclusive.
  • Each character in A will be between '0' and '9', inclusive.

Examples

  1. {"1"}

    Returns: 1

    There is a single edge. You have to delete it.

  2. {"0"}

    Returns: 0

    There are no edges and therefore there is no perfect matching.

  3. {"44","44"}

    Returns: 8

  4. {"861","870","245"}

    Returns: 6

  5. {"01000","30200","11102","10001","11001"}

    Returns: 0

  6. {"0111101100","0001101001","1001001000","1000100001","0110011111","0011110100","1000001100","0001100000","1000100001","0101110010"}

    Returns: 1

  7. {"65441060903302167490","54584129060537207056","04063109223863893065","32095021935342825271","86692607600049489234","60550452828998606283","93121304050306344633","49755871330285779159","01618175005086510403","31120822471060153329","58647094718671708562","32671323792255313133","75428263005278979250","57998998995496960076","58856145942496846637","20759381082208239849","94280256668006492067","28787496941560369415","33300662832690339459","23731251006225109477"}

    Returns: 58

  8. {"010001","001000","000003","000111","100010","010101"}

    Returns: 1

  9. {"03","12"}

    Returns: 1

  10. {"00","01"}

    Returns: 0

  11. {"130","111","010"}

    Returns: 1

  12. {"000","400","213"}

    Returns: 0

  13. {"0001","0122","0100","1002"}

    Returns: 1

  14. {"0100","1020","0001","0100"}

    Returns: 0

  15. {"02100","10100","01110","00001","00011"}

    Returns: 1

  16. {"301112","000000","100000","020001","011101","121030"}

    Returns: 0

  17. {"1000000","0200011","0000002","0011200","0011000","0000110","0010010"}

    Returns: 1

  18. {"1010201","0110000","0000002","2011031","0100001","2200011","0110000"}

    Returns: 0

  19. {"10100001","00012201","00000001","21010110","10010101","00110000","00001001","00002210"}

    Returns: 1

  20. {"01000001","00010000","00100100","11102120","00011000","00024000","01000024","01401010"}

    Returns: 0

  21. {"000001000","010000100","100100001","210110000","100001010","000000100","000201000","000100010","011010000"}

    Returns: 1

  22. {"001013122","000021000","002220001","010110010","000111000","000000000","111000100","110100000","100102001"}

    Returns: 0

  23. {"0001100201","0000000101","0001200001","0010000011","0000110004","0001000001","2210321001","1000102000","1001010001","1110100210"}

    Returns: 1

  24. {"1010000000","1001000000","0000001010","0000000010","0000100000","0000010000","1000000101","0010011011","1000000021","0000000010"}

    Returns: 0

  25. {"00000001110","12300012001","01000100000","20110000001","01010110000","00201001000","00000011100","00000000001","01000001101","01001100000","01110110000"}

    Returns: 1

  26. {"10000000000","10001000201","10100010010","00101000010","10000101000","10200010000","10000000000","01000111000","00011000000","01200000000","21102100100"}

    Returns: 0

  27. {"000200002010","000100000000","011012000000","100111010020","010001020002","000101000101","100000100001","000000001100","100000000000","000001000000","111101000000","000000001011"}

    Returns: 1

  28. {"010101000321","200000000011","001001000100","100020001010","200011000010","000100001000","000010000010","000002000100","010110000000","000300000100","013010000010","011000110001"}

    Returns: 0

  29. {"0001000000000","0000000000001","1000001000000","0000102000000","0100000001000","0000010101101","0100100001010","1000010100000","0000000001000","0000000000100","0000000020000","0001010000000","1010000000101"}

    Returns: 1

  30. {"0000000200000","0100001000100","0000000100000","0100201000100","0010010211100","0000001010001","0020101000032","1100000000000","2010001100100","0201000001011","1000010001010","0010002000000","0001100020100"}

    Returns: 0

  31. {"00010000010010","10011000001000","11111010000010","00000000000100","00000001103100","00010101200001","02000002011111","00012000100100","00021100010001","01010200000101","00010001011010","10000001000010","01000101001110","00000110101000"}

    Returns: 1

  32. {"11000001110000","10000111000000","00000110011001","10200011110000","00011000110000","11001110100001","00000001000000","00101000010010","01000013000000","01000100000000","00000001000010","00000020001000","00011000002000","00000001010000"}

    Returns: 0

  33. {"001100000011110","010010011100100","101000100000110","000001100000010","000010000000000","000010100111000","100020000101100","001010000000111","110101000200001","000010010100010","111010010000000","010000001000010","002011000001000","000100000000010","001000011101001"}

    Returns: 1

  34. {"000001000010000","001101000002010","000011000000000","030000010000100","110001000100000","000000000000000","010101000010110","100003000000001","000100000000000","200010210001010","100101000100000","000000020000010","100100101100000","000010100000101","000000000001000"}

    Returns: 0

  35. {"0000001001000001","0000001001001101","0000100001010000","0000100002100100","0001001000000110","0000101000000101","0000101000001000","0000000100000000","1100000000010000","1101100010101000","1000010000000000","2001020001000202","0110100002000000","0100001030010000","0010000000210010","1100000001020000"}

    Returns: 1

  36. {"0001001100000000","0000012001000000","0210100000003011","0000001000002000","1001200100000101","1000000020010000","0220010100000012","0010020011002102","0010101000200101","0010010110110011","0110100000001010","0000000000000000","0100001200010110","0000200110211100","0000101100011010","0001011000100001"}

    Returns: 0

  37. {"00020000100100100","10000000000000000","00001100000002101","00001000000001021","10000000000000010","01010000100101001","02000101010110001","00100000000100101","10000000101000000","00100010000000000","00010000000000001","00011000000000000","00000000011010001","00000000001011000","10001100000000100","00000010000100001","10000100000000000"}

    Returns: 1

  38. {"10010010011121001","00130101000000000","01000000000001100","00000010000000000","10010010000000000","00111000000000000","00000000011200001","00010010000010000","00000000100010000","01000000000011100","00010000000000100","00100000100000000","00000000010200001","10001000000000000","11000000000100000","00010100100002001","00010000000100000"}

    Returns: 0

  39. {"200100000200000000","000001000000000000","000000000000110000","000000110011000100","000000100000100000","000000001001001000","001000000000000001","000000000101020100","001000000200000000","000100100000000010","000000000000001100","101000000000100000","000010000100000000","000010000000000010","100000000000000000","011100000000000000","000000000010000000","001000000000111000"}

    Returns: 1

  40. {"001001011000000001","000001001000011010","000000002310000001","011100000011000100","001001000301000001","002100000001000000","000000000000000002","000011101000000000","000101000001111011","001010001000000000","000000000100000110","000000100000010010","000000000000010000","010501201000001000","000000001010000101","010100110100001000","010001000000100010","000000100100011001"}

    Returns: 0

  41. {"0100000000011101000","0111100110001000000","0100011001001010000","0210000000000010000","0000000000000000100","0100010010000000100","0001100001110000000","0000100000010000000","1120000000100000000","0100000000001000010","0000010010000000010","1000100021101001000","1000000100000000010","0000000010100000010","0000000000000000101","0102000001020000000","0110000000001000000","1002110111001011000","2000003100000000000"}

    Returns: 1

  42. {"0100000000100000000","0010000010000001000","0000100000000000100","0100000011000000010","0000000000011011000","0001000011000000000","0000000010010000000","0000010000000000000","0000001001001001001","1000000000000100010","0000001011010000000","0100000000300000000","0000100000010000100","0000001001000100000","1010001010110000000","1200100000000210000","0000001011000000000","0001100001011010200","0000000000000100000"}

    Returns: 0

  43. {"00010000000000100001","00000000211000000010","20110100010000001010","01000000001100001000","00000100010000011000","11000000000000110000","00111001000101000000","00000000001011000001","00000100001101100101","00001000000000001000","00000000100000101000","00110001101000010010","01000111000100000100","01000000002200000000","00010100010000000100","02020000100010000000","10001000100000100000","00011000010001100000","00000000000002000000","10000000002010000000"}

    Returns: 1

  44. {"00011100000010000000","00000000001000010000","10100000001000000010","00000002010000000100","00010000000010010040","00001000000200010020","00100001000000000000","00100000100000000000","00100000000200001010","20000000000100010000","00012200201000100000","00000200110010001400","00000000000000110000","02100000010000000000","00000000001010010000","01010010000110000000","00111110000000000101","10011000100000010100","00000000100010000100","00000000110030100002"}

    Returns: 0

  45. {"756","387","622"}

    Returns: 10

  46. {"014","860","475"}

    Returns: 5

  47. {"2062","3342","0352","5638"}

    Returns: 9

  48. {"86847","61523","08803","81087","37267"}

    Returns: 17

  49. {"112651","420147","754772","816084","810800","378080"}

    Returns: 14

  50. {"8042230","5127104","4182613","4660724","8240578","1855482","6860658"}

    Returns: 16

  51. {"17657677","77848437","66888252","12621114","71543556","21602724","28502835","38856612"}

    Returns: 18

  52. {"382578522","282407262","658832578","318003031","716730676","852844778","100558525","176118512","467317641"}

    Returns: 19

  53. {"8222837365","3315621787","6333604281","3240323233","7628851777","6131380803","7124351028","8310836888","6336733783","4647080200"}

    Returns: 25

  54. {"73828531766","06343837315","37070645634","34454162746","13057600025","83571148281","48124586103","00413728856","56546842015","36340428044","77430608642"}

    Returns: 29

  55. {"757344401448","045021788526","257438631358","405235803880","021500125512","361311025662","087486512853","468434232327","506616537800","410648726505","867556511573","515851111682"}

    Returns: 24

  56. {"0120632076486","3751181020841","4321880781465","8730543653427","7577086878613","1268321060507","7142453741030","2230704253218","0550581336853","5343713126004","3526471405500","2475841364256","7036077847485"}

    Returns: 33

  57. {"44320456046231","48486187464170","02544564241665","68526606606132","23340143854875","67438415365821","67786253421078","02586416876763","27282143703620","05187482736043","87168212067534","74652302170617","12058365006137","86843643206230"}

    Returns: 44

  58. {"612861162282888","432222176588506","270443740576520","656810747561348","282448610718218","422514325503184","683512547215225","830322571880525","743024687302710","628225863668218","888835115514083","785206878666006","481312251083227","162152570632063","717114025874683"}

    Returns: 35

  59. {"6542523646640072","0012488747365817","2226612660582660","0166756432035460","8133035768480076","7523563273380053","0613031637332220","7666003630330516","2084257025631064","0512615375672248","4427750615117316","1456670777877052","3137810761514724","3428815326474022","2835371580325001","2358373500122600"}

    Returns: 42

  60. {"65008304408074641","20685027522102582","77585735810741657","78221582625086418","61873640114431068","22204566845574130","46420667416537503","05745327688284818","52168888234141846","00864835044886383","73341867562432658","05266874448760304","24406212674845783","03471642670464738","65874345852085386","18304036281647240","05733428087837228"}

    Returns: 55

  61. {"443122878765431763","606707871333075323","343021460531064456","381061823026487631","436241762402373587","135854475621476263","072345752527042127","828301876708212230","878124318081351826","622487375708041461","172683053466654388","773645771884510506","477255640154542486","282811333434765142","256816215017784571","716167002843642344","465427054853654728","774550240311800148"}

    Returns: 53

  62. {"8388473220840358225","0602420540344715382","4051608247571757348","0013642865348255816","7871003678505831675","8275705674086513524","1284871315778364857","1378880135801104306","8275406881487643856","1486662360331512418","5274477886805064606","4667453343635168465","7626528000843307137","6721238206842486626","0558318317178456746","4865051313453187704","3412852140701004081","3072577547427763041","0883581318021371261"}

    Returns: 51

  63. {"46668164700618522073","04787533155337825545","27731328471126854155","31018843360414215378","10271502014757671428","10246847884555737063","06417644174307226806","41875223300031034806","57747631502362776123","78672745214420640727","12804870622687723634","05584501056102885545","48160507322678471513","14165532585823265558","48672163220586513351","00566458571783240358","60173468823388725871","73876240248674416505","44871842065672081715","00157354465222333276"}

    Returns: 54

  64. {"99999999999999999999","99111991191119111119","99999999999999999999","99999999999999999999","99999999999999999999","99111991191119111119","99111991191119111119","99111991191119111119","99111991191119111119","99111991191119111119","99999999999999999999","99999999999999999999","99111991191119111119","99111991191119111119","99999999999999999999","99111991191119111119","99111991191119111119","99111991191119111119","99111991191119111119","99999999999999999999"}

    Returns: 76

  65. {"19191911919119119911","19191911919119119911","19191911919119119911","99999999999999999999","19191911919119119911","19191911919119119911","99999999999999999999","19191911919119119911","99999999999999999999","19191911919119119911","99999999999999999999","19191911919119119911","99999999999999999999","99999999999999999999","19191911919119119911","19191911919119119911","19191911919119119911","99999999999999999999","99999999999999999999","19191911919119119911"}

    Returns: 84

  66. {"91199199111911919911","91199199111911919911","99999999999999999999","91199199111911919911","91199199111911919911","99999999999999999999","99999999999999999999","91199199111911919911","91199199111911919911","99999999999999999999","99999999999999999999","99999999999999999999","91199199111911919911","99999999999999999999","91199199111911919911","99999999999999999999","91199199111911919911","91199199111911919911","91199199111911919911","91199199111911919911"}

    Returns: 84

  67. {"99111919999911199991","99999999999999999999","99999999999999999999","99999999999999999999","99111919999911199991","99999999999999999999","99111919999911199991","99999999999999999999","99999999999999999999","99999999999999999999","99111919999911199991","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99111919999911199991","99111919999911199991","99111919999911199991","99999999999999999999"}

    Returns: 116

  68. {"99999999999999999999","91991191999991991919","91991191999991991919","99999999999999999999","99999999999999999999","99999999999999999999","91991191999991991919","99999999999999999999","91991191999991991919","91991191999991991919","91991191999991991919","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","91991191999991991919"}

    Returns: 124

  69. {"91919191999919999991","91919191999919999991","99999999999999999999","99999999999999999999","99999999999999999999","91919191999919999991","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","99999999999999999999","91919191999919999991","99999999999999999999","99999999999999999999","91919191999919999991","91919191999919999991","91919191999919999991","99999999999999999999","99999999999999999999"}

    Returns: 124

  70. {"99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999", "99999999999999999999" }

    Returns: 180

  71. {"111", "010", "010" }

    Returns: 0

  72. {"19991", "19919", "99199", "91999", "19999" }

    Returns: 21

  73. {"100", "100", "011" }

    Returns: 0

  74. {"11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111", "11111111111111111111" }

    Returns: 20

  75. {"19", "19" }

    Returns: 2

  76. {"0111101100", "0001101001", "1001001000", "1000100001", "0110011111", "0011110100", "1000001100", "0001100000", "1000100001", "0101110010" }

    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: