Statistics

Problem Statement for "ChessMatch"

Problem Statement

Just before a chess match between two teams, each team's coach secretly determines an ordering of his team's players. The first players in each team then get to play against each other, the second players in each team play against each other, etc. The team with the most wins will win the match.

You are the coach for one of the teams, and you have somehow managed to find out the order of the players in the other team. Based on that, you want to order your players so that your team's expected score is maximized to your advantage. The expected score of a single game can be calculated by the following formula (which is directly derived from how the international chess rating system works): 

EA = 1 / (1 + 10 (RB - RA)/400)

EB = 1 / (1 + 10 (RA - RB)/400)

where RA and RB are the ratings of player A and B, and EA and EB are the expected scores for each player. For instance, if RA is 2432 and RB is 2611, the expected score for player A is 1 / (1 + 10 179/400) = 0.263005239459. The expected score for a team is the sum of the expected scores for the players in that team.

To make things a bit more complicated, the players in a team must be ordered such that a player with rating x plays before all players with rating strictly less than x - lim, where lim is a given non-negative integer. For example, if lim is 100, a player with rating 2437 must play before a player with rating 2336 but not necessarily before a player with rating 2337.

Create a class ChessMatch containing the method bestExpectedScore which takes a int[] teamA, the ratings of your players (in no particular order); a int[] teamB, the ratings of your opponent's players in the order they will play; and an int lim, the limit determining how freely you can order your players. You can assume that your opponent's players will be ordered in accordance with lim. The method should return a double, your team's expected score if you order your players optimally.

Definition

Class:
ChessMatch
Method:
bestExpectedScore
Parameters:
int[], int[], int
Returns:
double
Method signature:
double bestExpectedScore(int[] teamA, int[] teamB, int lim)
(be sure your method is public)

Notes

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

Constraints

  • teamA will contain between 1 and 20 elements, inclusive.
  • teamB will contain the same number of elements as teamA.
  • Each element in teamA and teamB will be between 1500 and 3000, inclusive.
  • lim will be between 0 and 1500, inclusive.
  • teamB[i] + lim will be equal or greater than teamB[j] for j>i.

Examples

  1. {2239,2412,2399,2267}

    {2534,2429,2340,2389}

    100

    Returns: 1.4835736078879815

    There are only four possible ways to order the players in teamA so that the constraints are fulfilled. These are: {2399,2412,2239,2267} Expected score: 1.48040986... {2399,2412,2267,2239} Expected score: 1.48357361... {2412,2399,2239,2267} Expected score: 1.47815348... {2412,2399,2267,2239} Expected score: 1.48131723... Note that if we could order the players in teamA freely, the best way would have been to order them in reverse rating order, {2239, 2267, 2399, 2412}. However, this is not allowed, since 2239 and 2267 aren't allowed to appear before 2399 and 2412 as the difference is greater than the limit of 100.

  2. {2239,2412,2399,2267}

    {2534,2429,2340,2389}

    150

    Returns: 1.5332458652994558

    The players are the same as in the previous example, but the limit has been increased to 150, and a couple of more orderings are now possible. The best one is {2267, 2412, 2399, 2239}.

  3. {2500,2503}

    {1500,1503}

    3

    Returns: 1.9936953816334797

    teamA is superior, but the ordering still matters slightly.

  4. {1786,2080,2156,2132,2187,2380,2191}

    {1885,1851,1743,1714,2338,2167,1789}

    1500

    Returns: 5.227676657319362

    Since the limit is 1500, any ordering of the players is possible. The best one is {2191, 2187, 2132, 2080, 1786, 2380, 2156}.

  5. {1622,1529,1677,1805,1824,1648,1859,1540,1574}

    {1894,1734,1717,1861,1759,1862,1613,1639,1801}

    211

    Returns: 3.595004632329262

  6. {1601,1876,1608,1890,1764,1564,1674,1510,1645,1638,1754,1825,1624,1757,1653,1539,1543,1524,1693}

    {2298,2279,2293,2103,2216,2053,2194,2177,2113,2172,2119,1910,1932,1712,1725,1758,1533,1545,1602}

    152

    Returns: 4.063060581615008

  7. {1648,1776,1544,1595,1594,1787,1806,1624,1732,1863,1610,1879,1627,1622}

    {2541,2692,2635,2695,2378,2553,2279,2396,2188,2243,2160,1785,1682,1607}

    179

    Returns: 1.5682551710885595

  8. {1744,1555,1518}

    {1975,2082,1951}

    148

    Returns: 0.3394795935864918

  9. {1675,1891,1509,1818,1745,1823,1665,1592,1787,1608,1526,1795,1588,1545,1577,1882,1649,1786,1741}

    {2593,2593,2538,2611,2542,2534,2591,2522,2444,2490,2519,2354,2409,2146,2220,2109,2065,2103,1942}

    87

    Returns: 0.5019229780326477

  10. {1828,1795,1781,1587}

    {2466,2592,2617,2540}

    153

    Returns: 0.04704222038097157

  11. {2298,1548,2280,1664,2198,1781,1645,2040,1844,1748,1623,1782,2128}

    {1796,1774,1840,1768,1834,1871,1787,1800,1855,1577,1581,1653,1620}

    151

    Returns: 8.349137861726021

  12. {1868,1797,2213,2085,1611,2002,2167,1908, 1773,1834,1766,2245,1582,2009,2233,2030}

    {2138,2259,2109,2160,2295,2022,2043,2131, 1655,1716,1648,1779,1518,1570,1560,1677}

    200

    Returns: 9.229777079272512

  13. {2071,1569,2041,1872,1788,1543,1997,2057,2237,1639,2158,2272,2209,1854,2093}

    {2557,2154,2229,2033,2023,2104,1946,1898,1967,1831,1728,1544,1544,1617,1618}

    106

    Returns: 8.424395391910005

  14. {1983,1637,2288,1697,1727,2186,2092,1664,2073,1840,2145,2123,1706,1568}

    {2249,2252,2280,2181,2295,2203,2041,2058,2053,2024,2064,2004,1930,1932}

    126

    Returns: 3.766689796172387

  15. {2095,1882,2148,1721,1731,1506,1631}

    {2599,2434,2557,2091,2230,2193,2110}

    211

    Returns: 0.5846898764846311

  16. {2108,2263}

    {2412,2466}

    225

    Returns: 0.4107816710253576

  17. {1806,2275,1716,1995,2510,2043,2134,2284,2197,2530,1882,1804,1812,2106,1995,1776,1566,2249,2264}

    {1790,1743,1789,1855,1767,1820,1844,1881,1717,1658,1619,1690,1628,1718,1558,1658,1525,1600,1645}

    167

    Returns: 15.851517895136311

  18. {2356,1613,2138}

    {2215,1891,1551}

    221

    Returns: 2.0863810584863307

  19. {2539,1504,2062,2219,1711,2219,1670,1711,1835,1642,1931,2635,2692,1719,1501,2244,1522}

    {2555,2700,2632,2665,2486,2349,2494,2385,2165,2290,2309,2326,2113,1759,1693,1700,1525}

    179

    Returns: 4.111893432001513

  20. {1545,2149,1740,2312,2017,1614,1695,2651,1903,1595,2534,1610,2398,1790,2687,2120,2213,1981,2294}

    {2218,2241,2263,2231,2144,2146,2234,2139,2058,2100,2141,2110,1974,2012,1987,1998,2041,1934,1945}

    93

    Returns: 8.31621062261836

  21. {2589,2154,1820,1509,2633,1672,2315,1532,2623,2698,1597,1782,2154}

    {2632,2566,2476,2434,2321,2356,2296,2248,2196,2236,2048,2061,2017}

    63

    Returns: 4.0056785779491015

  22. {2205,2172,2027,1594,2153}

    {2493,2536,2588,2594,2384}

    177

    Returns: 0.39248423699104706

  23. {1927,2145,2245,2112,2062}

    {1766,1513,1687,1597,1593}

    176

    Returns: 4.656193581199512

  24. {1992,2272,2133,2132}

    {2058,1847,1571,1710}

    155

    Returns: 3.45017358370403

  25. {2274,2074,1945}

    {2552,2096,1539}

    197

    Returns: 1.5482271692449832

  26. {2212,2136,2273,2234,2162,2020,2180,2117,2002,1996,1924,2156,2119,1951,2101,2114,1968,1993}

    {2295,2285,2163,2158,2211,2154,2126,2093,2145,2048,2057,2068,2081,1987,1996,2059,1933,1941}

    102

    Returns: 8.832959079508132

  27. {1956}

    {2091}

    89

    Returns: 0.3149403910066497

  28. {2211,2018,2058,2090,2235,2102,2235,2288,2272,2246,1993,2093,2062,2300,2098,2252,2097,2089,1944}

    {2614,2657,2698,2586,2678,2673,2621,2549,2609,2508,2477,2466,2515,2374,2363,2358,2353,2325,2356}

    99

    Returns: 2.172533963677316

  29. {2216,2401}

    {1755,1759}

    141

    Returns: 1.9091204443775267

  30. {2452,2125,2060,2043,2582,2336,2609,2050,2269,2109,2493,2432,2217,1994,2475}

    {2271,2258,2297,2138,2237,2089,2143,1991,1736,1674,1788,1656,1568,1685,1648}

    130

    Returns: 13.02456617574149

  31. {2427,2672,2603,1901}

    {2423,1941,1683,1510}

    74

    Returns: 3.6768740480682447

  32. {2592,1925,2576,2502,2566,2379,2698,2455,1903,1983,2463,2474,2335}

    {2168,2170,2187,2184,2196,2281,2099,2201,1929,1977,1950,1915,2037}

    160

    Returns: 10.232805474983659

  33. {2335,2212,2352}

    {2463,2343,1998}

    209

    Returns: 1.6107954531019573

  34. {1988,2049,2149,2637,2513,2460,2243,1924,1906,2258,2074,2178,2190,2414,2232,1948,2536,2485,2251}

    {2589,2587,2549,2614,2565,2584,2634,2646,2655,2512,2540,2524,2608,2573,2541,2606,2434,2358,2369}

    175

    Returns: 3.649250874746338

  35. {2639,2601,2642,2547,2339,2418,2619}

    {1789,1766,1651,1744,1753,1776,1529}

    193

    Returns: 6.934757263678988

  36. {2494,2687,2557,2415,2532,2319,2333,2471,2429,2481,2508,2601}

    {2002,2058,2185,2084,2225,1959,2034,1726,1669,1795,1886,1596}

    244

    Returns: 11.449930844127683

  37. {2467,2675,2661,2385,2607}

    {2450,2215,2075,2064,1732}

    92

    Returns: 4.556807091576441

  38. {2589,2656,2364,2575,2575,2446,2422,2485,2303,2542,2325,2424,2612,2611,2401}

    {2297,2117,2148,2194,1985,1984,2020,2046,2066,1951,2039,2037,1902,1904,1922}

    90

    Returns: 13.88932873545747

  39. {2427,2450,2633,2412,2414,2400,2639,2366,2568,2538,2546,2551}

    {2537,2616,2573,2633,2588,2689,2271,2436,2071,2168,2229,2237}

    222

    Returns: 7.1676544291461015

  40. {2527,2661,2641,2350,2328,2469,2328,2544,2541}

    {2645,2698,2668,2610,2442,2462,2337,2388,2333}

    129

    Returns: 4.246875980919899

  41. {1500,1501,1502,1503,1504,1505,1506,1507,1508,1509,3000,2999,2998,2997,2996,2995,2994,2993,2992,2991}

    {1500,1501,1502,1503,1504,1505,1506,1507,1508,1509,3000,2999,2998,2997,2996,2995,2994,2993,2992,2991}

    1500

    Returns: 10.071897045774726

  42. {1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500,1500}

    {3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000,3000}

    0

    Returns: 0.0035559264769940806

  43. { 2500, 2503 }

    { 1500, 1503 }

    3

    Returns: 1.9936953816334797

  44. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677 }

    200

    Returns: 9.229777079272512

  45. { 2995, 1876, 1968, 1646, 1589, 2158, 2433, 2269, 2379, 1738, 2789, 2537, 1603, 2325, 1750, 2201, 2010, 1509, 2929, 2939 }

    { 2921, 2657, 2590, 1669, 1984, 2245, 1655, 2714, 2394, 2559, 2332, 2189, 2220, 2017, 1540, 2332, 2373, 2898, 2562, 2403 }

    1500

    Returns: 11.208459059142951

  46. { 2341, 2231, 1674, 1823, 2011, 2341, 2512, 2654, 2093, 1789, 1826, 2800, 2451, 2731, 2753, 1893, 2104, 2999, 2893, 2873 }

    { 2989, 2593, 2753, 2394, 2739, 2593, 2310, 2864, 1670, 1953, 1976, 1584, 1992, 1575, 2304, 2201, 2436, 2648, 2489, 2439 }

    1500

    Returns: 13.210816007788459

  47. { 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 }

    { 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 }

    100

    Returns: 10.000066695263175

  48. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677 }

    190

    Returns: 9.226151974496652

  49. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 2030, 2030, 2040, 2040 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 2030, 2030, 2040, 2040 }

    1000

    Returns: 11.872706135296516

  50. { 1500, 1501, 1502, 1503, 1504, 1600, 1601, 1602, 1603, 1604, 1700, 1701, 1702, 1703, 1704, 1800, 1801, 1802, 1803, 1804 }

    { 1900, 1901, 1902, 1903, 1904, 1800, 1801, 1802, 1803, 1804, 1700, 1701, 1702, 1703, 1704, 1600, 1601, 1602, 1603, 1604 }

    1500

    Returns: 8.056568473132375

  51. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 1500, 1500, 1500, 1500 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 1500, 1500, 1500, 1500 }

    200

    Returns: 11.229777079272512

  52. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 2014, 2184, 1552, 1598 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 1501, 1502, 1503, 1504 }

    1500

    Returns: 13.488117221474024

  53. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 1500, 1500, 1500, 1500 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 1500, 1500, 1500, 1500 }

    1500

    Returns: 12.534203066584341

  54. { 2401, 2402, 2403, 2404, 2405, 2406, 2407, 2408, 2409, 2410, 2491, 2492, 2493, 2494, 2495, 2496, 2497, 2498, 2499, 2500 }

    { 2501, 2502, 2503, 2504, 2505, 2506, 2507, 2508, 2509, 2510, 2511, 2512, 2513, 2514, 2515, 2516, 2517, 2518, 2519, 2520 }

    400

    Returns: 8.324375198544743

  55. { 2500, 2499, 2498, 2497, 2496, 2495, 2494, 2493, 2492, 2491, 2490, 2489, 2488, 2487, 2486, 2485, 2484, 2483, 2482, 2481 }

    { 2500, 2499, 2498, 2497, 2496, 2495, 2494, 2493, 2492, 2491, 2490, 2489, 2488, 2487, 2486, 2485, 2484, 2483, 2482, 2481 }

    19

    Returns: 10.000066695263177

  56. { 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500 }

    { 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500 }

    1500

    Returns: 10.0

  57. { 1501, 1502, 1503, 1504, 1505, 1506, 1507, 1508, 1509, 1510, 1511, 1512, 1513, 1514, 1515, 1516, 1517, 1518, 1519, 1520 }

    { 1520, 1519, 1518, 1517, 1516, 1515, 1514, 1513, 1512, 1511, 1510, 1509, 1508, 1507, 1506, 1505, 1504, 1503, 1502, 1501 }

    50

    Returns: 10.000066695263177

  58. { 1500, 1797, 2213, 2085, 1611, 1501, 2167, 1908, 1502, 1834, 1766, 2245, 1582, 2009, 1503, 2030 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677 }

    1500

    Returns: 8.544273888564282

  59. { 2012, 2034, 2014, 2005, 2031, 2007, 2001, 2056, 2054, 2021, 2047, 2023, 2043, 2023, 2094, 2045, 2076, 2054, 2073, 2035 }

    { 2042, 2014, 2034, 2045, 2051, 2017, 2031, 2016, 2044, 2051, 2067, 2073, 2083, 2012, 2034, 2015, 2046, 2051, 2074, 2085 }

    100

    Returns: 9.809191467090168

  60. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 2030, 2030, 2040, 2040 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 2030, 2030, 2040, 2040 }

    1500

    Returns: 11.872706135296516

  61. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 2085, 2085, 2085, 2085 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 2160, 2160, 2160, 2160 }

    1500

    Returns: 11.457969627214762

  62. { 1868, 1797, 2213, 2085, 1611, 2002, 2167, 1908, 1773, 1834, 1766, 2245, 1582, 2009, 2233, 2030, 2010, 2011, 2014, 2020 }

    { 2138, 2259, 2109, 2160, 2295, 2022, 2043, 2131, 1655, 1716, 1648, 1779, 1518, 1570, 1560, 1677, 1714, 1932, 1964, 1979 }

    1500

    Returns: 12.469319119764483

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: