Sortish
SRM 636 · 2014-08-25 · by Errichto
SRM 636 · 2014-08-25 · by Errichto · Search, Sorting
Problem Statement
Problem Statement
Everyone likes some sequences more than others. Every person has their own function which tells them how good a sequence is. For example, for some people this function could simply be the count of negative numbers in the sequence.
Jezalb's most favorite sequences are ones that are sorted in increasing order. When he sees a sequence S, he immediately calculates the number of pairs of indexes i < j such that S[i] < S[j]. He calls this number the "sortedness" of S.
This morning Jezalb entered a classroom and saw a permutation of 1 through N on the blackboard.
He quickly calculated its sortedness.
He then left the classroom and forgot the permutation.
He only remembered the sortedness he computed.
You are given this value in a
Later that day Jezalb reentered the classroom and saw a sequence on the blackboard.
The sequence was a permutation of 1 through N, but with some elements erased.
You are given this sequence as a
Jezalb thinks that the sequence seq may have been obtained by erasing some elements of the sequence he saw during his first visit to the classroom. He would like to restore the erased elements.
You are given the
Notes
- Pay attention to the unusual time limit.
Constraints
- sortedness will be between 0 and 1,000,000,000, inclusive.
- seq will contain between 1 and 2,000 elements, inclusive.
- Elements in seq will be between 0 and number of elements in seq, inclusive.
- Positive elements in seq will be distinct.
- Number of elements equal to 0 in seq will be between 0 and 14, inclusive.
Examples
0)
5
{4, 0, 0, 2, 0}
Returns: 2
There are six ways to fill in the missing elements. Out of those six permutations, only two have sortedness 5: {4, 1, 5, 2, 3} and {4, 3, 1, 2, 5}.
1)
4
{0, 0, 0, 0}
Returns: 5
All 5 possible ways are: {1, 3, 4, 2}, {1, 4, 2, 3}, {2, 1, 4, 3}, {2, 3, 1, 4}, {3, 1, 2, 4}.
2)
2
{1, 3, 2}
Returns: 1
There are no gaps and sortedness is indeed equal to 2.
3)
3
{0, 0, 2, 0, 0, 0}
Returns: 4
4)
87
{2,0}
Returns: 0
The only permutation that matches seq is {2, 1}. However, the sortedness of this sequence is 0, not 87.
7)
1021183
{855,1295,849,490,1911,1666,1586,579,287,195,1177,561,873,1099,700,1480,1083,35,947,196,542,254,360,1775,1847,1034,1128,1337,967,106,434,1054,798,983,970,163,765,1463,1117,685,79,1126,1124,546,916,1813,1600,806,1929,283,656,1681,89,1163,1630,923,412,728,1566,273,682,124,574,448,1349,1608,1411,1357,1470,1740,1792,1393,857,369,1109,224,1650,804,1839,1552,528,355,1802,1418,471,1116,310,419,353,245,1827,588,408,219,552,1433,94,318,324,1129,354,912,1859,1215,1761,1639,530,1156,735,1788,949,26,1024,1765,738,1696,1365,1950,1854,843,1528,686,309,925,1462,1795,1571,1049,1717,1935,592,1353,1442,1395,142,861,314,455,1142,712,1583,1318,1412,393,1957,614,674,1510,1667,242,174,1200,302,93,1273,1559,958,1011,1821,1568,114,269,190,1831,0,495,340,1567,1591,839,1069,244,973,1300,1059,1801,404,533,1356,451,1474,207,1317,270,1955,1519,1676,1095,1671,1768,898,1725,1245,1182,1198,240,838,1283,1711,30,1269,1951,896,1716,1783,14,969,953,1136,392,1434,1623,1606,1236,1726,1822,1603,1220,1493,1053,1350,1050,1070,149,1030,1976,57,636,1271,482,805,1665,608,1691,1332,1208,1466,461,1430,1856,1107,1984,1287,647,1299,1508,41,152,137,1487,1635,767,618,49,1029,1974,76,891,468,1233,602,631,466,389,560,1344,361,1341,1243,341,772,1595,271,134,648,1192,255,381,465,1486,844,1286,1945,1904,785,277,1575,1604,729,1067,128,1101,36,1359,375,1158,5,830,1655,1524,1372,997,1248,1641,203,597,202,853,877,992,1171,803,872,1441,425,644,1560,562,1085,256,1764,188,1161,924,1206,1956,1594,1654,975,472,1186,379,1512,368,571,1150,147,1475,1809,56,343,221,445,1861,1561,1304,880,964,1001,1018,87,1890,43,264,903,948,540,910,1088,70,1858,0,1971,1622,1118,1383,205,914,382,1103,1338,814,977,113,708,1785,1626,776,1863,132,1889,367,1014,1893,1830,55,719,1537,1166,629,1179,1525,159,1217,47,1728,1139,488,1140,1406,704,1450,1729,129,261,362,1274,1037,1112,841,741,1965,1471,642,759,198,143,582,12,517,168,1400,1513,1090,781,39,97,936,1016,640,1961,1565,1345,1388,678,234,974,1754,1986,1036,1732,1908,1642,1291,764,329,1309,732,1913,16,1763,649,945,449,462,1235,1375,1188,1563,1700,1241,1781,999,1044,965,299,604,572,0,1429,1197,1760,40,366,593,24,38,172,164,135,183,819,1305,1414,413,348,431,1980,1892,894,327,1580,622,263,1967,1625,13,845,160,875,1891,484,1741,665,227,1147,1601,278,356,705,301,1105,568,744,598,417,531,1080,68,1733,257,1,1977,1322,962,1451,673,296,1374,1263,502,1973,69,1618,761,184,1569,136,1102,581,80,83,391,246,123,1526,688,1402,968,553,1907,1334,1947,1468,420,846,285,1620,635,1251,306,331,411,1408,1617,1806,4,1205,1312,286,101,943,696,86,976,111,1873,1750,884,1948,162,1028,654,1444,1027,1380,795,460,1742,1554,1683,1662,415,1238,139,567,405,1281,1211,154,606,330,1258,1076,1267,585,594,933,1678,1523,78,681,321,390,676,1851,1368,813,566,1925,672,1979,1542,1425,944,539,112,1489,409,1900,345,1491,1938,1721,1264,864,769,643,1160,900,60,1421,1551,1670,646,1071,564,607,223,1013,1239,1106,1127,1838,1835,634,989,879,1153,1707,125,1927,1816,823,856,1324,1125,28,383,680,595,982,866,689,65,1254,1703,326,1026,479,1680,54,118,1697,1484,1645,840,1794,394,481,167,1895,1689,504,21,428,308,1244,917,723,1797,0,1115,1249,1193,1888,0,480,669,200,1363,232,547,1940,1490,1457,1438,454,1638,1485,1336,475,878,1162,17,577,1515,18,229,1415,1301,1964,1710,1459,508,1086,513,831,752,1351,699,847,529,1328,1377,1407,737,226,303,1759,297,1852,1077,250,374,91,1790,541,436,1498,1506,702,1247,621,191,1058,590,1056,358,141,543,1906,1843,1909,869,638,1196,442,1360,538,1387,837,1675,1634,632,1669,1392,996,1280,274,1409,918,862,1727,1864,1690,1609,249,583,247,1476,1543,1046,610,986,499,1612,1555,1436,825,757,1982,1672,932,1325,1664,1637,291,633,477,1885,1364,520,1033,166,1576,1953,1120,1180,1991,1157,1342,1903,1367,1469,1296,1194,402,1456,1039,186,1914,1849,486,279,378,906,192,1771,1673,1285,1587,1041,1511,1857,981,1094,426,536,50,315,650,1202,1335,376,1923,1677,558,1114,690,1564,1536,1310,1985,1602,72,1708,19,909,711,1452,516,591,661,1138,1837,1749,85,500,210,1926,1867,110,1825,1752,1942,1379,1135,1999,7,706,774,194,657,1222,8,1949,1850,37,1278,1596,1943,1003,1780,1539,697,703,1276,870,1302,1293,829,930,707,835,414,1306,1121,485,235,756,1212,1315,734,407,1311,104,950,1242,1361,919,494,1448,1722,684,1473,173,742,177,726,489,1660,1440,1288,397,1823,1648,1152,1989,1748,755,138,1092,151,236,1165,430,1226,980,120,988,281,1799,1649,1767,668,639,259,1653,507,1507,1527,1482,1467,45,1659,1405,1803,145,81,745,730,155,1610,1692,718,753,1423,1701,410,20,848,1167,185,1437,1988,15,1535,1091,1784,653,1151,243,1930,619,385,457,1340,535,1842,1739,100,1464,483,1123,75,95,213,260,0,897,1862,779,433,351,1221,1556,1931,1055,811,1937,71,913,667,941,1010,1170,1460,487,1770,1465,1005,350,1020,1234,251,935,292,1628,0,1841,1019,406,332,225,1148,1146,1699,206,307,505,1597,1562,942,651,766,1916,874,82,9,1100,1737,934,161,905,1413,1661,750,1174,370,556,907,652,178,1082,90,627,1992,1477,963,551,64,371,1176,1427,1277,1159,2,1252,372,1901,317,792,1793,493,777,743,1145,1686,253,1445,1658,1966,1744,1396,733,937,1688,1607,126,1227,0,1546,339,1883,1621,1327,694,611,1181,1584,889,121,1479,1416,1514,1656,545,222,474,824,693,1743,150,714,473,1499,599,554,1589,1579,1812,1378,775,1840,252,1458,1990,32,851,1898,959,1131,1040,1225,453,1297,544,807,204,954,523,63,1804,1915,319,1203,1089,605,328,0,758,850,1807,834,0,492,1022,927,144,298,25,637,1187,0,421,1137,1509,1702,1048,762,1061,1614,0,511,1023,1995,1663,731,122,1132,888,780,1386,587,276,1373,180,1582,659,1550,1970,432,189,400,1993,1731,1504,1627,1314,380,1917,1693,424,1592,1074,1461,548,503,133,1371,1122,788,797,1522,603,1204,1826,1008,1237,1756,1214,422,951,1709,312,1134,1636,1516,347,1782,1880,464,1805,66,435,1175,1084,721,1578,1042,519,1834,1936,1068,1975,1773,1960,1815,575,701,812,1779,446,1918,1495,1616,300,153,1154,1191,1298,1714,1933,109,459,794,565,984,1185,1577,525,1668,1343,399,103,1410,440,1755,452,1981,1811,265,333,821,956,1724,1517,1449,596,1972,746,1719,1424,926,288,1354,1346,1035,713,1454,337,957,1715,1685,1078,437,1110,1149,751,972,1774,695,563,778,1240,939,1877,966,1887,1934,1189,1954,179,1712,216,1845,1540,158,773,1905,1875,201,1944,1255,1141,1651,822,1738,1355,170,77,1320,904,1687,1313,600,1718,979,863,881,1075,802,1818,450,1652,1294,1866,116,557,882,1230,1520,280,1173,859,518,1541,131,1558,1730,1544,578,687,1899,1209,978,510,62,171,876,1006,1518,993,423,1246,1097,860,2000,1096,899,438,1087,1632,33,1778,1257,817,771,1488,809,789,1066,946,885,1879,220,199,1860,1290,816,620,952,1553,1401,506,612,961,1155,218,1832,1534,799,197,782,826,509,893,1093,630,709,387,1323,3,1786,1073,1829,169,140,1910,1757,1924,1876,323,698,736,1308,311,1978,364,1330,34,304,272,524,233,241,108,833,1419,1289,901,1428,44,1231,1869,212,156,1213,1573,1394,1963,1987,971,130,320,96,1531,1959,1455,1574,1496,6,645,1481,1824,1533,1819,491,791,238,1435,1224,334,790,871,1870,800,1184,335,1787,1920,1169,336,1113,810,1266,887,854,10,1422,1766,1399,1820,1219,165,1503,357,1391,770,1588,293,1735,613,187,1275,1747,655,1420,960,915,1047,1329,359,1098,115,1713,1853,1736,1501,427,1817,1994,497,1321,1404,266,1720,1624,1218,1548,1810,1647,1941,53,1494,1366,1679,1268,67,215,1216,537,313,148,534,670,1833,88,931,691,710,998,1417,346,559,938,514,820,584,1723,1796,248,469,624,995,1919,921,1370,955,352,692,677,679,827,377,852,717,576,868,1108,985,1190,1432,628,282,1382,832,294,0,793,660,1025,1896,23,1031,663,1939,865,1633,1529,928,363,1674,476,1789,1038,61,1051,716,623,127,1629,895,439,1358,1897,228,349,1381,401,1201,217,1952,1798,1878,239,784,1928,1144,748,1684,458,1492,1547,683,418,1262,573,1874,463,1997,1644,1706,107,181,1316,1130,1922,725,1682,11,470,501,1958,615,398,496,715,1695,22,1319,1228,386,1998,1062,1881,467,119,262,920,208,1769,1279,31,720,1207,1339,1776,675,1376,1453,84,512,1472,1172,1284,1844,1229,1497,52,867,749,1307,1777,1921,1705,801,1884,1500,1872,456,1538,1007,1745,1530,929,1762,0,1808,1265,1282,1983,739,231,1646,444,1063,1753,1272,1017,1352,1210,373,1746,1326,1599,1640,1478,441,1260,836,902,1384,515,1009,403,1619,478,51,580,92,1570,570,1043,1751,1505,429,911,724,105,146,73,1758,1052,1389,1912,237,858,258,27,1572,1657,1447,157,1557,1581,1390,1734,1593,786,1270,1057,1598,1072,1932,586,1012,1613,322,1814,1996,1223,59,842,1256,1855,1081,1483,658,1698,1836,1643,1443,601,290,1250,617,1002,589,1398,1143,1439,922,532,1502,193,1347,1183,1585,549,1032,1962,268,1021,1894,1397,664,175,1064,1532,498,102,1865,365,641,267,209,1694,763,443,1164,1104,1303,1004,522,555,1704,609,1199,99,1292,295,1333,892,29,760,990,671,727,1882,1868,808,1195,1605,1615,1369,940,1828,1259,176,818,1403,994,42,46,787,1178,284,616,625,342,48,1232,416,908,305,1331,1549,722,991,662,796,1045,214,275,395,890,1168,1060,1521,1119,1065,1846,1946,338,1902,1253,754,1362,396,289,1015,1545,1800,1261,783,1446,883,1886,1431,1079,98,527,316,388,1133,1611,1969,1848,666,550,1385,569,521,626,117,1111,1791,325,211,740,747,1000,1968,1631,1590,987,768,886}
Returns: 27332616
2000 14
8)
70
{8,0,0,0,0,0,0,0,0,0,0,0,12,0,0,0}
Returns: 2539199134
16 14
Submissions are judged against all 144 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Sortish with a public method long long ways(int sortedness, vector<int> seq) · 144 test cases · 2 s / 256 MB per case