11031 - Looking for a Subset

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Bert
New poster
Posts: 3
Joined: Mon Jun 19, 2006 9:57 am
Location: Hong Kong

Post by Bert » Tue Jun 20, 2006 4:04 am

sohel wrote:I have solved this problem using LDS .... I am not sure whether it can be solved using LIS.

Reverse the input array and apply LDS. Then isn't the last value, with a seq # more than the reqd value, the first number in the answer.
Thanks so much~ :)
I finally got AC, it turns out that what I kept doing wrong is that my dry-run result of the bsearch on the paper was wrong.... what a shame.... :oops:

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Tue Jun 27, 2006 10:16 am

Hello, I tried to use LDS algorithm to solve the problem.
And I have passed all the input/output in the board.
I handled negative inputs and duplicate values, but still get WA.
Could someone give me more tricky input/output? Thx

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Post by viniciusweb » Fri May 25, 2007 10:03 pm

Ok, here is some REALLY BIG test case (just one set though)

Code: Select all

10000 100
-880 3346 7245 -286 5242 901 573 4369 4548 1444 1676 4740 1673 8398 2849 5137 -974 1489 942 7320 2850 3843 4504 428 6754 3744 1603 8897 3897 2771 4453 6809 8381 1977 4944 1656 2406 -949 3664 1256 6400 7914 409 -886 6432 4756 -785 8754 6939 -875 2064 6065 -746 2101 1506 8547 2902 462 6560 324 3932 1533 8013 -822 3245 3969 4782 136 6879 -882 2590 2916 7401 6593 8520 2150 -524 5579 3700 2605 2987 -513 5978 1082 7177 4389 4084 3279 2273 1663 7153 5931 3494 4827 -843 8087 7985 1356 6286 1212 6238 5272 2518 -763 8705 2821 7920 -946 5644 -218 -240 2828 7475 2641 5350 6812 5880 8268 598 -753 8562 1456 7928 4178 5528 6741 5410 1017 513 1495 5687 3285 -371 8822 8511 8649 4358 3923 3527 8603 7027 948 2026 4373 658 2174 8778 7996 2753 411 201 5192 4621 991 2433 6414 -249 1452 2691 1562 2675 5428 978 6676 2329 8638 5682 2391 5814 356 7192 8537 -8 3599 1502 4544 8493 823 2584 6415 1542 8956 5752 3526 2237 899 1464 1275 5580 7443 -730 7871 7084 7000 5806 4327 8024 8212 110 8416 8590 -630 4195 4970 3936 8465 -223 8330 505 -189 -834 8885 2002 6502 2933 8485 8073 8757 5180 914 2136 8148 7524 -85 3707 3190 6638 2739 2823 2985 -431 12 2571 4251 5962 1691 7404 2421 3264 5182 6866 7777 7474 4392 -960 5158 2970 6952 117 8910 774 3847 2546 -14 6295 1270 5743 4120 5660 6298 6426 -752 1483 3373 6437 3480 821 160 4754 -903 4090 4048 8301 -770 3120 8684 7133 4881 5604 463 786 4363 1064 3328 986 5335 6312 8987 4591 7269 6926 973 1376 4167 113 -798 4985 8904 3251 6811 612 5288 8973 5526 516 6710 1834 7184 5738 108 -747 8277 7010 -476 575 8858 6099 4899 2324 194 7227 7032 5535 157 3704 3145 6469 7538 5261 5757 8935 7683 765 8867 8765 8249 -436 -455 7892 8592 2517 6249 1942 8648 1594 6136 1817 5878 2223 3441 2785 1419 5091 1479 2617 7093 6144 2885 6390 8877 3074 -877 729 8224 4808 -885 849 4390 1892 1223 7079 6307 1504 3595 926 2634 8441 6899 1385 1135 3421 4632 5755 8612 8663 4401 1150 5815 1196 8306 902 3832 -497 4926 8965 4151 316 412 6349 5530 5430 8957 5753 -803 8052 4663 5895 879 3227 8433 8925 8868 5473 923 7674 3539 2231 4884 3536 6093 6982 180 6958 7732 890 5848 7221 3179 5136 3156 8047 6447 6475 6695 8466 6830 4123 -884 1339 3708 8076 309 3161 1756 2978 1619 5657 7067 6923 2008 2564 -408 5801 5715 974 -740 -772 2636 7811 3885 4874 -186 4616 6718 5621 4990 -471 6362 1352 2244 -618 7239 4474 2874 293 2330 5321 2797 3679 5379 4430 5617 1824 151 -964 2139 4546 1263 5940 7671 888 3168 7563 5820 5541 8525 3878 2861 1081 8502 8189 8529 7145 3609 7303 2863 3922 7368 7998 7468 5997 3491 5305 7384 -692 5922 1430 -559 7342 1797 1535 4873 7945 2068 6602 18 403 130 133 -637 5160 6248 2086 3211 2240 851 4951 6273 8775 3153 -400 421 8712 1729 -751 6165 7763 1591 7751 1734 992 3872 8884 7963 4826 981 109 436 8135 8998 6835 8291 503 1296 6440 3989 983 8182 279 -956 6544 3248 6283 -969 -757 -295 2930 -804 2365 1375 5988 6566 7739 6647 3377 3364 2848 568 4773 -13 5756 601 3757 8102 -557 8974 3710 5344 -178 6631 -538 -598 995 5850 4265 8886 1166 5816 4739 4246 -654 5031 4513 2006 5053 124 2527 7781 3372 -625 6915 5932 1799 1485 -727 6156 904 3504 5587 2111 1378 1366 -53 1908 5968 7714 8353 -612 -31 184 6233 5564 5161 955 4128 154 2900 4039 298 7753 4528 4653 5859 1327 2541 2277 6463 1946 73 8315 433 8790 3822 2134 5238 2290 -52 7394 5525 2652 1383 -247 7789 7214 1248 3195 2746 6132 961 4249 -139 6250 7564 5707 6361 4139 5106 8342 2764 8238 3400 6874 2789 8847 1735 3917 6239 2319 2681 3159 8383 8578 1050 -434 5000 3258 4809 5690 1842 1147 64 1077 -86 971 2295 2042 1072 5737 8977 596 1692 2642 1848 -440 3371 2839 7142 670 1547 2331 8058 468 3727 3556 7074 3747 1528 5532 5353 222 -270 8643 6318 2494 1255 8450 5069 8746 4402 3541 7319 2935 -678 6160 489 8002 5407 7358 2952 8312 -56 -909 2459 248 -590 679 2221 6111 1119 8829 7195 6615 2964 3723 2957 -62 862 1937 3645 3670 1054 2522 5641 6580 816 5264 2278 2180 2929 7238 6653 1267 8022 7430 6810 3752 2918 1518 3715 1015 -82 2130 4611 8821 682 266 6576 8144 62 8540 4791 2308 -629 5372 3687 6997 3477 30 7498 3107 7827 5220 8979 2977 -272 7725 -509 4434 7190 7316 7837 4487 3597 287 6611 4927 4325 6252 4897 2050 3402 -345 3458 5061 3278 2151 7109 2181 -33 6000 258 2709 958 2594 5825 5348 349 6834 -500 -556 168 3692 1807 4002 4376 2420 5873 7249 5479 985 5913 6826 4340 4180 -401 3022 4674 8767 3205 833 -76 5157 1316 7951 8209 3273 611 6766 147 -283 8913 4736 4896 4599 6959 8405 1407 5725 2796 3095 3506 -511 8333 -601 1526 3470 3931 4760 5884 3339 3705 -285 -994 8122 6261 4142 4004 8937 6723 1587 6175 334 6155 4510 5611 4147 3359 3436 5441 3864 2798 391 1129 771 7054 6847 8579 1260 3495 58 5994 2521 1812 5452 7481 6026 2858 8288 5653 6770 5812 2915 -713 7734 5265 5179 5904 6196 7291 3970 7622 8745 4540 -284 6732 6173 6479 1474 4620 4767 4183 1993 8788 5614 2601 5080 -599 3673 1416 6343 2283 4529 1771 -23 -372 8075 8100 7199 4132 7447 -365 5600 6053 2988 850 6772 -742 7678 -967 -468 5716 5586 1009 5256 6122 8796 2154 1975 2555 2623 1176 134 5684 8958 6188 7167 1210 2205 4150 7923 -859 4898 4592 5071 4344 -626 3503 8661 53 2495 -914 4398 4028 857 4585 -183 3215 4060 2454 3928 -484 1132 1350 2751 2118 1703 4480 8814 2524 3802 -148 1823 4361 7388 4268 630 5114 -966 2070 5330 -93 3024 4152 2611 76 548 8396 -474 2400 7472 6980 7482 4572 8752 7931 8337 103 2327 2424 -847 7149 7095 -932 1100 2928 4036 7572 5827 2140 1410 1103 4805 5504 2566 2725 8471 4382 -697 4160 3828 3635 6412 3662 6359 1273 7819 -291 7504 6712 6697 8835 613 7656 5094 4707 1888 7542 3601 192 6633 3467 730 996 4541 6851 4579 8758 7634 3848 2845 3334 5529 4457 4307 8290 -64 7661 -180 4409 3247 1564 8552 384 1653 1112 1061 312 3461 251 4717 3315 2030 668 1919 6624 4110 77 8282 3806 6428 2063 6001 3462 1808 6757 7607 2574 1149 5052 4100 1271 4965 401 8864 2595 -682 -352 1916 7465 7253 6133 3532 7137 5423 2662 1741 4766 5892 2010 3693 8259 6738 3424 -422 79 2553 4561 143 -101 5235 8482 218 8607 6430 5029 7603 2362 6746 1602 6051 7120 6996 2613 6787 3600 4179 7008 1094 4914 1109 3417 1001 4427 6352 5397 7157 2747 1333 6081 417 317 2986 637 945 4017 7992 5134 6820 7099 8124 8318 8181 8553 8723 -119 7553 6714 3624 2166 -731 8130 -714 40 6708 1544 4226 6545 603 6637 3049 4488 -894 5186 3533 4882 3850 -870 1400 4617 6468 5380 2188 239 1509 -930 -516 1991 2258 -863 5475 6865 6991 123 7942 1641 3476 5184 5839 3447 812 8219 5406 -796 1880 2191 3305 8708 8069 8694 4723 1861 -142 1657 31 1541 1761 407 6085 7016 809 6665 5642 4727 -187 3570 7821 -755 5171 2960 1640 5438 3380 1205 1922 5730 -348 6030 4714 2700 7561 7451 5643 7894 6931 6434 4058 -790 2731 8072 1787 6876 7569 7549 8568 1701 255 6435 -35 7600 8730 1984 419 6481 6371 4252 1238 2740 2047 -648 5202 6355 1115 6267 905 8755 7277 402 4396 5832 3111 -239 546 896 719 558 1076 5445 3957 5487 6917 -60 84 -584 6788 4169 2500 224 491 8358 -562 7565 2318 3749 4229 5123 7776 -635 1083 4865 6409 2325 2357 2304 8713 7861 3482 8706 6590 8343 579 325 7927 4144 7434 4594 3100 7971 3184 1028 7878 1745 7757 7375 -759 4603 8494 3007 3413 -379 1345 2442 5592 3322 8090 2519 928 8295 4550 684 7788 5426 3451 5206 2884 211 1434 5440 -420 5090 8063 2396 8313 -169 2092 3546 1802 7386 6886 1632 237 501 2476 3669 4567 535 2903 5942 8969 5241 8480 6050 -32 387 4095 4598 8954 5381 7580 880 -267 -561 5933 8801 2509 4493 -910 4044 8891 216 6740 6587 4956 4407 649 5501 1450 6268 2901 4638 8608 467 3331 800 865 5976 2755 7189 8941 822 3550 6575 1760 -104 4436 3475 4082 3737 3884 5274 6197 7381 3523 3840 706 3542 3243 8588 1947 5742 6691 118 4683 3130 1589 5639 -298 6041 5252 3639 3502 5779 2490 5842 -460 1429 7348 6018 5999 3123 4922 1025 7665 8429 1233 5748 2445 8127 4491 2963 8793 1181 1998 3457 1453 5513 6521 5291 3028 7293 4536 7041 1624 5399 -642 2085 6571 -242 2417 4414 4573 1295 7705 -38 1099 4016 7517 -965 8759 1503 4062 8719 3135 8112 5722 604 5312 4742 4045 6785 -734 6815 3071 2754 2926 3059 5692 1415 8332 2877 561 7228 6216 3320 3350 3573 2572 8434 5218 8685 1792 7378 6974 1266 7409 -314 8586 4466 1622 4687 4372 5133 2947 4768 8549 4020 6291 3176 969 4276 4482 3361 156 2722 3812 8915 3915 7459 5496 1616 8408 2458 1730 6837 3433 -879 5568 5543 4976 6236 3853 5039 -818 2560 1000 3321 7750 6406 1530 5140 1789 -366 6761 1847 1758 3720 717 8049 3592 4403 4141 5162 6709 5511 1941 4300 8088 8454 7720 5945 -628 6244 8390 790 3053 2262 576 7387 4937 8131 -30 4292 6703 6220 7989 3787 2694 7340 6822 -330 5303 5694 177 3443 1655 7961 7047 7593 2071 5930 8008 7181 956 2535 1532 3318 4935 3431 6134 8134 7406 2168 5890 6607 372 323 2186 4892 5780 -656 -151 6776 4511 8500 3564 4999 7993 -280 3552 1854 6169 6903 1668 217 4690 625 5175 8195 3524 -57 6046 424 8916 8486 7922 8359 2298 8564 3390 3745 7583 1985 1896 735 1096 2229 6388 6972 2632 4547 6266 946 8484 4274 4247 5085 -575 4590 -819 2384 1075 4209 4817 3746 5559 6301 2637 5478 5431 5109 1682 28 5253 4417 1313 3761 2575 7616 7587 3013 352 243 4426 7212 8066 5065 2932 1200 5928 1857 5982 2080 6601 -745 6224 5459 392 7994 -922 4967 620 2193 2124 8882 8743 6125 8832 2105 3423 5637 1898 1705 265 -477 3953 3064 -643 2099 4377 3481 314 3725 3374 8810 4353 4759 6082 8061 2813 8825 388 3702 6532 2793 7805 8041 7925 2121 107 1617 1766 5362 -589 1768 4075 2761 1648 8938 3282 5944 -145 2523 6092 1558 208 1116 8631 8740 7964 44 5128 4633 5718 6584 7325 7088 3014 7050 5323 -262 2724 1794 6227 5190 1446 3189 2141 5313 465 2693 4802 990 5790 65 1629 1314 3349 3703 8321 3384 7779 4743 6100 5050 3079 4210 1178 4752 8208 4595 2416 3 7138 -676 3078 2939 3935 1634 2280 6189 5153 3252 4332 4351 7935 5322 6672 4757 545 3422 5706 5767 -111 7790 3272 911 6686 6752 -231 7437 473 3080 -165 7164 7441 1723 7487 5680 4538 4103 5793 6623 2528 1686 8241 4460 2309 1213 2786 6287 383 6933 3861 5138 1689 5491 4223 5448 552 6951 2532 1905 1814 4424 5073 7471 2094 8593 6570 4855 7094 6701 348 6071 1209 6727 1290 6358 2294 3963 3906 5427 2824 1284 1397 1074 2263 2664 6897 6274 399 8214 63 6375 7080 4272 5618 5435 8811 6424 7895 230 5608 8142 2196 1288 5522 8751 -40 2909 7260 5670 358 7353 6758 8944 7886 5979 4975 6470 5920 1596 7649 -655 6878 7904 3618 7020 292 1992 1970 -102 8922 -596 3593 3173 6315 -441 6659 -684 5170 6379 3362 140 -862 4467 884 5688 6922 2 -968 2450 6337 -319 5891 7311 6219 66 2765 8838 3356 1346 8164 1827 6681 7772 2855 6280 7310 4685 2371 837 3169 8032 -326 8587 6342 19 148 3378 6420 2368 3015 6060 -416 1757 -287 1308 6488 7328 3559 6854 -514 6689 7048 -15 8276 3797 7489 8514 2000 7323 8210 5831 8850 3891 5954 426 6960 4338 2577 1032 3051 -355 5225 2250 -257 2539 5292 3416 665 4201 6621 4365 2804 8670 8731 2776 681 8978 2028 -897 3769 7467 3874 1006 2878 2287 7539 3206 5446 2794 4472 -955 4523 1225 1325 -265 -414 -816 7727 1490 7278 4986 3900 4049 2423 1476 486 4347 254 170 4716 3735 6271 8352 262 5120 7697 115 7701 1134 6564 8834 3240 4862 4050 1538 6649 8305 -20 6483 5569 6044 4122 -349 4497 7770 5324 3876 -307 8505 8600 1698 -435 908 5033 3718 1058 788 7191 -892 126 1618 -695 3254 6760 -18 1059 6408 4613 6957 7426 4442 8949 -641 2643 2361 5633 7613 6150 2714 -861 2039 8308 3628 205 7028 6510 1607 4906 -324 3140 4500 -171 930 -351 8294 6918 734 410 5841 2256 6535 2592 -530 5662 8442 710 2469 1555 5750 1004 4173 560 3964 6585 7251 1315 5721 1505 7043 8555 2020 -362 4725 3345 452 7411 1279 4868 5914 1329 3118 4170 15 7644 6364 1160 3070 1560 1334 616 -219 2783 6814 3181 4924 6540 5956 6292 3455 8769 1699 4260 3004 4667 4728 8874 556 6784 7365 2894 5105 2508 7525 8116 8439 5212 8492 -292 3396 7132 -123 1609 7508 -787 4019 3551 -824 7089 3468 2965 7485 4755 1282 -904 7896 7845 918 2073 3815 8984 -712 1996 7813 4709 7160 5542 6790 4320 -835 3619 5624 8900 4484 8035 1651 -116 1696 2412 7155 500 5466 -9 -681 7163 4950 -342 7668 6256 772 2866 4271 445 2837 -438 6885 3594 -707 5549 8464 -778 3579 2232 2805 8737 6955 4831 1600 -991 -815 3901 538 2069 2905 3122 591 8921 3980 2351 2728 1199 7071 1168 -623 1595 6322 2974 7966 694 -383 3232 4184 1226 2054 3286 3998 308 8806 8929 5025 1219 4929 7497 2925 5711 2336 623 8672 1786 2997 3187 -591 6289 931 8356 4445 8724 6332 4509 313 -979 3438 3975 8777 8565 4037 7704 5191 1121 1182 172 1764 4219 3694 6867 3808 6010 4816 7265 7209 268 8780 3208 1307 2653 2873 7289 4205 721 6747 3701 3634 4287 6181 2102 4203 7141 6131 6828 -817 3513 7615 1752 4751 2578 3587 7428 3742 2132 6340 -276 4027 5681 7496 1697 7769 -456 965 3538 6028 1206 4586 7213 6466 6277 7073 6662 5606 -733 6106 7589 190 91 7804 646 -521 4789 7024 -657 5266 4833 8228 1063 1373 3653 -445 7491 -191 2679 4066 4938 5223 3712 -605 3006 -485 7287 3288 8601 2041 6932 342 2462 773 1924 3193 448 6630 2037 7645 6626 4046 3160 6221 6215 7063 -184 6613 534 -339 2224 6176 8805 7136 7654 7798 8576 3984 173 8875 6792 2946 8266 -768 8950 2138 7578 7112 3401 6320 1344 5519 2802 8089 699 3048 3067 8322 1863 1093 8369 1586 246 7940 780 -669 -384 5347 3852 651 5674 1997 282 5067 8370 5495 7991 3209 5597 7519 5794 1105 2038 6650 8042 5405 6232 8798 4485 4880 4087 3799 3866 1950 1592 1795 1246 7969 5273 2995 1309 873 6074 4947 3544 -215 -103 8424 6458 7500 1599 8413 2674 8060 1265 2757 -224 2531 7329 8121 1933 2516 8782 5110 5189 3199 2529 1540 -749 1472 6141 2778 5807 6235 2153 8722 1711 3262 6863 7078 7407 1097 3610 5577 6401 7460 8896 939 864 5570 7629 3731 2748 7709 1319 8427 2979 1443 2791 7669 8594 -417 6423 4156 5237 7127 1724 7183 6794 7978 1012 628 2910 2600 8030 626 -346 5871 925 8544 4038 8113 -944 4934 4575 6789 252 7912 8972 8530 1856 8859 4677 4236 6087 466 479 3108 8766 5054 8994 8296 8367 2615 8438 1825 3256 510 4220 -197 -391 6895 1068 5709 1243 6928 2481 3819 7294 1742 5974 3553 6004 4741 -442 1791 5334 8681 8996 2760 7778 -945 4280 7057 2418 6690 2023 167 5948 4266 6305 6446 3041 7257 5714 6275 5024 3605 4948 2044 4931 7908 5132 -496 3724 2131 935 -826 4891 2551 3688 5072 5032 3926 3085 -375 -495 3046 4858 5457 2337 6042 4545 8064 8800 3830 7859 1932 -94 5385 8146 2341 -525 4803 1693 -174 7369 5108 5451 249 7866 6002 4666 3484 8682 4312 4526 -209 8397 3569 270 4386 6549 3420 6617 -370 -857 993 2448 8099 4412 -147 7842 5135 -719 -748 8300 5394 3666 6911 5014 6964 6762 3102 4942 2491 7771 4715 6300 4476 4952 1311 2465 4033 -459 1647 8015 6185 758 7494 2110 777 -454 4378 8573 1389 4659 4551 7114 4316 -22 4193 805 5717 5696 2782 480 6421 6862 1402 2414 6146 228 3454 8440 6704 8572 -25 5224 2630 2293 8270 2143 1090 5524 6370 7884 7363 8604 5364 8045 5036 7429 25 8753 4702 1175 6642 4138 6731 -368 4437 4769 6492 2147 1570 7357 8804 4989 4861 6574 8946 8199 5163 4593 1967 7222 6499 -427 7699 8378 4177 7462 878 1660 4423 3898 284 4391 6967 6658 6618 3869 3231 8717 3613 7224 8093 -585 2288 6683 -323 7687 7627 2843 842 2332 361 7794 5005 7448 2924 7745 1855 3158 3839 3633 6860 6898 8412 4359 -549 -382 3623 -908 -79 4429 1885 4972 3794 -451 -424 4680 4133 -71 1813 7017 3323 785 989 2835 7011 7905 544 1473 -406 52 -124 3824 4574 6487 8394 4796 5826 7560 5471 4960 3134 5669 161 610 5889 3009 4840 8078 4293 9 3572 885 3316 -664 877 -248 5503 4011 6182 -997 2228 152 7641 8001 8371 4421 6673 -891 8629 7831 7327 -594 4163 5584 5908 8092 6109 3493 3732 3762 1561 5345 7657 8995 1566 159 3197 1254 2483 844 3023 924 4360 1486 4455 3089 5809 4154 -699 3530 3851 1312 8934 1488 -458 7636 5837 7044 7795 6937 6720 5122 6520 2058 4692 1003 8967 3280 7921 1123 1590 -419 -931 2914 7266 -978 1978 6014 2057 641 8411 6500 1565 6599 7512 2826 3428 2248 3697 8246 3625 1153 6411 6990 4108 3951 6661 5346 5659 2695 2155 4175 -842 1930 4242 1190 6304 1148 5919 1631 1187 6490 7258 6097 1158 5845 775 3751 6039 4035 8632 1803 6625 8689 852 1688 2001 6977 2684 747 -532 -311 3202 3636 5316 962 1679 1317 3221 3944 3786 2742 1748 7990 -227 3369 7315 3183 7785 3212 2967 4837 3086 2173 2893 588 1635 8936 203 2678 7640 4106 3191 -5 2547 2437 4408 1781 2710 1110 464 6094 7377 1441 2707 -722 1772 3307 4981 5282 4712 3584 8841 7107 5879 7452 8521 3368 3257 1869 4091 162 7768 6999 1879 5481 1893 6207 8634 7626 7161 6751 2655 6748 -426 4079 1185 5490 4624 -685 -852 1681 3497 1658 2213 -902 5268 5338 7718 495 4845 88 3292 496 2511 5239 261 8668 673 3902 7915 8750 817 1087 4842 -210 1151 6254 5921 2104 5215 3414 7970 3583 -690 6651 6700 1755 8048 -141 6764 3210 3175 6385 6161 4530 1287 6832 7139 8655 1548 8350 1101 2415 1877 3709 3439 3754 7829 5517 6518 1539 1451 2428 4055 569 -229 7219 5203 -493 -830 5744 8906 7326 4923 5736 3395 1351 6069 6013 -36 1165 8003 4607 -958 2633 365 1581 -600 3517 6351 8644 6294 5259 4463 -529 5196 6563 -972 3650 7873 8711 3460 7980 2980 3489 2317 6187 1598 2502 1895 3335 7425 4871 7792 4112 3139 1320 5802 -717 4729 8373 8828 -867 6454 -380 7611 6541 -996 1513 4071 2545 -266 6833 -570 1976 8448 6858 2683 5555 647 -185 779 6148 5515 7586 7865 6471 5429 8823 887 4864 7660 7947 6840 3882 2306 5472 -762 3133 5173 3042 1690 5119 8287 1674 1921 2480 7639 6431 3198 4557 2383 -975 3294 3381 6329 6380 3870 5084 425 594 6262 2692 5957 5876 2314 472 1125 8080 1678 7617 5990 2431 707 7376 3157 6394 2165 762 5500 -328 7178 742 1508 -854 8924 638 2123 2349 5782 405 45 5784 1765 3073 1108 3655 -39 4771 6678 1574 4623 5992 5 618 7502 8991 6367 2079 -876 5371 7624 519 520 2587 1011 2948 3950 3995 3180 3574 5703 6845 -153 3699 7635 5298 6242 6759 4218 6103 6807 1359 5311 -251 1324 8468 1943 3061 3612 -506 2917 5433 8802 3418 8106 2842 5010 2214 2563 4130 3511 442 2077 6145 615 -41 2953 3098 7667 639 163 7362 6622 5461 -230 4415 6877 -668 5281 -268 8626 8764 8221 4113 6114 90 2557 5571 7347 6211 6223 5439 2289 3938 7007 2822 1906 4792 332 7049 6805 7243 5533 898 2257 2973 3658 8947 4093 7520 8255 4303 7349 1763 2840 8570 116 -725 5799 1833 -450 4644 7038 4828 -881 5972 2677 2291 8539 1331 23 6890 6782 6734 3204 2247 6605 276 2220 1067 2507 7848 -578 7929 4461 5260 8006 1367 508 6506 5051 -659 3578 3907 4764 1903 -155 2658 7170 3615 6771 2656 4552 4945 2436 189 4245 8360 5020 7297 2434 5851 2671 4067 7550 7218 -848 7823 5939 -128 6537 3488 2012 310 2271 1864 2673 6596 2870 6108 8401 5980 2387 1862 5981 -934 3005 7371 -802 1751 7003 2249 4841 3918 -127 839 5497 8624 2211 8504 6128 2194 3690 -736 1036 5708 8517 2338 2252 93 4939 -706 -282 1278 4745 7708 3382 2734 2446 6995 1604 4917 -389 4645 5467 3920 5093 1398 2430 5102 8989 7752 3614 5205 6552 7910 7747 8609 7433 6159 -701 6655 -939 1024 6191 3370 1292 6961 8391 4587 1137 1425 6586 4770 -37 1913 5774 927 4958 8893 580 5194 1396 -75 7374 2098 2137 5278 6542 1821 -646 2046 2316 6441 1714 2559 1364 7321 2014 3855 1710 6472 -860 4321 8637 2279 7018 6258 -523 2496 5623 3627 -510 7713 6272 7230 6773 1439 5874 129 8693 3713 4568 5320 5772 1336 6166 6493 3783 1005 559 3656 4660 6127 315 2856 7946 8813 6871 2570 3859 7737 3781 6684 8310 6084 7735 -873 3575 3580 7397 4943 5886 4299 8952 327 7346 7962 4137 5498 6017 -331 6920 7670 -245 1089 -216 6859 2680 906 7312 5788 6205 2614 -130 6664 760 3178 903 4014 4750 4747 8662 1230 -488 2847 8664 2066 3353 5343 3581 5349 3275 6798 2440 5937 4410 8410 3561 8584 6113 -453 963 3987 37 4844 -411 7853 2784 490 8846 4863 8023 2536 5228 4333 7891 3895 6402 7151 8186 7280 1776 5546 8881 8459 7983 -473 1798 48 642 8495 5058 841 1568 2405 4235 8125 3192 2814 8591 7175 8581 2376 3759 3807 7413 186 -611 8599 6806 3106 4706 4315 4334 5027 8463 8516 7427 4383 5610 6339 125 1228 7422 2439 4349 1732 950 1835 1299 7658 3967 4643 8393 8177 2281 1722 2663 1597 972 -144 -63 6438 6883 6398 3741 3337 3833 6368 8265 6151 4954 3450 7979 2017 3622 6925 1056 5699 7599 7309 -182 532 2543 7420 6095 3642 3376 -579 7006 -918 6652 660 -202 6889 182 3974 7977 6255 8034 1783 6715 3162 5557 8054 1680 7513 5294 4061 6335 1173 8447 1800 2993 6119 6021 -120 1431 4578 7314 5232 1436 1709 2169 7855 6316 7124 5329 1051 5627 2908 3194 8137 2554 2354 1078 3290 2736 1662 5214 -47 5628 3336 -117 3903 5844 3763 6846 4007 1790 7449 6496 -992 7913 7997 4468 8968 -136 5574 2999 179 -43 4971 4255 8961 999 2610 1492 8933 4309 -290 -432 1470 2379 7698 4508 3958 7546 -924 3008 -403 6755 2690 5300 1169 2687 6739 5847 7493 1853 2937 7758 1554 -152 5236 -80 6949 4425 -173 3616 2034 288 8787 5935 5762 2762 5516 6756 6019 -222 7370 1435 6149 8086 -716 3916 5013 8816 1052 8489 3921 1164 3896 -993 3883 1646 6341 5506 1088 6429 3621 389 46 -831 4388 8402 2461 3298 8085 1638 5351 6692 2820 2159 202 6619 7061 2343 -294 4668 1830 676 1071 2661 4672 2745 78 881 7125 2685 4849 5088 8382 669 7486 6310 7814 7408 2425 6824 7454 6512 3676 -764 4400 6850 4473 4902 7882 142 137 8220 454 8037 4886 6168 8709 3774 2472 -163 4846 4343 1954 1377 8779 6443 1839 8191 1630 8218 -164 863 7440 4305 -553 -947 4275 5612 5635 6142 390 -840 269 2032 -925 8256 7522 -61 7605 1341 2819 8479 7019 7885 1726 72 2081 3358 7352 988 450 7800 4918 4859 8699 3474 6523 7215 830 8691 7273 8688 7943 5169 869 2968 6986 5418 4051 4646 8635 867 1571 3510 4005 8690 8536 6606 -853 5797 3756 6045 8526 4762 6333 -149 -429 6528 6032 6934 632 307 4288 -289 7418 176 -986 -478 1822 1477 5906 8363 3977 4331 3748 368 3591 5002 2307 -317 2482 2266 7846 6162 4186 7783 2049 1328 141 3976 5888 2084 274 6296 7439 1283 1522 5277 5100 4819 4345 4696 -957 8198 832 5650 766 1191 2471 2478 957 5147 583 767 6568 8960 6992 3568 7029 3738 81 -548 7476 1022 1636 -437 6369 1870 2889 8744 2052 7392 1552 5082 3545 6893 1 3213 2378 -244 5589 4738 2074 22 4982 4854 3310 8596 7533 -970 8327 8650 5881 -49 1613 347 6643 4077 8990 8366 3776 2951 4074 4614 461 7283 1902 5474 5062 1261 804 1774 8569 6378 7646 7055 1811 542 3665 1716 5585 4277 6360 7305 7780 932 1883 7479 8472 6225 533 5301 4905 470 2106 7002 3795 5276 -316 5550 -679 4941 2429 -820 8736 6592 6753 8163 5704 5492 5777 7711 5483 3960 6396 5315 8675 578 1332 7836 5101 4920 7899 2706 3012 5803 4263 5958 8230 8104 7897 5905 6909 -160 5638 8824 2752 6978 1529 -789 4155 3668 8844 2113 5510 700 1353 7786 -723 89 8231 3407 2682 4700 8236 5245 8399 5057 5168 8854 2938 894 3464 1958 6442 3785 8334 -813 5869 2394 1197 -546 166 6172 2775 -887 3845 7566 5325 5449 -84 6869 2569 4214 -353 2407 2862 6088 7666 3389 5625 2913 8091 4694 5787 -874 7888 1253 4448 7499 3218 8421 2767 1214 4807 5828 537 3230 2743 5177 4895 7742 5833 6139 96 6654 3849 -519 -696 -16 7621 8902 5022 6240 4749 4385 -766 5991 8892 4637 7445 4148 5902 7103 2750 275 56 3329 -741 7247 6419 7417 4462 814 920 8117 -288 8623 7204 6797 6209 8203 8695 6452 -985 2218 3163 338 204 8499 7547 1583 3873 5746 1796 1338 70 6688 2621 6086 2832 7534 1878 7248 2599 394 438 5126 4313 6460 5953 4763 4465 7694 976 -66 5486 5951 1393 6288 7025 4025 3340 -920 2886 6527 1601 2562 -658 7568 4875 3233 -107 8772 6354 2372 2809 -90 843 -392 3270 -181 -258 6353 5066 4070 7298 3291 -987 4355 4969 5477 382 -687 322 8483 8478 -70 375 1374 7692 8852 2989 645 5442 4679 5829 1939 -448 7372 6539 7893 7338 8475 3137 3347 895 1960 -673 1268 4362 6372 4930 4118 7584 3220 1381 5043 5567 3092 4824 3406 3804 1850 1931 7975 6685 1221 4980 2534 5507 -77 8470 7344 655 8522 6550 138 3398 3366 5817 5877 4420 7730 4211 8665 2499 4326 -217 8271 8170 1239 8930 7960 6037 6864 3547 571 8151 8617 7723 200 2204 8247 -214 3142 4832 690 1874 1437 6031 689 4830 5735 6594 4804 6217 2261 5390 8611 7068 -129 8639 7824 4129 -582 919 952 67 6477 2920 2891 3985 2888 2199 3675 1302 7650 2628 5450 5092 4928 -59 1138 8029 3132 1642 3930 4172 8435 3560 6229 3226 3590 1481 8763 4795 -89 7577 4839 6749 944 5808 291 -661 7226 2198 8403 1382 2267 7210 654 3440 4086 -662 4506 7135 6514 1707 240 8561 21 3875 -899 39 4059 933 709 2513 2473 4254 6853 916 6251 3096 5672 518 3637 171 7826 4850 2197 1750 6066 437 5520 -433 5040 5468 -168 7270 -27 4479 414 889 277 5947 8428 3863 8541 3521 54 4146 4936 5763 -794 7042 5885 299 -962 8262 5195 7307 -614 7202 4428 3148 7356 2404 -989 4043 4354 1370 4507 4730 3829 1979 -555 702 191 3415 4166 6302 6728 7700 2585 8460 5246 3394 -823 4231 97 7620 5915 2549 4384 4893 6473 3311 2795 4117 -58 783 8853 7455 1454 8376 8781 6467 6778 7244 7236 5547 2883 1818 8872 6504 1578 5818 2896 4786 7188 -923 2897 8036 4907 -109 1926 3268 2129 1775 7958 2844 7551 6698 -640 4788 2353 6153 5018 1286 3429 3404 7987 4350 3647 5314 8274 7256 7075 967 951 1549 1846 6399 3644 3514 8129 815 4708 -998 4089 4317 -838 6198 1725 5248 787 7 5337 -729 -627 178 3031 8443 -728 1499 8335 6767 5083 6034 6035 -313 768 7267 289 7121 6705 3446 4192 381 -738 1449 2650 2380 8372 5243 -503 -660 7540 6231 7652 4273 4240 444 7203 1010 6896 5654 -308 4308 4102 5006 -769 8797 3127 -297 2366 4618 -255 7166 5986 1938 1204 -517 1406 8017 2120 6038 6096 6547 8716 3654 4053 7738 7659 8901 -65 8840 -131 4516 8286 3260 6461 3054 8589 6410 7628 6671 724 7466 376 2242 2444 1080 5929 3383 8362 106 2983 8971 4435 8509 7523 6813 2966 7638 6968 -138 -78 6598 -528 6213 5963 6519 8050 5701 3716 7932 507 1909 5197 2568 8414 1143 7744 6588 1368 1157 7596 -465 2573 1611 4558 5857 1543 6921 -547 4678 1390 -554 1809 8377 526 4853 5251 7380 7719 7582 4099 1914 7787 7585 8909 5675 -878 8982 4991 6282 2363 7808 6344 6836 7839 2803 2688 4801 1559 4109 82 2763 8923 3128 5378 2036 5693 7492 8140 726 8395 8304 4724 7766 -551 8331 6077 2626 7242 1019 1475 1409 6073 8139 8642 3375 3453 6962 1923 6338 3939 94 2033 1183 8721 443 3039 7681 6774 4821 2259 -672 6597 6078 377 7478 7651 7876 3075 3445 4812 -889 7231 2865 6194 6190 3978 2591 146 -619 3643 460 8660 -558 193 6459 8234 6241 6202 3652 8742 369 7567 602 1520 2234 5786 1388 2399 1956 214 648 5969 4900 3131 357 7889 8118 -774 -505 -122 1038 595 4104 7796 6498 1527 8185 8126 441 5159 5271 5971 1413 4783 2125 1644 8261 7552 232 -698 2501 1391 7729 6102 2876 3124 7733 330 -464 3136 3522 86 5561 1695 4030 597 -246 8225 256 6387 -161 60 7812 696 7398 8056 2246 6377 3803 1281 7815 -34 4342 6439 2737 6919 8488 2260 3722 2370 1291 795 4056 5910 2666 3684 -587 2323 1130 5678 3448 6323 5810 8595 897 4494 6533 7501 7575 7801 8196 7950 119 8827 5924 8598 2998 1804 608 2207 4411 6873 3225 3165 3966 5766 5326 -466 7172 7158 2919 715 3933 3818 8071 3792 6634 3434 4477 6116 -325 306 8141 7173 3534 8227 3090 75 3846 175 3648 4018 6716 1424 7608 -369 7862 806 7597 5989 4267 120 5556 2972 7937 5419 5484 4367 1163 7529 1062 737 3236 6476 8325 8082 4642 432 4115 1034 -492 7743 5113 -544 8658 6737 8497 5759 408 8314 6405 1521 -28 4072 7021 6164 -241 2443 1777 -900 2716 7290 3200 4569 4996 2911 7360 3793 8273 5226 4555 6556 2401 6269 2808 3555 294 7916 8184 835 8577 3109 3558 -98 8173 -845 4145 6548 2264 1837 3620 5342 -337 954 8585 8729 6058 4394 5619 2061 8292 2031 8476 5222 7336 4001 6056 5646 1875 650 6750 3606 6003 7436 5697 6902 158 7867 69 483 2275 5156 7509 5115 6334 934 1920 2788 7557 -344 264 6818 -807 2090 5172 6907 3045 -711 5411 1955 7193 4499 8556 3166 2484 4581 7335 531 1712 8887 656 3525 353 8107 8656 4 8192 8512 8566 5514 145 1910 723 1627 8515 1739 4711 7875 2890 -154 7483 2811 4612 5745 -866 5835 -315 2533 -415 8275 2817 5987 -898 4165 2606 6945 5995 8983 2689 6049 3946 1237 8532 1524 7754 6451 5377 5275 2184 6663 6480 4933 8698 6503 5938 6121 2390 -888 4078 7816 8217 -135 5030 2544 6515 4664 8807 7220 5747 -581 -832 776 3911 1829 5003 6657 -504 -689 6228 3651 7176 2660 8559 6924 581 1405 -982 8426 1039 1683 2800 4063 7285 697 -158 5422 1694 -705 1423 1784 6640 1172 7117 3276 2488 -341 3535 4671 4042 1684 3103 4481 7104 854 4171 6526 5663 4324 4878 8628 -146 7301 8932 3099 5758 1442 8346 4691 7373 1852 6064 6780 8671 7544 -486 8692 3033 -228 769 5117 4604 5201 8152 4635 -457 1198 4041 5269 1107 1250 8000 -792 7530 2158 6376 5702 4330 584 6900 4285 6616 4227 2238 1820 4800 3640 1104 4188 4034 3072 4498 8025 1643 2230 235 7059 1127 3817 6163 5558 1040 8762 3677 -583 1235 6786 -799 2994 423 3771 -273 3577 1871 300 497 7828 3827 7691 4081 8871 3529 7526 8507 855 3341 2451 -338 5370 -480 2875 4088 2088 4496 6817 4387 7276 1858 4348 8156 5331 1575 -535 4955 3629 -784 8344 -827 8819 4615 -829 3002 3937 4908 2056 3289 3224 -461 4397 285 5166 5540 8538 7833 1462 3302 -735 1180 1836 5912 7721 3016 2727 7784 1952 4483 -602 7858 -907 8920 8876 1929 8776 3543 -700 6449 1384 362 8533 8818 6603 4932 8143 2530 8026 8519 -756 6234 2816 1779 4963 4135 3066 4134 8147 1007 -277 -312 -475 3229 4239 -48 2364 6040 5967 393 8253 -806 5907 1414 3905 8613 -836 -580 8319 643 4222 6660 3088 3965 -624 1102 7250 541 585 6803 7180 550 5356 4489 6222 7108 8774 636 4131 3567 7402 2091 5210 -893 7807 3671 2604 8108 2982 8914 6201 2178 4813 6711 8453 693 379 4553 8702 3519 4784 6465 860 8114 8888 5077 -367 8444 6123 3772 2879 5916 4582 -261 7077 8415 5178 705 5593 5213 2950 4525 8860 8843 4395 2093 8175 5575 5285 4381 7205 8009 8491 1318 5917 447 1161 4631 629 -483 2729 3914 1494 3674 1628 1957 2067 2880 5095 5946 8245 861 5700 1859 -194 2644 5089 -318 7598 1021 5773 600 -971 5934 4286 2457 236 8341 -564 5400 3631 -444 3934 7264 7208 2352 5019 -644 7333 -44 6137 -694 6729 2388 524 3798 6887 3087 683 5640 2711 6841 3355 3820 5882 5318 4629 3324 6247 740 36 354 929 8985 8469 3548 8299 3880 2269 1557 6855 3432 8387 5424 2251 3586 3050 7229 5181 5855 6856 4258 980 5047 2369 8645 7361 4998 7906 3403 2087 3342 3000 3740 8732 1889 4765 1343 7976 3947 5872 1095 7023 2698 3755 6264 7632 -512 2504 2313 2589 4888 4606 3626 2588 3598 7359 8696 4341 4957 -358 -954 6012 7113 283 6987 644 4181 698 -264 -487 6565 4627 -361 1773 6226 8437 4121 4207 6383 853 3297 8605 1860 1365 2537 3698 2984 2128 1900 4825 1432 8269 640 4065 3711 6579 8 4879 3893 599 1968 5505 6147 4978 7012 7633 718 6130 5464 -425 2712 3471 5004 7936 430 1831 1940 4973 6246 3750 5863 8132 7825 -491 -356 8551 6317 3945 1593 1171 563 1639 7514 -565 8962 7393 691 2192 5389 71 8254 1030 -566 2239 883 -597 662 -449 5761 2119 -73 5594 -507 -300 8251 1480 557 5595 6632 4228 3105 586 4241 -773 701 3563 6497 6285 3021 -715 3388 -837 3726 3986 2815 5392 5622 1625 1713 -405 8040 482 1987 1974 2497 3171 4979 -188 8597 827 7555 7165 3486 1244 -780 7938 1706 2302 5581 8809 8473 4630 5055 2296 7197 231 4894 8496 6306 6180 5792 4450 5143 6453 7052 3466 4818 7111 917 7883 6212 4083 7775 4021 4052 756 7774 5304 4438 333 8320 -653 2773 4444 -754 1780 4823 1111 4157 4695 3490 7150 7954 3119 1297 8457 4628 8278 7707 7756 6507 5042 4404 1652 1664 4092 1280 1884 2749 5655 7129 3973 8785 4329 3826 2768 6327 2112 2413 6098 187 474 2580 2385 8528 4993 909 8418 1195 4737 4857 -540 -783 7442 8748 7147 2991 8770 7764 1445 7341 6381 757 4995 5791 4200 4505 -447 8232 2741 4416 5078 4698 836 667 290 2149 2254 2212 8432 2646 5432 8190 7662 -841 2895 6801 499 188 132 7490 3263 7144 716 -988 4641 938 3299 8870 5527 -233 4374 8420 4983 1285 7724 1170 -961 7366 3057 1203 2892 8010 6152 5975 8467 7302 -220 4670 1229 3796 1990 4253 2152 1832 4994 183 3838 1788 2075 8079 8524 5925 3810 5045 7464 6901 8791 5909 -413 5420 8993 4264 959 2603 3854 -1 1257 3020 8462 5710 1349 2558 6195 6783 6389 6577 3306 5901 680 3065 5118 7571 1687 2969 1665 5415 -995 5626 727 6614 -494 1136 3924 825 7415 3887 977 3991 6827 2395 8235 8355 1145 6646 1672 5836 2872 4364 6825 4440 6346 6403 -132 6694 5383 6513 3303 2486 6183 808 7330 8980 8285 -636 5785 4925 6993 -2 2538 4684 6781 7930 1276 1865 567 -801 4535 4562 555 2003 -616 4554 6693 2096 6303 1179 2923 2326 105 5775 219 -674 5366 678 -1000 3129 1897 5368 6357 5751 3427 2142 1008 987 3638 6529 8703 2583 3047 2853 7898 7686 5544 3025 6800 5609 2179 5026 -577 8575 4597 -193 7554 475 4822 900 5469 7461 4651 -69 1901 5139 3877 1177 3865 -606 7765 8773 8244 3030 144 6022 8895 5776 5603 2639 -172 6299 7306 2216 1440 -17 6445 4625 8513 7570 5509 1084 2772 6795 2931 8735 802 2818 7631 4772 728 1949 339 5035 5453 1207 1983 5590 4810 3823 5376 8375 1041 0 6501 8110 8622 1274 2954 2934 -306 6823 8033 -462 6881 6989 1577 4794 8527 4984 8760 3999 7272 -498 -588 6456 3982 6313 3018 3115 7588 5247 627 2441 525 6384 3144 6043 2460 3685 5726 11 7755 7271 7955 1840 3101 8738 3325 -942 3811 8046 813 3281 5647 7527 8640 2241 272 3909 4600 -45 1386 370 7391 7863 2114 2576 3800 3308 -393 6569 -281 -225 2265 7762 -343 1142 8820 6117 3019 1844 4734 8619 1277 7506 7259 2864 3207 -428 3860 -812 2402 331 8357 1252 5017 -211 2148 4492 3778 6775 2377 8153 1510 2871 4748 8407 3430 5949 -499 7064 7334 -844 7488 6668 1124 2236 5677 7793 8328 6177 8733 4909 7879 6016 6253 1478 6648 3912 606 7982 250 6884 4339 1404 5064 1114 -410 7728 2268 5538 8389 34 6336 1159 4458 968 652 2697 -110 5899 704 -467 8168 798 6804 2089 3228 2438 2851 3244 -865 5144 8815 3167 778 819 692 5875 8728 1227 7255 -68 3172 3766 2801 2515 -396 7304 1467 1305 2579 5414 3055 820 4605 1363 4449 -592 5602 5436 949 2305 6938 1189 2721 3941 2629 3604 -407 7101 3027 1053 5229 5327 8912 4793 784 2868 -691 267 7610 -704 3487 415 4419 7480 3094 2512 7870 3842 7237 7126 1300 7869 2927 8012 7379 5727 2382 4689 8257 121 247 2833 2510 2201 3821 5421 6880 233 3983 4023 3729 -858 2117 -593 6730 8997 -901 2170 3237 355 5037 3201 471 -534 5227 6677 5211 5860 6639 6464 4153 -552 -649 -632 260 3956 5985 6135 1969 4270 1801 6143 3267 8345 5434 1953 1876 -309 80 3734 6105 2769 8666 7435 7355 8830 8894 539 3083 -364 4686 5125 -743 3777 1335 4704 5998 8945 7225 1098 1873 7400 2447 6208 -959 7350 4640 5824 1826 8817 8211 6063 1989 7282 2619 4370 8252 1184 7395 2781 2466 8857 6554 -726 -296 8548 7817 1762 -409 6531 6669 8094 5333 8704 7082 6546 4580 6486 5207 3889 -347 8422 5462 4124 7390 5493 4422 5582 5249 6374 -150 7194 128 7279 6722 8384 4626 5798 4238 131 3126 4913 427 1810 5676 7092 7241 5563 1936 -83 3222 7949 1487 3003 -469 5523 5926 -92 8602 2921 2912 3554 1046 3313 -278 6047 2756 3672 7959 8531 536 7860 1828 4608 8679 -207 5096 4571 8747 3979 3971 5789 6023 7261 7058 8311 8981 7046 609 1326 5142 7463 7956 6717 4744 1961 1965 -977 -686 4054 8707 -7 2303 4746 8534 2144 4968 5856 8174 5165 199 8338 6733 -737 3498 4811 7974 2715 8213 -421 -470 7263 2831 6838 6839 2243 476 2738 6680 4753 8449 2593 -631 2219 2253 5127 2321 1211 5393 4234 1139 663 4988 8986 7791 1086 1023 1412 8557 5658 -688 7799 7473 -814 7337 2422 2018 4946 1608 7856 5866 -895 6725 6281 7296 7367 -710 3576 2708 4009 2019 504 -760 8216 5739 5768 6936 6604 418 -567 1193 -941 3717 1659 8392 -572 6679 810 3515 8027 6070 4008 8855 4213 5749 7874 4589 6214 -680 2719 6237 1057 3689 3255 -205 -610 4654 1262 8059 1146 7036 8136 3753 5070 5146 -950 6656 -720 3888 1498 7030 868 2021 1496 1144 8583 5499 7559 1894 5408 2403 3419 3040 346 1553 8183 -320 6505 6942 6257 8490 3154 1719 4718 2904 5834 6687 4705 3768 4966 4829 2477 6413 -159 549 5250 6561 6743 1060 4244 4451 4596 5984 7292 8771 6843 5651 6101 -677 8651 7240 826 8865 229 -782 3399 7015 5620 5284 3992 5897 4393 20 8005 5185 5712 634 4785 4475 8501 5865 4199 2286 7446 5898 -999 -303 1131 8734 2882 5341 1899 -702 7581 807 4992 1043 3469 8616 5822 3691 4537 5107 8687 6799 319 8419 3948 3478 2163 -376 3114 5193 1447 3837 5796 6027 3219 6259 2852 8115 7091 8349 4446 2657 2779 886 6981 7731 8943 4834 7521 195 2565 915 6610 7186 4243 739 29 522 7806 3287 396 2272 5354 4940 2498 2780 2452 7200 6170 1650 -647 -928 2029 6076 3479 759 6905 3507 5896 2807 847 6511 3528 7037 7911 5537 6138 400 2426 1403 1348 4283 1395 8546 2076 1868 743 4000 7999 7284 712 5560 7606 5671 4911 8272 -869 6706 8641 493 374 4262 6311 4836 801 5923 4852 1994 664 4126 8324 4838 5079 2172 4775 5572 -51 -252 3496 8347 6083 1301 4204 845 5665 2475 1728 -981 7748 -397 8503 738 7146 68 4073 5308 635 6345 4015 3001 112 2233 -973 7926 8481 725 4237 7187 321 8789 4719 2464 -805 6745 6115 8477 1411 -543 910 1408 5521 -767 416 5425 8718 2520 8898 1708 -929 4306 8518 185 4290 8452 2735 7595 7840 7274 -595 343 5009 2540 3739 4732 2829 4323 8783 7830 7746 92 6608 -203 5554 1721 6914 1753 540 1623 7663 7760 4699 3412 5332 789 7510 234 8720 5900 4648 1740 6179 921 913 6427 5973 7005 286 6707 4057 527 5129 -550 2355 241 874 4187 3603 2270 3338 8167 3813 5804 4162 8162 1049 8323 -622 4776 4847 3265 2958 5074 1747 4470 3537 4790 1511 1720 4720 5960 7761 5038 8159 47 3113 7965 -781 3696 7252 7672 5539 6543 5358 6578 754 6524 6674 2638 -856 675 5044 6478 -522 8761 6956 -6 3706 2284 8096 3296 1661 3660 1122 83 6007 4013 1523 320 -779 1224 6768 -938 4799 2255 4856 7152 4860 -724 1154 8614 -423 7516 7185 2398 893 4298 1417 4517 8409 1463 206 1746 3596 907 3185 8233 4761 5280 3442 7703 220 1380 7216 5795 4774 6120 -833 2616 5257 -310 7917 -200 4610 4577 4565 8150 3630 3044 4185 3499 373 5328 3758 8243 7528 4441 8508 4539 752 8659 6048 5258 824 8154 5412 8955 791 4190 8615 7169 2040 1793 7066 7140 1907 7809 5576 -42 5164 1491 -775 3760 7767 1031 4447 3386 6417 1251 5821 3326 711 3391 3990 1029 1323 6319 -105 311 3077 4503 8194 -518 7877 8677 7174 4328 8657 4501 1514 5605 6075 -708 8636 1915 2107 4560 4721 891 7852 565 866 1576 688 7918 5713 494 5008 6245 -137 8567 2625 1073 153 7060 226 8964 3425 -828 -237 2631 8250 7182 1330 2830 5116 434 -639 6366 2108 4486 7102 4735 6628 8222 6029 4212 3836 530 5255 5754 5270 1234 6965 4140 6350 7495 7623 7484 7275 3929 -913 4490 3682 -395 -663 2607 3899 685 5443 98 7612 6218 2971 1579 7972 -542 6167 511 8348 7034 4588 4454 5437 4798 451 912 3814 8851 5771 8004 5941 4368 3608 5695 8095 2222 4780 3117 2686 8942 -243 605 5686 8237 2045 590 2548 3492 577 6555 5552 4647 8926 8627 344 2854 3602 5911 3035 -502 7450 3473 6365 6724 6713 2463 1806 3871 8145 1218 2550 3856 6485 -106 8653 6553 5630 6891 3116 8883 2956 8425 2602 6104 6516 1737 3155 -951 413 7722 8057 7741 7026 940 4949 6008 253 2699 3784 6393 3170 6314 3367 5591 1536 2503 5145 8361 582 6944 6308 6581 278 5152 8436 2015 4556 350 296 4726 174 4022 -279 5046 859 7834 1186 6054 8715 212 2292 8119 794 3801 1085 2333 7696 -3 43 4779 4257 -67 -811 5395 7548 6270 3426 4069 7664 1754 469 135 2705 7130 74 1654 8710 3038 6397 3152 5781 4559 5705 1079 4432 3037 8558 7179 8701 5667 263 4673 1140 1928 449 1361 5613 4032 3968 960 -232 5007 4380 7351 5733 8340 3765 5918 8727 714 3890 2375 8138 5631 2024 5048 5103 6600 3954 3892 5297 3641 8890 -574 2492 5723 6382 2975 1567 6178 -443 -263 7594 4296 4781 1247 3867 2659 196 3250 1845 8498 1620 6629 -10 2374 26 1220 2348 -140 7854 8966 5778 7421 8179 6107 2245 3728 345 5996 1399 7675 4202 -260 5645 5375 14 7431 3093 -953 4649 1217 -360 -526 -948 3607 3319 2467 3719 1167 3736 -791 7574 3886 6627 4161 7591 5130 4413 5805 2007 554 8385 2941 2397 4514 621 6025 1633 8223 1027 1537 5148 7246 4159 3408 4713 8714 8848 -693 8065 -665 7868 6057 619 364 2949 8725 -166 7281 761 -354 1851 5360 -795 5460 8031 5578 2009 104 7110 16 -868 6777 4085 4366 1428 5964 4191 8845 7233 7438 8939 2493 3182 5724 5208 937 8550 6331 4693 4962 -350 2127 5959 5849 3994 4619 3091 1551 1911 8109 -274 102 3611 -761 848 7339 8794 1128 1645 7953 2187 8193 5729 7558 3147 2022 4675 3683 1259 1457 7013 2567 4848 8836 8646 8975 2346 7647 3011 -758 -226 8680 4890 3174 1951 4889 3309 1785 1459 7618 7143 395 6721 406 5299 5028 8165 2759 5306 1069 4515 5447 8070 7004 5518 6404 7902 2200 3881 5853 -573 1778 5854 8297 947 3646 1904 3387 5673 4731 1516 5562 6816 2645 5936 770 3508 7162 2552 2004 2358 114 149 7424 446 7677 502 3312 6595 7014 -96 1980 440 326 732 -125 4885 -399 5293 8368 943 340 1605 3069 3411 301 5086 2202 2774 3060 5398 5800 1048 4459 1816 7196 1018 748 5016 -373 2335 7609 2157 4189 5098 2758 6284 3775 4915 3879 397 3405 57 6055 6557 5309 8039 4096 6791 4758 5361 3782 6870 41 -167 2609 360 6998 7119 882 3138 8053 5616 1426 2489 1091 4549 5200 5365 6448 -937 1156 3300 5887 4622 -95 3052 753 5858 514 -709 6953 6583 1805 2556 7684 5480 -545 8014 3363 2189 4602 227 2525 -671 1002 359 4116 -527 2456 2841 3330 8364 1727 3343 7967 4282 2777 2381 7115 840 1293 5961 1935 -501 4478 720 7453 -481 8169 8861 2470 2597 1995 1999 4297 5174 -515 6670 5566 7864 1612 2612 6641 7065 -850 7262 7890 3104 3259 574 3993 5104 8379 2011 8833 509 5388 1584 8560 3125 5861 4225 2176 1912 1917 -797 2065 5267 5862 2940 7031 7444 8630 2301 1563 5279 101 1675 4974 523 -849 4563 1982 5965 6973 1126 5864 6582 7122 7693 1519 6948 7934 8948 4876 7988 5151 3940 -50 4533 -221 2190 -633 4564 6154 -615 -46 5307 5244 5823 672 3695 1556 1303 8303 1621 3327 3844 4883 -12 1944 2730 7939 589 6742 6888 4870 1666 3764 -750 -871 8055 6508 -302 2526 5231 8959 -839 622 528 5476 3068 3274 4304 7759 273 6842 -55 -394 2367 856 -305 4168 8927 7318 892 8799 4105 6821 -810 1715 4997 4921 7286 6293 7148 562 8535 8606 4119 8264 5416 8172 -452 6418 5551 -385 2025 994 3841 1461 1340 -304 8563 8188 8726 329 3908 6199 1269 7880 2344 318 -198 997 2703 7803 8103 1964 5740 -192 1500 2906 -651 1249 5983 2581 875 6276 32 4566 4439 6243 8940 8307 671 4206 6126 6609 6474 4532 7907 1466 708 -912 5843 -412 198 2654 431 8201 4217 1759 6966 7086 8351 8878 1484 6067 5041 2340 7673 7984 2468 6005 5121 1120 3082 1887 5167 5583 -321 876 6186 1152 3223 -390 8083 139 6852 8856 3518 485 5840 4127 8326 803 6386 -212 5720 -645 2961 7973 7689 964 6675 6348 -990 6290 5636 150 6089 5384 -586 8007 2227 4877 1358 6808 -299 6875 5648 8571 1236 2582 38 750 3483 2857 2156 4733 5124 7797 3952 2373 3056 6124 7131 7254 -386 6946 5056 1546 8430 3485 617 6963 5970 1573 6666 -800 7201 1033 8673 8018 953 7223 4524 481 5455 2608 3868 4502 5596 3858 2598 1337 1482 3357 587 5485 1118 2881 2668 1379 1401 5209 50 2410 2133 7456 1202 3029 61 7535 8506 633 2825 7556 24 7532 3121 335 2310 6573 8417 3351 7702 55 7648 1422 7033 7847 7235 1216 5893 8510 7642 5154 4346 6457 6979 3344 2059 -208 1934 4024 -536 -607 1770 5403 7416 4040 2485 3961 7653 4405 -175 5770 -4 5149 1174 455 8157 8803 8700 215 4337 3141 4522 2704 6831 7039 8831 -940 -19 -143 -634 5598 225 6567 3301 2618 -667 7614 4107 3177 4872 -332 1531 4269 1550 -915 1580 1066 4356 2350 5689 751 4311 4399 2648 1458 8697 2859 -333 5458 7543 566 7423 7053 2389 3831 -917 8654 7712 8837 6363 659 871 5599 -983 7322 4006 998 -808 458 3943 2109 7802 3773 7051 2195 2082 7469 8329 3779 6793 8812 1497 7948 2669 8200 4901 2561 2846 3269 2311 2016 5456 3919 6930 6090 2225 3678 7604 1272 941 4143 2339 7690 6395 -569 -675 5819 1972 5060 3097 7536 593 4835 4570 -112 3942 2299 3410 2596 5489 657 2770 7590 6020 7592 8905 2164 2723 2672 4688 7851 6940 1258 4068 3385 6321 4662 7414 5396 5340 2048 -388 6954 8999 4520 492 1222 2183 2981 6943 2945 4519 1035 2097 3084 484 8610 5221 4843 6988 -162 3562 3904 4248 3557 7317 6861 1670 4336 7009 2320 7123 1106 2226 169 5691 7154 3659 6844 3253 3284 2359 6534 2005 2208 3585 6356 5977 7295 7232 1606 4609 8016 3242 1971 8431 1133 7749 -744 363 3565 6206 7716 966 936 4681 7924 5852 7470 4310 1572 2898 6969 1891 4710 165 6636 420 7715 -482 7736 4319 6079 4797 8618 7844 -91 5402 7919 6796 -620 8077 8674 2976 6455 7810 6929 4953 -398 -121 4176 281 5668 592 -100 -87 -108 4371 6059 8406 2766 2810 -156 7887 4379 5097 155 8756 2215 7850 6192 1162 553 6562 6 2356 8879 7062 3452 6309 6158 7268 3164 2649 570 3805 1310 3360 2702 7083 3063 8686 4216 2116 6444 572 2542 8051 8866 5290 -776 5454 8908 -531 5141 380 5233 5357 8097 8074 5883 5728 -190 4111 2393 398 -463 -74 8667 7076 6819 1819 95 8260 5296 7105 6849 7541 4098 8574 7171 3588 3354 564 8633 1306 8543 3449 4656 2959 4250 7070 -201 5545 2955 4322 8128 3186 5741 1945 7035 6763 8133 1201 8842 5666 8808 1637 5838 4904 -576 6589 6484 7128 5719 5254 6904 7100 3348 1471 1736 2182 8215 3112 2670 7458 6326 4964 87 2787 4158 5649 -335 2640 4197 4224 5011 1294 5870 2312 1113 8283 5063 7096 -11 3862 6910 3714 2060 4318 1569 5081 3571 744 459 8317 8229 -846 1843 456 477 3217 1493 4198 1700 7537 3110 1841 1610 5894 197 3894 6645 2411 4961 5404 3081 3150 1469 487 4697 1717 5531 1918 2899 5198 733 478 5283 4916 -864 2836 1387 8487 543 341 2334 2185 59 6052 3500 1588 8621 3295 4335 3034 6324 8795 33 2210 8171 8676 4910 4919 1242 1369 607 5943 8374 4010 -402 7630 1438 4431 2635 818 8336 8021 1013 6726 6892 -927 6157 3790 2078 3397 7324 5339 6559 8180 828 2342 7695 8120 3617 3743 498 979 1501 -133 4867 5993 -739 3266 3203 6682 -952 1421 2696 2209 722 6950 1986 6347 7832 5183 2206 1042 5374 5470 295 6462 -604 -29 8267 3955 -238 4433 4182 5234 6491 7881 51 -921 4583 1704 4639 4601 547 7944 8281 -374 6906 2869 3241 7717 4026 111 7573 8458 7995 1240 7098 5386 -520 8084 975 2514 6204 8280 5868 6667 4295 1677 8149 297 749 8380 1289 7040 -703 1545 7159 -275 3277 1749 7900 3249 4512 2177 2095 1044 5131 1392 8161 4031 674 4542 5764 755 3459 7726 666 661 4352 8542 6522 -533 2235 1047 8652 1372 2432 -418 5588 1427 2135 -336 7655 3146 6110 6033 5811 -777 3988 7090 5813 6779 6061 245 -568 512 -896 3540 8523 7515 6009 4778 -911 1525 653 271 2505 1347 2936 7602 5367 6635 7676 -404 17 5112 6912 223 4375 3962 6894 3927 3379 8388 2027 3261 8289 8081 614 7685 6985 3058 -387 2665 8451 1342 -24 8028 8976 2435 3589 4256 -327 2062 8907 -322 7001 1055 6330 2667 210 2717 -254 8749 6976 5656 521 7087 -638 42 2276 2274 8889 8248 5240 2345 2419 5760 -235 6391 4261 7531 5409 7682 8187 1362 -250 -359 4471 6011 -851 8647 4669 3409 4518 5652 221 3981 6872 7308 -652 7849 7706 422 4164 -809 5573 8784 8919 8917 5204 3437 -293 6916 -253 7405 1867 1959 6112 -430 799 970 2506 8461 2386 -872 3026 1988 7345 2860 4521 8400 1360 5502 2171 2285 4815 3314 3392 8205 8178 2392 2297 3333 2455 731 2887 -329 782 5629 5664 7843 7562 -115 7820 1866 127 1215 7410 4233 8240 5783 6530 6174 2115 3767 3816 -213 8849 7300 3780 1981 551 8155 745 5952 6848 8992 5512 1649 6994 5111 4149 4452 8043 5444 8298 4076 3393 6036 4232 2126 6699 5955 8258 4302 7505 5355 8911 8202 2300 4029 453 5731 763 4657 6373 7818 4301 6015 164 2347 4977 7740 4194 677 -134 8899 6882 6489 2217 2103 7313 6006 1973 5534 5319 1534 5336 -88 2792 1685 1963 6971 6495 4443 -204 713 6975 1582 13 1966 3788 3857 5068 7331 7933 3456 7680 -788 1355 4661 7822 -489 -793 6171 5685 1925 6868 -363 -560 687 3834 3663 7354 7403 8206 5607 3661 8111 7382 5417 1070 -508 386 5176 8863 2145 2942 4080 213 7679 3283 5927 -571 -72 -206 5001 4527 7022 5317 8545 7857 5565 4655 7134 6278 6193 3216 8339 793 4174 5075 385 2160 7072 6482 3770 -771 7156 5867 2408 4652 7419 7116 8862 1465 5634 181 7299 7396 488 8263 1026 7206 5310 3686 5289 4650 5295 1065 -199 3317 6765 2732 6802 7941 3465 8739 8293 -905 -963 6260 -157 5059 3246 6702 1194 2146 4701 -439 -855 8284 5536 3949 305 5683 1702 4114 6392 5150 3997 792 8302 7364 -926 435 1208 872 -821 1418 5216 3435 439 5488 8582 8404 7207 4230 6947 3365 3632 2100 -472 741 6970 7399 4469 4314 703 5023 686 7835 2790 1241 4215 3509 6263 5287 1585 8880 -666 3925 5369 7637 457 -890 -259 378 6422 5601 -357 1141 1731 7838 838 3239 6927 3649 3505 1322 6857 1192 6080 8038 303 -943 4658 -609 7909 8098 4291 6450 3582 -718 85 5401 2718 8826 5765 6230 984 8158 -170 5548 4912 7234 -21 2328 336 5015 5679 5465 1782 4284 1037 3566 7045 6328 5494 2322 3214 5734 7773 -683 6984 831 1232 -97 1357 3032 2449 1667 811 257 7511 -114 2812 1881 5049 1092 5373 4866 4281 2453 5034 7081 4576 2962 -54 8386 7986 4820 -179 7619 3681 1245 7545 3444 6416 3910 4278 1231 -269 6091 404 6068 2627 -825 6200 7217 6536 6735 100 1448 7389 2676 4777 5830 8204 -906 5846 4136 7872 1849 -479 8423 3151 -603 2867 8918 2651 -334 746 1733 5632 5391 3512 1117 7097 4869 6210 6769 4279 7625 6140 -936 781 2161 517 27 1615 8928 2733 351 8044 280 3789 3835 3352 8741 7601 6129 6551 7968 3959 3516 1767 8683 -563 244 2013 7056 8768 3463 6184 8242 6072 7432 4634 7576 1045 5219 4259 2806 4665 4534 -976 2203 5263 506 2701 2943 1188 1014 1890 8365 5363 5732 -621 6644 -301 8869 4676 2083 -381 302 2175 367 5661 8176 4959 -935 2360 1671 8456 2799 8474 -541 3996 7957 2053 1354 2427 1298 -786 3733 1155 2315 7211 304 2944 6913 3304 -113 3036 4531 -176 1838 4584 7507 796 1948 -933 5087 6941 8445 4003 2409 631 2713 7981 8786 4289 3730 4047 4418 5262 3017 -271 7085 7841 6525 1815 7069 3234 1455 6591 6908 429 4064 1016 7477 -195 2162 922 1738 1512 6425 2586 -650 7383 1743 7288 -883 8309 1962 -236 2620 1718 6509 2996 4221 4987 -378 5769 3010 6538 122 8011 1927 8554 1882 5553 5387 3972 242 1304 4636 328 2726 8953 2827 8625 1264 5413 4703 8105 4125 2479 5903 4887 2043 6696 8166 8678 7579 8931 4097 1433 5076 1020 2282 4101 7688 1614 4495 8226 6325 1468 7901 238 2474 6935 4357 -916 8207 6983 2622 3501 1460 4722 5012 1394 624 6517 4806 7952 5698 7412 7457 6433 -919 -118 7903 259 2122 1321 8620 2035 8123 8970 3188 3531 8068 366 4094 -539 8316 2907 4682 5482 3149 3680 5217 -26 3332 1515 -490 7168 736 6620 1769 5615 8354 2838 846 3293 -984 2487 -617 4787 -340 5508 3667 5230 3913 7332 6719 5286 1744 -732 2744 4208 7118 3721 6118 5382 7106 6829 207 3791 1872 5021 834 -608 8446 5463 337 3825 6572 7385 3076 5099 3520 3472 -234 -99 7343 35 1626 6436 2051 3657 1420 8455 8839 6407 8580 3235 4903 -613 829 5352 8669 2922 1669 8019 7198 6736 764 4814 3549 5199 -377 4464 2624 7643 7518 99 6612 7503 8963 5966 2647 -177 797 8101 -721 5359 5302 1517 515 -81 -537 8067 6297 8197 371 2834 982 8279 870 -196 8903 8988 6265 5950 -446 529 5187 6558 3271 -256 2990 858 -126 3238 6494 -670 8062 1507 4196 6062 7710 4294 6203 4543 1886 8873 3143 -980 3043 10 2167 8951 4851 2720 49 8239 5155 6744 4406 8160 4456 2055 -765 209 4012 3062 3196 3809 6024 8792 2072 7782 5188 1371 8020 6279 2992 695
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
0 0
My AC output:

Code: Select all


Set 1:
  Subset 1:
    -880
  Subset 2:
    -880 3346
  Subset 3:
    -880 3346 7245
  Subset 4:
    -880 3346 7245 8398
  Subset 5:
    -880 3346 7245 8398 8897
  Subset 6:
    -880 3346 7245 8398 8897 8956
  Subset 7:
    -880 3346 7245 8398 8897 8956 8987
  Subset 8:
    -880 3346 7245 8398 8897 8956 8987 8998
  Subset 9:
    -880 3346 7245 8398 8897 8956 8987 8998 8999
  Subset 10:
    -880 3346 7245 8398 8897 8956 8987 8994 8996 8997
  Subset 11:
    -880 3346 7245 8398 8897 8956 8987 8994 8996 8997 8999
  Subset 12:
    -880 3346 7245 8398 8897 8956 8987 8989 8990 8993 8997 8999
  Subset 13:
    -880 3346 7245 8398 8897 8956 8973 8974 8977 8979 8984 8994 8996
  Subset 14:
    -880 3346 7245 8398 8897 8956 8973 8974 8977 8979 8984 8994 8996 8997
  Subset 15:
    -880 3346 7245 8398 8897 8956 8973 8974 8977 8979 8984 8994 8996 8997 8999
  Subset 16:
    -880 3346 7245 8398 8897 8956 8973 8974 8977 8979 8984 8989 8990 8993 8997 8999
  Subset 17:
    -880 3346 7245 8398 8897 8956 8957 8958 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 18:
    -880 3346 7245 8398 8897 8910 8935 8957 8958 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 19:
    -880 3346 7245 8398 8897 8910 8935 8937 8941 8944 8949 8950 8972 8982 8983 8985 8993 8997 8999
  Subset 20:
    -880 3346 7245 8398 8897 8910 8935 8937 8941 8944 8949 8950 8967 8968 8971 8982 8983 8985 8993 8997
  Subset 21:
    -880 3346 7245 8398 8897 8910 8935 8937 8941 8944 8949 8950 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 22:
    -880 3346 7245 8398 8897 8910 8913 8915 8916 8938 8944 8949 8950 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 23:
    -880 3346 7245 8398 8897 8910 8913 8915 8916 8922 8929 8934 8936 8947 8952 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 24:
    -880 3346 7245 8398 8754 8822 8885 8910 8913 8915 8916 8938 8944 8949 8950 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 25:
    -880 3346 7245 8398 8754 8822 8885 8910 8913 8915 8916 8922 8929 8934 8936 8947 8952 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 26:
    -880 3346 7245 8398 8754 8822 8858 8867 8877 8884 8886 8913 8937 8941 8944 8949 8950 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 27:
    -880 3346 7245 8398 8754 8822 8858 8867 8877 8884 8886 8913 8915 8916 8938 8944 8949 8950 8967 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 28:
    -880 3346 7245 8398 8754 8822 8858 8867 8877 8884 8886 8913 8915 8916 8922 8929 8934 8936 8947 8952 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 29:
    -880 3346 7245 8398 8754 8778 8790 8796 8801 8810 8825 8838 8850 8874 8900 8921 8929 8934 8936 8947 8952 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 30:
    -880 3346 7245 8398 8754 8778 8790 8796 8801 8810 8811 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 31:
    -880 3346 7245 8398 8754 8757 8765 8775 8790 8796 8801 8810 8825 8838 8850 8874 8900 8921 8929 8934 8936 8947 8952 8968 8971 8982 8983 8985 8993 8997 8999
  Subset 32:
    -880 3346 7245 8398 8754 8757 8765 8775 8790 8796 8801 8810 8811 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 33:
    -880 3346 7245 8398 8754 8757 8765 8767 8769 8777 8780 8798 8800 8804 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 34:
    -880 3346 7245 8398 8547 8705 8757 8765 8767 8769 8777 8780 8798 8800 8804 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 35:
    -880 3346 7245 8398 8547 8705 8712 8746 8752 8758 8759 8769 8777 8780 8798 8800 8804 8823 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 36:
    -880 3346 7245 8398 8547 8705 8712 8746 8752 8758 8759 8769 8777 8780 8798 8800 8804 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 37:
    -880 3346 7245 8398 8547 8562 8649 8684 8712 8746 8752 8758 8759 8769 8777 8780 8798 8800 8804 8823 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 38:
    -880 3346 7245 8398 8547 8562 8649 8684 8712 8746 8752 8758 8759 8769 8777 8780 8798 8800 8804 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 39:
    -880 3346 7245 8398 8547 8562 8603 8638 8684 8712 8746 8752 8758 8759 8769 8777 8780 8798 8800 8804 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 40:
    -880 3346 7245 8398 8547 8562 8603 8638 8648 8663 8712 8746 8752 8758 8759 8769 8777 8780 8798 8800 8804 8813 8816 8824 8844 8852 8853 8872 8887 8888 8895 8898 8905 8908 8917 8918 8928 8953 8970 8988
  Subset 41:
    -880 3346 7245 8398 8547 8562 8603 8607 8608 8631 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 42:
    -880 3346 7245 8398 8547 8562 8590 8592 8607 8608 8631 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 43:
    -880 3346 7245 8398 8547 8562 8590 8592 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8691 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 44:
    -880 3346 7245 8398 8547 8562 8590 8592 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 45:
    -880 3346 7245 8398 8547 8562 8578 8579 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 46:
    -880 3346 7245 8398 8520 8537 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8691 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 47:
    -880 3346 7245 8398 8520 8537 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 48:
    -880 3346 7245 8398 8520 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 49:
    -880 3346 7245 8398 8416 8465 8485 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8691 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 50:
    -880 3346 7245 8398 8416 8465 8485 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 51:
    -880 3346 7245 7320 8381 8416 8465 8485 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 52:
    -880 3346 7245 7320 7914 8013 8087 8268 8511 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 53:
    -880 3346 7245 7320 7914 8013 8087 8268 8416 8465 8485 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8691 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 54:
    -880 3346 7245 7320 7914 8013 8087 8268 8416 8465 8485 8525 8529 8540 8552 8553 8568 8588 8593 8600 8601 8604 8629 8632 8634 8655 8662 8664 8688 8690 8695 8716 8721 8729 8732 8735 8738 8747 8771 8789 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 55:
    -880 3346 7245 7320 7914 8013 8087 8268 8330 8353 8358 8359 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 56:
    -880 3346 7245 7320 7914 8013 8087 8268 8330 8342 8343 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 57:
    -880 3346 7245 7320 7914 8013 8087 8268 8330 8333 8337 8343 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 58:
    -880 3346 7245 7320 7914 8013 8087 8268 8301 8306 8315 8342 8343 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 59:
    -880 3346 7245 7320 7914 8013 8087 8268 8301 8306 8315 8333 8337 8343 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 60:
    -880 3346 7245 7320 7914 8013 8087 8212 8224 8238 8288 8290 8295 8313 8332 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 61:
    -880 3346 7245 7320 7914 8013 8087 8102 8122 8124 8181 8195 8208 8241 8276 8305 8308 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 62:
    -880 3346 7245 7320 7914 8013 8087 8102 8122 8124 8130 8131 8134 8195 8208 8241 8276 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 63:
    -880 3346 7245 7320 7914 8013 8087 8102 8122 8124 8130 8131 8134 8195 8208 8241 8276 8305 8308 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 64:
    -880 3346 7245 7320 7914 8013 8024 8073 8076 8102 8122 8124 8130 8131 8134 8195 8208 8241 8276 8352 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 65:
    -880 3346 7245 7320 7914 8013 8024 8073 8076 8102 8122 8124 8130 8131 8134 8195 8208 8241 8276 8305 8308 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 66:
    -880 3346 7245 7320 7914 7985 7996 8024 8073 8076 8102 8122 8124 8130 8131 8134 8195 8208 8241 8276 8305 8308 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 67:
    -880 3346 7245 7320 7914 7920 7928 7996 8024 8073 8076 8102 8122 8124 8130 8131 8134 8195 8208 8241 8276 8305 8308 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 68:
    -880 3346 7245 7320 7401 7475 7871 7892 7945 7963 8002 8022 8075 8100 8124 8130 8131 8134 8195 8208 8241 8276 8305 8308 8356 8369 8370 8424 8427 8438 8440 8448 8459 8463 8479 8483 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 69:
    -880 3346 7245 7320 7401 7475 7871 7892 7923 7931 7942 7971 7989 7993 7994 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 70:
    -880 3346 7245 7320 7401 7475 7524 7777 7892 7923 7931 7942 7971 7989 7993 7994 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 71:
    -880 3346 7245 7320 7401 7475 7524 7777 7811 7827 7837 7923 7931 7942 7971 7989 8008 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 72:
    -880 3346 7245 7320 7401 7475 7524 7777 7811 7827 7837 7923 7931 7942 7971 7989 7993 7994 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 73:
    -880 3346 7245 7320 7401 7475 7524 7777 7781 7789 7827 7837 7923 7931 7942 7971 7989 7993 7994 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 74:
    -880 3346 7245 7320 7401 7475 7524 7538 7683 7732 7811 7827 7837 7923 7931 7942 7971 7989 7993 7994 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 75:
    -880 3346 7245 7320 7401 7475 7524 7538 7683 7732 7763 7781 7789 7827 7837 7923 7931 7942 7971 7989 8008 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262 8274 8335 8372 8377 8395 8488 8497 8512 8515 8519 8524 8527 8531 8534 8557 8583 8616 8641 8659 8677 8710 8714 8725 8794 8799 8803 8831 8837 8842 8849 8863 8880 8918 8928 8953 8970 8988
  Subset 76:
    -880 3346 7245 7320 7401 7475 7524 7538 7683 7732 7763 7781 7789 7827 7837 7923 7931 7942 7971 7989 7993 7994 8032 8035 8042 8060 8064 8078 8092 8106 8125 8177 8191 8218 8230 8231 8236 8247 8262

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11031 - Looking for a Subset

Post by andysoft » Fri May 09, 2008 8:12 pm

Hail people!
I was trying to solve this one all day long..
I used LIS/LDS algorithm that works within N*Log(L), but I just do not understand, how your solutions handle this case:
6 1
1000 1002 1 2 3 4
2

Running LIS algorithm will make 1-2-3-4 the longest subsequence... And if I want to find increasing subsequence of length=2, it will return 1,2; though correct answer is 1000;1002..
Any hint?

Thank you for attention
Now I lay me down to sleep...
my profile

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11031 - Looking for a Subset

Post by sohel » Sat May 10, 2008 4:10 am

Using LIS to solve the problem would be tough.
LDS should be more straight forward.

Code: Select all

6 1
1000 1002 1 2 3 4
2
  • Reverse the array -> { 4 3 2 1 1002 1000 }
    Apply LDS to get seq[] (1 2 3 4 1 2 }
Since we are looking for 2-sub, then isn't the last value in the seq[] whose value is >= 2 the first value in the required result (1 2 3 4 1 2). This 2 corresponds to 1000. The other numbers in the required result should follow the same method.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11031 - Looking for a Subset

Post by andysoft » Sat May 10, 2008 12:21 pm

It seems that I've got what you mean.
I shall apply LDS to the reversed sequence and get sequence seq[]. And after that, if I want to find the LIS of length x, I should find x in the seq[], and I shall start search from the end.. And I will find the needed LIS (described in problem statement)..

But the only question is the following:
I know how to that with O(N^2) algorithm - it generates array, let it be seq, and seq(i) means: 'what is the maximum length of LDS finishing on element i'. But O(N*Log(L)) LDS algorithm stores other information in seq. seq(i) in O(N*Log(L)) LDS is 'what is the maximum element of LDS of length = i'.
If it's unclear, let's look at our test case array (already reversed):

Code: Select all

4 3 2 1 1002 1000
O(N^2) LDS will produce the following seq[]:

Code: Select all

1 2 3 4 1 2 
And O(N*Log(L)) algorithm produces the following seq[]:

Code: Select all

1 2 3 4
I used LDS algorithm described at wikipedia: http://en.wikipedia.org/wiki/Longest_in ... ubsequence

I dunno how to do the problem, with such seq[]....

How shall I change algrothim?

Thank you for attention
Now I lay me down to sleep...
my profile

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11031 - Looking for a Subset

Post by sohel » Sun May 11, 2008 10:26 am

Hmm... got your point.
I know how to that with O(N^2) algorithm - it generates array, let it be seq, and seq(i) means: 'what is the maximum length of LDS finishing on element i'
This can be done in O( N * log(L) ) as well.
Lets see how it works:
We need 3 arrays:
1. A[] = {4 3 2 1 1002 1000} (this is the input array after reversing)
2. seq[] = ( seq[i] means - 'what is the maximum length of LDS finishing on element i)
3. abc[] = ( this is a helper array and it guides us to create the seq[] ) Excuse my nomenclature, it is usually very crappy.

Initially both seq and abc arrays are empty. For each element that we iterate in A[], we have to fill the corresponding index in the seq[] and update abc[] accordingly. After everything is complete, seq[] will have the same number of elements as that of array[], but abc[] will have a cardinality equaling the value of LDS.

For the sake of convenience, we are using 1 base index.
#1 - 4
For the first number just set seq[1] with 1 and abc[1] with 4.
seq[] = {1}
abc[] = {4}

#2 - 3
Look for the smallest number in abc[] whose value is > 3 and place it right after that.
We have 4 and so place 3 on the right side of 4. seq[] will be appended with the index of the value in abc[] were just placed 3. It is the 2nd index and thus seq[] will be appended with 2.
seq[] = {1, 2}
abc[] = {4, 3)

#3 - 2
Look for the smallest number in abc[] whose value is >2 and place it right after that.
seq[] gets updated with the index in abc[] where we place 2.
seq[] = {1, 2, 3}
abc[] = {4, 3, 2}

#4 - 1
Look for the smallest number in abc[] whose value is >1 and place it right after that.
seq[] = {1, 2, 3, 4}
abc[] = {4, 3, 2, 1}

#5 - 1002
Now then. Look for the smallest number in abc[] > is 1002. There is no such number and so place it at index 1.
seq[] gets updated with the index of 1002 in abc[].
seq[] = {1, 2, 3, 4, 1}
abc[] = {1002, 3, 2, 1} (note that we are replacing 1002 and not inserting)

#6 - 1000
The smallest value larger than 1000 in abc[] is 1002 and it as at index #1. So we place 1000 at #2 in abc[]
seq[] = {1, 2, 3, 4, 1, 2}
abc[] = {1002, 1000, 2, 1}

Here you go.
abc[] is always sorted. So when we are searching for smallest value in abc[] larger than 'X', we can use binary search and thus that results in an overall complexity of O( N * log(L) ) .

With the resultant seq[], you can find the required result in O(N).

The explanation could be a little disarrayed, but hope it helps nonetheless.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11031 - Looking for a Subset

Post by andysoft » Sun May 11, 2008 8:46 pm

Hello, sohel!
Thank you for you explanation! It is very detailed and good, don't worry :)
I understand your method, and the only thing I had trouble with was outputting correct sequence.. It outputted sequences which were correct, but not fine for this problem. Finally I managed how to output fine sequences!
So I got Accepted in 0.190

Again thank you for your support.
Now I lay me down to sleep...
my profile

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

11031 - Looking for a Subset

Post by BUET » Fri Aug 23, 2013 3:45 pm

mf's output is not correct according to my accepted output.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11031 - Looking for a Subset

Post by brianfry713 » Sat Aug 24, 2013 12:54 am

My AC code agrees with mf's output, what is your output BUET?
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 110 (11000-11099)”