Statistics

Problem Statement for "PerfectMemory"

Problem Statement

You might have played the game called Memoria. In this game, there is a board consisting of N rows containing M cells each. Each of the cells has a symbol on its back. Each symbol occurs on exactly two cells on the board.

A move means turning a pair of cells one by one to see the symbols behind them. When the symbols differ, both of the cells are turned on their faces, thus hiding the symbols again. The player should remember the symbols. If the symbols on the backs of the turned cells coincide, the cells stay that way, i.e., don't turn back again. As soon as after some move all the cells on the board are turned (such that all the symbols are simultaneously visible), the game ends.

Manao has a perfect memory, so when he sees the symbol behind some cell, he remembers it forever. Manao is trying to finish the game in the least expected number of moves. Find the expected number of moves he will need to accomplish this.

Definition

Class:
PerfectMemory
Method:
getExpectation
Parameters:
int, int
Returns:
double
Method signature:
double getExpectation(int N, int M)
(be sure your method is public)

Notes

  • The board Manao plays on is generated as follows. The same set of (N * M) / 2 symbols is used for each generation. The board contents are chosen uniformly among all valid N x M boards.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • N will be between 1 and 50, inclusive.
  • M will be between 1 and 50, inclusive.
  • N * M will be even.

Examples

  1. 1

    2

    Returns: 1.0

    There are only two cells on the board, so the game always ends in one move.

  2. 2

    2

    Returns: 2.6666666666666665

    There are four cells. The game may flow in two possible scenarios: 1) In the first move, Manao turns two cells with equal symbols. The game ends in two moves then and the probability of such a first move is 1/3. 2) In the first move, Manao turns two cells with different symbols. Then he finishes the game in three moves and the probability of such a first move is 2/3. The overall expected number of moves is 1/3 * 2 + 2/3 * 3 = 8/3.

  3. 2

    3

    Returns: 4.333333333333334

  4. 4

    4

    Returns: 12.392984792984793

  5. 50

    50

    Returns: 2016.6207229777651

  6. 49

    50

    Returns: 1976.2780813675422

  7. 48

    50

    Returns: 1935.9354397307177

  8. 50

    47

    Returns: 1895.5927980655927

  9. 46

    36

    Returns: 1335.6369274290305

  10. 46

    46

    Returns: 1706.789234637251

  11. 49

    48

    Returns: 1897.2065037327618

  12. 2

    12

    Returns: 18.849790540892975

  13. 2

    22

    Returns: 34.98841742770249

  14. 2

    43

    Returns: 68.87713012093411

  15. 3

    48

    Returns: 115.67496570129474

  16. 4

    34

    Returns: 109.22011081919707

  17. 5

    6

    Returns: 23.69160691896086

  18. 5

    8

    Returns: 31.760820843903016

  19. 5

    12

    Returns: 47.89855303785223

  20. 5

    40

    Returns: 160.858877139804

  21. 6

    25

    Returns: 120.51610458647065

  22. 6

    30

    Returns: 144.7217769343189

  23. 7

    14

    Returns: 78.55947739317146

  24. 8

    27

    Returns: 173.76855143767952

  25. 8

    28

    Returns: 180.22338701676645

  26. 9

    46

    Returns: 333.5255837686135

  27. 11

    18

    Returns: 159.2451675193959

  28. 11

    20

    Returns: 176.99596934610258

  29. 12

    8

    Returns: 76.94575483559984

  30. 12

    27

    Returns: 260.90877734010786

  31. 13

    2

    Returns: 20.463769550919906

  32. 13

    10

    Returns: 104.37896702860029

  33. 14

    27

    Returns: 304.47886421459447

  34. 17

    10

    Returns: 136.65322294496434

  35. 17

    20

    Returns: 273.81843385997223

  36. 17

    38

    Returns: 520.7155058920074

  37. 18

    15

    Returns: 217.33867656959313

  38. 18

    27

    Returns: 391.6190148377305

  39. 20

    1

    Returns: 15.621650038987498

  40. 20

    2

    Returns: 31.760820843903016

  41. 20

    31

    Returns: 499.73732750058963

  42. 22

    15

    Returns: 265.7498986650561

  43. 24

    39

    Returns: 754.7028610875919

  44. 25

    28

    Returns: 564.2855674961802

  45. 27

    22

    Returns: 478.75914866326076

  46. 29

    34

    Returns: 795.0455063001342

  47. 30

    9

    Returns: 217.33867656959313

  48. 30

    12

    Returns: 289.95550308013884

  49. 30

    31

    Returns: 749.8617436314158

  50. 32

    23

    Returns: 593.3322744687753

  51. 32

    30

    Returns: 774.0673308447905

  52. 32

    49

    Returns: 1264.633876667661

  53. 33

    4

    Returns: 105.99268189876544

  54. 33

    6

    Returns: 159.2451675193959

  55. 34

    22

    Returns: 603.0145100091017

  56. 34

    29

    Returns: 795.0455063001342

  57. 34

    45

    Returns: 1233.9734682900253

  58. 36

    5

    Returns: 144.7217769343189

  59. 36

    14

    Returns: 406.1423713496746

  60. 38

    19

    Returns: 582.0363329332532

  61. 38

    24

    Returns: 735.3383912202512

  62. 40

    35

    Returns: 1129.0825970154985

  63. 42

    12

    Returns: 406.1423713496746

  64. 42

    27

    Returns: 914.4597339359035

  65. 43

    6

    Returns: 207.65642918602504

  66. 43

    48

    Returns: 1664.832887095386

  67. 44

    10

    Returns: 354.5037682720973

  68. 44

    16

    Returns: 567.5129794096994

  69. 45

    8

    Returns: 289.95550308013884

  70. 46

    41

    Returns: 1521.2130816594033

  71. 47

    30

    Returns: 1137.151125606176

  72. 48

    8

    Returns: 309.31998437589533

  73. 50

    28

    Returns: 1129.0825970154985

  74. 50

    43

    Returns: 1734.222231082574

  75. 45

    46

    Returns: 1669.6740041218345

  76. 48

    49

    Returns: 1897.2065037327618

  77. 50

    48

    Returns: 1935.9354397307177

  78. 50

    49

    Returns: 1976.2780813675422

  79. 48

    48

    Returns: 1858.4775677070973

  80. 48

    46

    Returns: 1781.0196955653944

  81. 47

    48

    Returns: 1819.7486316519498

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: