Statistics

Problem Statement for "RandomPaintingOnABoard"

Problem Statement

You are given a board with N row and M columns. We will use (i,j) to denote the j-th cell in the i-th row (0-based indices). Each cell is initially white. You goal is to have a board that has at least one black cell in each row, and at the same time at least one black cell in each column.

You will paint the cells black in turns. In each turn, you select one cell (in a specific way that is given below) and color it black. You stop as soon as your goal is achieved.

You are given a String[] prob consisting of N elements, each M characters long. All characters in prob are digits ('0'-'9'). The digit represented by the j-th character in the i-th row (0-based indices) will be denoted p[i][j]. This digit is the relative probability of cell (i,j) being chosen in each turn.

Formally, let s be the sum of all p[i][j]. Then in each turn the cell (i,j) is chosen with probability p[i][j]/s. Note that the same cell may be chosen multiple times: we may sometimes choose a cell that is already black.

The constraints guarantee that achieving your goal is possible. Return the expected number of turns until your goal is achieved.

Definition

Class:
RandomPaintingOnABoard
Method:
expectedSteps
Parameters:
String[]
Returns:
double
Method signature:
double expectedSteps(String[] prob)
(be sure your method is public)

Notes

  • Your return value must have a relative or an absolute error of less than 1e-9.

Constraints

  • prob will contain between 1 and 21 elements, inclusive.
  • Each element of prob will be between 1 and 21 characters long, inclusive.
  • The elements of prob will be of the same length.
  • Each element of prob will consist of digits only ('0'-'9').
  • The total number of cells (i.e., the total number of digits in prob) will be between 1 and 150, inclusive.
  • In each row there will be at least one non-zero digit.
  • In each column there will be at least one non-zero digit.

Examples

  1. {"10", "01"}

    Returns: 3.0

    Each of the cells (0,0) and (1,1) has probability 1/2 to be chosen in each turn. One of those cells will be colored black in the first turn. Then there will be some additional turns until the other cell is chosen. As that happens with probability 1/2, the expected number of additional turns is 2. Thus the total expected number of turns is 1+2 = 3.

  2. {"11", "11"}

    Returns: 3.6666666666666665

    This board is symmetric, so we can just assume that the cell (0,0) was chosen in the first turn. Then there will be some additional turns until some other cell is chosen for the first time. The probability of choosing a different cell is 3/4, thus the expected number of these additional turns is 4/3. Now, what is the second cell to be colored black? With probability 1/3 it is the cell (1,1) and we are done. With probability 2/3 it is one of the other two cells. In either of these two cases, we still need to color any one of the other two white cells black, and the expected number of turns until that happens is 2. Thus the answer is 1 + 4/3 + (2/3 * 2) = 11/3.

  3. {"11", "12"}

    Returns: 3.9166666666666665

  4. {"0976", "1701", "7119"}

    Returns: 11.214334077031307

  5. {"380543603580587026373","485133852599920266180","492918585613728841125","603678561711172413417","750202755363934793389","668261168887502016694","543948589568007346243"}

    Returns: 84.45923398680405

  6. {"0188836","9616423","0574110","5459143","2081997","4038280","2647440","8846452","4875967","4035164","9203749","5929590","2968681","5547458","4808661","6004749","6772056","7524241","8007534","2155505","9541121"}

    Returns: 85.33973947236763

  7. {"898898898898988898989","989898999999998999999","988999999899889989889","989898898989998999988","999989999988899899899","998888998888998889989","889898999898889989888"}

    Returns: 76.63127641078452

  8. {"9989888","9898889","9888888","9989898","9998988","8899998","8898989","8989989","9988899","8888888","8999988","8988889","8888988","9898999","9989989","8998998","8989888","8999989","8898989","8998889","8888999"}

    Returns: 76.64534204640518

  9. {"000020080000000004000","100000000008000600000","000800000000030000700","000000500060500000000","000000008200008000000","090002000000000030000","004000000000000000052"}

    Returns: 159.93797686033446

  10. {"0500000","0060000","0005000","0000002","0000005","0300000","0000005","0003000","0000060","5000000","2000000","0000500","0000030","0060000","0300000","0000080","0050000","0003000","0000100","2000000","0000700"}

    Returns: 134.68459028753597

  11. {"000000000000001000000", "888999988889890999988", "988889988899980889999", "889898998889980999898", "988889999989880899999", "998888998988990989998", "998988999898990889899"}

    Returns: 1028.7662876159634

  12. {"0898988","0988899","0899989","0999899","0888898","0888999","0999998","0999899","0989888","0999989","1000000","0998989","0999898","0898898","0999999","0889898","0998888","0899898","0899888","0898998","0889888"}

    Returns: 1027.7703189300398

  13. {"072396367826339412","342566506549993306","696051407285622939","245983621935729151","455839008863797688","701156208125443509","618107920958278190","958704724743897469"}

    Returns: 82.62508700953535

  14. {"31895395","75359476","13309631","52576751","42185481","83681764","27279898","71205727","85963743","39105898","33883860","13872252","69737785","20853886","26335558","74710380","72387161","20934864"}

    Returns: 67.7478127964156

  15. {"899899999888988988","898999989999889999","899899999889889899","898899888889889898","999899989899989899","899898989989998999","988999899889888989","888988998999988898"}

    Returns: 63.09563696287171

  16. {"89888888","88998899","89888899","88898988","98899998","98899999","99898989","98989988","98989899","98899888","89889889","99898988","89989889","99899898","98989989","88889988","88999998","89998899"}

    Returns: 63.06660717899339

  17. {"000010000000800700","000008000100000000","503000000000000009","000000007000008000","000000710000000000","080000000010000000","000100000000010000","100000000001000030"}

    Returns: 210.4824436987288

  18. {"00020000","00000200","00000100","00030000","00000006","00500000","00300000","00000005","00008000","30000000","00000020","09000000","00003000","00000040","60000000","01000000","00020000","00000097"}

    Returns: 146.15280620343373

  19. {"989889899808899988","998898989908889989","999988999808898999","988888898909999889","000000000010000000","898888889908988899","989888889809999898","888888899909988999"}

    Returns: 1012.8820706542815

  20. {"08988989","08999999","08988898","09889888","08888898","09899888","08998899","09899889","09889998","09998989","09998899","09988989","09998898","08988998","10000000","08988989","08998989","08888889"}

    Returns: 1012.8814737163843

  21. {"5508390121807744","6958367712589200","6618862143567496","3025885109713203","2496873962683048","1768682089133250","2674239733230284","8535540815118919","1136672934997781"}

    Returns: 58.97033056167796

  22. {"793121830","978506438","622921034","600630152","887713166","707249164","536582766","772051994","647918141","047967100","536975958","718703132","733972418","199810866","664720707","942824257"}

    Returns: 60.921227148773475

  23. {"9998988889888888","9998998888998888","8988889899998898","8899989989988998","9989998988888998","9999989898899889","9998888999998888","9888888999989999","9898899889988888"}

    Returns: 54.64762379585377

  24. {"988899888","989889889","998998999","999989888","888999888","898889888","899998888","989989898","888998899","899899998","899988989","889889988","888999989","989898988","899888889","998998889"}

    Returns: 54.63609312765075

  25. {"0900000000000000","0080000000003000","0000000000530000","0000000020000007","0000010008000000","5000000600000000","0000000000400070","0007001000000000","0000100000000200"}

    Returns: 154.02705211155074

  26. {"000070000","000000005","100000000","000000002","040000000","800000000","000007010","000000500","090000000","000500000","000003000","000050000","006000000","000000080","004000000","000300000"}

    Returns: 108.97556219347472

  27. {"9809898888899998","9908889889989899","9909988999989989","9908888989988899","8909989888999899","9909898998999899","8908889999898899","0010000000000000","8809899898988999"}

    Returns: 1031.36540984649

  28. {"898908888","898808998","898809898","988908899","998809988","998808898","989808898","999808999","899808999","898808888","889908989","988809898","000010000","998808989","989908888","989909989"}

    Returns: 1016.384940071684

  29. {"220709666912551","831321816752642","139757216262789","491332989684692","842024426096115","450101750102084","853778762862493","792153156920886","247938882272416","710691286105976"}

    Returns: 58.03656072223395

  30. {"9061320974","5714880191","5702334052","0258289777","5898854469","2322497664","4335219876","8236762268","4019949949","3299095305","0978967435","0162129385","0649008410","1416343953","7231038015"}

    Returns: 56.58048534488787

  31. {"998988988988888","999999989888998","888899999899999","888998989889988","989889989898999","989899888989888","888989899998899","888898989988999","888989998989998","998898988888999"}

    Returns: 51.15883767982401

  32. {"8898988999","8888989999","8889989889","8899998988","9999889899","8889889998","9899999888","8899989888","8989888889","9999989898","9998898898","9989998998","8888999898","9888889989","9988999998"}

    Returns: 51.14899885124127

  33. {"000009000000006","006000002000000","000000000000080","000010000000000","000000000066000","000000010000000","500500000000000","000000300500000","060000000000000","000300000000500"}

    Returns: 125.34574324580612

  34. {"0200000000","0005000000","0000006000","0000006090","4000000000","0000020000","0000000006","0000000300","0000100000","0080000000","0040000000","0000000300","0000000090","0800000000","8000000000"}

    Returns: 115.74006727442804

  35. {"998888099889888","000000100000000","899989099898888","889988088898999","989899098898888","998988088898989","899899099888999","988889089998889","999888098999998","899998099998998"}

    Returns: 1074.1312870309466

  36. {"0000000001","8988898880","8988989880","9999889890","8999989880","8988888880","8999989880","9989899990","8888998890","9898998890","9999989890","9898989880","8989989980","9998888890","9988998880"}

    Returns: 1071.1353347541049

  37. {"1479033300358","3846871844628","4479860388971","7642568725882","4103312713713","9906351633657","3213524128073","9746127367184","4959994071638","4047724885447","8533498611476"}

    Returns: 48.91383007858037

  38. {"74306728263","71574561853","06221910048","20144938882","65960936753","24207459819","45645370071","44185420422","21590106882","63728396862","00346052873","44685014486","53111762970"}

    Returns: 48.36812087582793

  39. {"9998898998898","8899999898899","8989888898999","9899898999889","9999889989988","8898898999989","8898898988899","9888898999998","9899889899989","8999899889889","9889898888999"}

    Returns: 45.31100672648463

  40. {"98989898899","98989998899","88988899899","88898889999","88988899999","98998998899","89899998898","98898998999","99898998988","89999889998","89999899998","98989898998","89888999899"}

    Returns: 45.297131620043416

  41. {"6000000000000","0000007001000","0100000000000","0000300000000","0000000000005","0050000004000","0000000000500","0001000000030","0000000400000","0000000090000","0000080000000"}

    Returns: 98.59339703960332

  42. {"00000900000","20000000000","00000090000","00600000000","02060000000","00000000050","00000000200","07000000000","00000009000","00080000000","00007000000","00000000060","00000000004"}

    Returns: 69.52840991433986

  43. {"9989998989908","8988899889809","9889888899809","8898898999908","8989888889808","9989988998909","8999899999908","8998889988908","0000000000010","8999898998908","9988899999808"}

    Returns: 1024.9008126562242

  44. {"98999989890","00000000001","88988889990","99988899980","89989999990","99999888880","88898889880","98898989880","99999899880","88888989880","98989988880","98989998990","89998889990"}

    Returns: 1023.9018754239484

  45. {"556898596409","231671605440","770587506227","840853621730","544206603284","307572707830","357477409492","759466168331","431543767592","332712493789","869076753794","684528408242"}

    Returns: 47.88304175701358

  46. {"557961700203","244104992988","625246711129","136501190328","983001388401","382172363167","774325494100","249688901870","739321700588","122795553035","709766839835","435839550443"}

    Returns: 47.85366900247705

  47. {"898889888888","899898998988","999999988999","888998889888","999899999899","899989888999","988999988898","989998988998","999989998988","898999888888","989989989998","889899989888"}

    Returns: 44.5898834285838

  48. {"888888899889","889889989989","999898898999","989899989989","999888899889","998989898988","998988889999","999998999988","888888889899","999898999899","998998999999","999998899988"}

    Returns: 44.584272534496385

  49. {"000000000200","000000060000","060000000000","000001000000","003000000000","000000000003","000000000070","000000007000","000050000000","000400000000","000000800000","200000000000"}

    Returns: 73.96502870064538

  50. {"000000000002","400000000000","090000000000","000000800000","000000020000","000000000080","008000000000","000000000800","000000001000","000050000000","000004000000","000400000000"}

    Returns: 84.13411024362

  51. {"999808898889","998908999988","899909988888","898809898998","888809998989","898808989899","998909889999","899808998989","999909888999","999909988898","999909999999","000010000000"}

    Returns: 1041.8503519267833

  52. {"898998889980","899899988890","889988998980","989988998990","998889899890","989888899990","988899898880","989899898880","989989898890","000000000001","889888989980","889899888990"}

    Returns: 1028.8604496869295

  53. {"7"}

    Returns: 1.0

  54. {"123456789123456789123"}

    Returns: 191.6781070582628

  55. {"1","2","3","4","5","6","7","8","9","1","2","3","4","5","6","7","8","9","1","2","3"}

    Returns: 191.6781070582628

  56. {"000000000000001000000", "888999988889890999988", "988889988899980889999", "889898998889980999898", "988889999989880899999", "998888998988990989998", "998988999898990889899" }

    Returns: 1028.7662876159634

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: