AqaAsadiGroups
SRM 787 · 2020-06-17 · by a.poorakhavan
Problem Statement
Aqa Asadi holds regular coding championships between his students. There are N students who want to take part in the next coding championship. All N students are sitting along one long desk in the computer lab. Aqa Asadi wants to divide the students into exactly k groups. Each group must be contiguous, so that the students in the group can talk to each other during the contest without disturbing the other groups. The groups should be as balanced as possible, as defined below.
You are given the
Calculate the smallest possible total badness. Return that value multiplied by k^2. (It can be shown that this value is always an integer.)
Constraints
- Skills will contain between 1 and 500 elements, inclusive.
- Each element of Skills will be between 1 and 4000, inclusive.
- k will be between 1 and 500, inclusive.
{1, 2}
2
Returns: 2
The optimal split of {1, 2} into two groups is to split it into {1} and {2}. The average skill of a group is S/k = 3/2. Thus, the individual groups have badness (3/2 - 1)^2 and (3/2 - 2)^2. The total badness is therefore 1/4 + 1/4 = 1/2, and we should return the value (1/2) * k^2 = (1/2)*4 = 2.
{1, 2}
1
Returns: 0
The only way of splitting {1, 2} into just one group is to leave {1, 2} as the only group. Its badness is zero.
{1, 2, 3, 4}
2
Returns: 8
One optimal split is into {1, 2, 3} and {4}. Each group has badness 1, the total badness is 2, and the correct return value is 2 * k^2 = 8. Note that the groups must be contiguous, so we cannot divide the input into {2, 3} and {1, 4}.
{2789, 1021, 738, 3784, 3123, 2225, 3289, 1619, 3677, 1891, 836, 2881, 577, 1104, 1450, 2632, 2478, 2538, 3397, 2644, 3017, 2966, 2244, 2565, 3787, 1902, 3434, 1198, 640, 353, 77, 2391, 3753, 654, 248, 3516, 603, 2796, 2953, 1933, 2334, 3685, 1459, 3404, 848, 3863, 414, 978, 2495, 3954, 1218, 2825, 466, 1180, 1904, 1619, 1057, 3536, 3017, 1378, 2424, 2874, 2148, 3934, 3641, 61, 1100, 739, 406, 461, 576, 1503, 2459, 981, 242, 2200, 2050, 467, 1321, 325, 1532, 3191, 1951, 2288, 3919, 1704, 290, 570, 595, 830, 1303, 1111, 980, 3337, 2483, 3214, 2611, 2761, 736, 2810, 581, 3187, 2303, 3148, 2546, 1043, 736, 486, 2519, 1444, 2667, 2369, 997, 1817, 2138, 2888, 3647, 888, 796, 923, 288, 346, 2420, 173, 2707, 2733, 3641, 839, 793, 1266, 2100, 3843, 2695, 2047, 2500, 945, 613, 1949, 669, 533, 3152, 1451, 2724, 3623, 3096, 953, 2133, 3665, 963, 2382, 3486, 53, 2408, 2595, 1985, 741, 1845, 3654, 2998, 3017, 714, 2744, 3558, 3484, 3612, 3023, 2769, 2063, 2163, 821, 1897, 3909, 1740, 3975, 1365, 2229, 3095, 534, 1935, 1900, 2074, 1801, 486, 904, 1324, 1882, 3805, 1342, 1467, 3733, 906, 1172, 1735, 3900, 2040, 3240, 388, 2405, 165, 1063, 3292, 1498, 1381, 1719, 1259, 1752, 3613, 109, 3105, 945, 2344, 728, 324, 1226, 2422, 3348, 2379, 3005, 104, 1240, 68, 1624, 3350, 3497, 174, 1181, 713, 1380, 3456, 2080, 2337, 1432, 3360, 1164, 112, 3849, 397, 1342, 1468, 2287, 2550, 3240, 1537, 949, 353, 1840, 1709, 2426, 1445, 3438, 1987, 2355, 464, 3409, 3992, 3143, 353, 1115, 3673, 2354, 2351, 1024, 2115, 3714, 1792, 876, 2986, 1533, 2451, 2426, 1043, 281, 2519, 3357, 633, 2659, 3409, 571, 843, 3513, 3162, 1100, 1964, 2704, 447, 3200, 531, 3278, 1759, 2230, 3881, 1200, 1073, 3366, 2061, 1798, 3771, 3576, 1651, 1202, 1884, 3595, 128, 1229, 1123, 3759, 3184, 1186, 2389, 3691, 1585, 2065, 2059, 2712, 1861, 3021, 2417, 3811, 644, 2975, 1705, 1327, 599, 2241, 774, 2129, 862, 99, 2769, 1682, 2795, 1033, 1736, 177, 1893, 3818, 2330, 574, 70, 211, 748, 1600, 3614, 3619, 503, 1680, 3149, 2156, 1383, 3676, 3468, 2616, 2685, 357, 1317, 3458, 1551, 3073, 3607, 1177, 2467, 505, 3123, 2400, 535, 44, 3009, 3985, 2876, 2379, 3996, 2453, 3318, 2971, 1170, 3053, 2302, 1494, 101, 3149, 192, 2954, 1196, 1691, 3869, 1464, 243, 181, 2570, 2742, 214, 584, 3664, 782, 2346, 1785, 3242, 829, 3253, 1792, 1450, 789, 561, 1384, 3187, 1659, 3693, 2321, 1728, 713, 2892, 366, 2620, 3309, 1219, 3400, 3081, 2601, 255, 1048, 1657, 2353, 989, 3857, 2264, 3280, 145, 2708, 736, 2691, 3904, 2137, 1538, 220, 2757, 2605, 3812, 1952, 2703, 1870, 3070, 554, 3489, 1489, 2780, 3974, 2642, 1053, 2399, 2486, 3531, 3182, 2396, 145, 1163, 2482, 2555, 3807, 1158, 751, 1017, 3518, 3522, 443, 1574, 1888, 2008, 1859, 2184, 3019, 1433, 3461, 119, 439, 2183, 3061, 3071, 2771, 2135, 3772, 1057, 3937, 1366, 3924, 241, 3478, 1825, 2637, 409, 1691, 491, 1836, 1909, 3406, 2459, 2823, 1014, 3522, 1867, 2154}
23
Returns: 6690768126
{460, 387, 3279, 2083, 965, 2963, 1359, 2013, 1299, 3651, 3603, 2805, 3681, 2274, 1425, 2929, 3152, 1361, 2580, 3663, 2933, 3431, 1435, 2204, 536, 1772, 3063, 3486, 3861, 2046, 1617, 2603, 2655, 2319, 65, 2447, 3032, 3780, 1144, 3818, 3739, 1592, 1239, 3856, 3987, 983, 1782, 1031, 321, 995, 894, 1580, 2777, 2355, 1263, 3438, 3365, 3151, 2523, 1138, 1441, 533, 1129, 2413, 2589, 855, 787, 2157, 2207, 1435, 328, 1553, 1694, 1658, 2251, 364, 1800, 3969, 2866, 3302, 1372, 787, 3207, 1691, 3921, 3876, 2219, 2618, 846, 1855, 3566, 103, 3439, 1794, 856, 3449, 2407, 509, 1700, 2653, 1720, 1143, 3487, 3345, 1020, 2985, 3053, 1578, 1024, 1984, 2181, 3822, 2244, 159, 1200, 1115, 3484, 3163, 910, 2270, 2450, 3677, 208, 1437, 225, 2308, 127, 3374, 91, 160, 2356, 1757, 1381, 1272, 1342, 1322, 3126, 229, 1343, 2568, 1915, 2325, 3439, 2400, 1878, 2697, 2712, 3468, 3642, 1463, 2488, 2588, 881, 72, 3970, 3252, 3734, 187, 1245, 1356, 1147, 576, 707, 2095, 1061, 2782, 2244, 3548, 3083, 559, 1440, 2664, 26, 3806, 881, 2842, 436, 560, 639, 2798, 3564, 3128, 1545, 3763, 1643, 3072, 67, 3789, 2703, 1703, 2802, 3379, 2375, 3006, 82, 3570, 3480, 426, 3441, 1544, 3515, 581, 2769, 266, 28, 3389, 1353, 574, 477, 3412, 2917, 2114, 3217, 1918, 1506, 1603, 3489, 230, 2739, 2695, 1514, 2729, 1023, 2340, 3389, 1401, 1440, 2790, 1022, 2331, 1861, 1133, 870, 2954, 3185, 556, 193, 1938, 2330, 3148, 3985, 3957, 2410, 2727, 521, 2154, 2626, 2637, 2290, 985, 3122, 130, 3273, 736, 418, 2782, 223, 2897, 717, 2444, 1272, 1713, 192, 3307, 3885, 3771, 3264, 2640, 3658, 955, 993, 1858, 3536, 2772, 3695, 2813, 2068, 922, 2505, 2960, 3102, 3385, 417, 62, 3595, 684, 381, 161, 2412, 2918, 1401, 2498, 3877, 397, 1411, 1155, 2447, 3226, 2174, 3125, 1302, 3066, 959, 2466, 379, 3760, 2547, 292, 1875, 3184, 1623, 2604, 3046, 198, 2590, 284, 3729, 3821, 1103, 3373, 1764, 633, 3877, 330, 2373, 1901, 3693, 2643, 1420, 1061, 267, 3291, 1221, 3886, 1269, 2539, 2097, 3017, 662, 1725, 3428, 2860, 2349, 1761, 1545, 288, 3820, 251, 121, 3716, 1401, 1699, 2280, 2024, 1616, 868, 345, 1619, 3486, 3485, 3268, 862, 232, 1027, 1239, 3895, 514, 1277, 498, 2559, 1753, 2215, 970, 876, 1386, 463, 70, 808, 3240, 1083, 3685, 2128, 3738, 1730, 2871, 2966, 3034, 1582, 735, 1311, 3959, 3168, 3768, 453, 1076, 972, 3916, 2006, 2247, 3608, 2238, 3027, 3259, 1154, 1506, 3858, 942, 951, 896, 3933, 3027, 1725, 1684, 1073, 2610, 426, 1713, 2976, 643, 1130, 2937, 3855, 3287, 1149, 1543, 2968, 559, 2870, 1701, 138, 1282, 3293, 3670, 2500, 3996, 1134, 2797, 1181, 2233, 344, 1716, 2463, 3694, 1471, 1959, 1959, 3873, 3611, 2134, 3527, 2060, 2583, 1254, 933, 2782, 1042, 3121, 2489, 3129, 3873, 2657, 115, 1813, 427, 2105, 690, 2108, 3852, 3628, 3406, 204, 723, 3876, 2063, 1144, 1763, 3580, 403, 583, 310, 359, 1836, 1908, 341, 1255, 64, 2860, 3521, 2070, 1223, 1779, 750, 2881, 1457, 1727, 738, 3495, 926, 1563, 635}
382
Returns: 35780666940688
{1, 2}
5
Returns: 80
One optimal split is into the following five groups: {1}, {}, {2}, {}, {}. Note that some groups must be empty, as k is greater than the number of students. The average skill of a group is S/k = 3/5. Thus, the individual groups have badness (3/5 - 1)^2, (3/5 - 0)^2, (3/5 - 2)^2, (3/5 - 0)^2, (3/5 - 0)^2. The total badness is therefore 16/5, and we should return the value (16/5) * k^2 = 16*5 = 80.
Submissions are judged against all 48 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AqaAsadiGroups with a public method long long minimumDifference(vector<int> Skills, int k) · 48 test cases · 2 s / 256 MB per case