Phone

+919997782184

Email

support@roboticswithpython.com

Geeks of Coding

Home Forums Cody Bank Domino Solitaire (Indian National Olympiad in Informatics, 2008)

• Author
Posts
• #232

(Indian National Olympiad in Informatics, 2008)

Here’s the link of Github Repository for this question –

In Domino Solitaire, you have a grid with two rows and many columns. Each square in the grid contains an integer. You are given a supply of rectangular 2 × 1 tiles, each of which exactly covers two adjacent squares of the grid. You have to place tiles to cover all the squares in the grid such that each tile covers two squares and no pair of tiles overlap.

The score for a tile is the difference between the bigger and the smaller number that is covered by the tile. The aim of the game is to maximize the sum of the scores of all the tiles.

Here is an example of a grid, along with two different tilings and their scores.

The score for Tiling 1 is 12 = (9−8)+(6−2)+(7−1)+(3−2) while the score for Tiling 2 is 6 = (8−6)+(9−7)+(3−2)+(2−1). There are other tilings possible for this grid, but you can check that Tiling 1 has the maximum score among all tilings.

Your task is to read the grid of numbers and compute the maximum score that can be achieved by any tiling of the grid.
Solution hint
Recursively find the best tiling, from left to right. You can start the tiling with one vertical tile or two horizontal tiles. Use dynamic programming to evaluate the recursive expression efficiently.
Input format
The first line contains one integer N, the number of columns in the grid. This is followed by 2 lines describing the grid. Each of these lines consists of N integers, separated by blanks.
Output format
A single integer indicating the maximum score that can be achieved by any tiling of the given grid.
Test Data:
For all inputs, 1 ≤ N ≤ 105. Each integer in the grid is in the range {0,1,…,104}.
Sample Input:

```4
8 6 2 3
9 7 1 2
```

Sample Output:

```12
```
```4
8 6 2 3
9 7 1 2
12
```

Test Case 2

```10
8789 7959 4809 5257 4592 9455 6462 5855 6399 9569
4977 5499 7329 2997 9599 5445 2412 9838 6252 6577
```
```31597
```

Test Case 3

```100
2511 2090 9410 4226 3959 3826 2318 5356 5333 8630 9624 3155 7360 6547 503 4539 8065 6558 8119 8299 792 2046 6803 6519 9765 851 2039 2315 143 1566 141 7040 894 5713 9574 2861 1437 8254 8573 3503 2540 2862 8272 5518 9578 155 8493 9935 1672 5874 5457 3379 3689 6102 9972 4269 3263 274 8535 2766 1393 1859 2864 8412 368 6360 9530 1607 5327 6394 6831 86 7476 1983 1257 9508 5275 8492 8620 4276 800 5409 2229 6220 8377 2016 1569 1255 1554 4253 3592 8325 8073 4123 5605 7625 4737 5013 4173 2287
9668 4457 791 6609 6438 9208 9074 5723 6687 4940 3855 3866 7280 6290 3158 7736 7585 9150 5101 5567 8238 605 3218 3442 6767 7493 2552 6121 7803 9479 1702 7483 7379 9357 1309 4021 6197 2206 402 6193 5867 6284 8661 5558 3199 5171 4723 8388 9933 827 9738 7870 1030 6640 7850 249 2164 4176 4203 4686 2685 5869 9403 698 1360 1954 1818 464 9144 5064 5033 9785 2402 1599 3597 1153 5942 9486 1823 4149 3317 6659 5671 2763 753 518 9301 399 5176 3041 5035 2088 8825 8874 7437 9378 6412 9721 9874 7499

425423
```

Test Case 4

```1000 9732 3404 5420 3913 7633 7535 876 366 4670 9237 6093 9707 7672 2047 9543 5470 4593 3758 6787 5518 6895 560 8951 28 6474 2192 2293 8463 6631 2226 8236 1160 7880 5644 8338 3952 2066 8659 1334 1098 7758 9694 3964 1420 7548 2242 5258 9954 3249 9058 6006 6735 8491 7324 4498 820 3374 7984 3460 715 2218 1681 6188 7647 679 3398 6083 331 1034 8101 9192 4898 6143 7990 4630 1582 925 6307 447 6808 1033 3390 9820 781 8331 3529 3529 3224 1747 9415 3334 4048 5649 8040 7716 8457 154 3918 6929 3176 3359 3654 593 9382 2469 9232 5090 9717 2949 4831 3648 9075 4250 5399 2581 8122 178 1371 8244 2693 7789 7447 679 3086 2668 8896 8825 3019 832 3779 4953 5869 9247 6313 1333 4113 2355 5484 3026 9279 1082 4309 7390 2846 1960 1760 2900 1269 6188 9505 9004 9756 4314 5033 1185 2638 9624 7411 4327 2610 9052 364 5821 5215 1384 3523 2288 8346 9540 7727 9735 3062 2823 6019 2799 1660 1019 2427 301 746 291 5375 9691 1374 9742 8480 4418 9531 1591 5913 5519 8984 9979 2132 573 4458 6853 1835 953 7257 4974 7861 7335 2710 479 5571 6586 629 1314 7177 2400 6408 4894 9454 1696 3283 3545 1336 7520 1053 56 2640 2732 5247 7313 2681 2426 4155 4876 3980 4132 1642 4851 5739 5217 7333 8018 8109 5424 5294 6188 8436 7577 9114 5906 6402 1547 8309 3122 5826 669 4988 5183 6659 7775 3940 683 3595 1577 5890 5368 5359 6747 6100 2596 6251 760 6221 4988 4186 2696 201 3068 5404 8159 7742 1078 8131 7160 5658 7137 6828 9300 6257 7636 5942 1249 7362 5751 1085 3021 3854 3321 4940 1792 686 9788 1433 9307 663 2508 1301 2634 2207 9282 4456 9121 6571 6675 3790 7733 6189 287 3379 8078 5165 4989 3609 9758 5111 1999 1413 2367 9265 3997 5573 6408 1044 1032 2633 8390 9860 6329 6097 6842 3517 8073 845 7277 7998 7450 1662 2265 8656 4525 2728 1634 2240 7686 7339 7991 3857 3219 115 4674 2643 3955 8725 9100 2016 7780 7699 1221 5949 1962 2225 8197 9436 9812 6684 5996 5621 4958 7978 1712 1930 1724 1928 7057 4680 9591 6935 692 4337 5695 9998 1284 8939 2884 8616 3081 9725 6088 8215 4436 3126 6885 8874 7132 5863 3401 224 416 2663 9174 7636 9774 8202 2788 1959 3141 9404 8095 5064 9513 582 9082 2943 9669 516 1269 783 754 7142 3329 1774 5100 5863 4806 4960 5310 1494 2874 1415 8165 752 8445 1849 7316 2151 8208 9404 1396 7693 8799 6156 9747 6365 4977 483 1284 2973 8867 47 4319 8118 8847 4292 1967 1238 7016 3986 1670 9770 4194 8764 599 4053 2750 7690 5422 1101 5059 646 3809 6448 9765 8463 1949 3879 8190 8179 2427 8834 9010 2899 7522 4903 3549 7358 6001 359 5789 4560 5866 5534 7241 2473 9537 3753 5288 4567 2080 1149 5455 3623 2373 1038 338 4291 3433 9641 5706 8780 3110 4076 3726 9304 3534 4137 3457 5623 5149 3890 4875 1581 4079 1430 8005 8873 4510 7890 7385 2598 7501 4266 1432 2107 5361 4753 9543 3390 4658 2619 8346 9175 8933 2520 4680 8907 3954 6317 2192 9234 8380 6684 2045 3084 2221 9015 5961 1145 5517 1543 1721 7913 3072 1384 1288 7530 5368 9862 9041 4509 5493 9596 119 6135 969 3058 4938 6669 3960 3743 7410 6298 3976 6511 8721 7758 1515 9611 1651 1326 6289 2369 8876 9860 8937 6447 2369 3348 4110 5267 5668 114 6367 2745 275 5836 8657 4754 6544 2903 8579 1936 6185 390 7082 1891 1662 8118 1461 9871 9453 8611 3057 6489 2196 5127 5219 6452 5289 6941 8972 5760 8535 9275 9299 4445 3049 2186 701 4772 8928 2732 5100 9542 4329 8103 1513 4027 1733 4346 5186 7078 551 8940 3834 9733 5983 3786 1869 2456 4611 4058 6326 7887 5703 3713 3813 4314 101 8924 8979 4175 3126 9959 6614 1700 4666 1633 822 7844 4740 3799 2172 9171 1100 875 3201 9228 2001 2240 2144 6566 959 792 6597 7406 5430 2008 2737 3472 650 520 457 6564 6822 351 1687 1897 9246 1398 3625 7119 9328 1174 3371 4500 578 2764 7601 345 9306 8091 4730 9901 9585 8103 6094 3349 6981 6980 2883 1034 4310 6863 2114 4574 5213 9336 5169 7291 509 3711 8179 8728 6961 4343 3704 6294 5348 6198 6139 3992 2392 1918 9487 6535 376 3877 592 3689 6014 1224 5607 7823 1612 6730 3872 9219 2695 9116 5135 2521 6389 8477 1222 982 8968 849 6935 6875 2401 755 1898 9262 2664 975 1830 8411 4311 7520 5678 7606 9539 5818 2260 2313 7228 5053 4534 7092 360 194 953 6983 4367 1935 6073 1065 5653 69 7941 6584 8301 5031 8750 6429 8221 9795 744 6240 1356 2098 8850 9351 5437 7190 9511 3798 886 8969 5735 410 4328 2312 7495 589 9466 9442 4985 6586 2485 6036 7349 2441 8329 8963 8688 5301 6971 2715 5431 1365 4812 9010 8378 8720 1561 7147 9564 7789 986 7666 8892 4919 9886 9808 475 3000 1197 3291 759 6216 8350 5928 3569 1527 815 2441 4655 3922 8057 3313 5591 3615 7106 205 3921 3119 9400 1075 248 8638 5902 1009 169 644 6457 6383 7914 1337 4445 572 2612 4437 884 9224 7203 4095 1665 5208 3887 2621 6612 5755 333 122 2023 2934 3897 6241 7317 9297 9995 4383 7992 1961 8447 491 8382 4282 2753 1368 9299 6067 1309 5393 3861 2520 2841 1408 4093 3049 6763 8418 6822 3062 718 125 8388 2043 4622 8337 8351 6598 2704 8823 5291 7796 1301 1708 6526 2893 1584 7169 4838 5190 8548 835 1667 5010 3232 3304 8540 5268 6161 4785 8322 7287 946 746 194 4805 6197 3094 7601 4914 7476 5828 5906 5088 3988 5186 5708 1757 4520 4267
1846 1965 5603 7174 5833 9630 847 484 7787 8459 2323 1745 908 6612 3156 8743 8171 3293 153 6108 4167 4182 8247 857 106 3509 6437 7621 2939 2991 1200 1255 9487 7036 6225 6634 8643 4870 1823 6528 2269 1557 8228 1340 2562 4347 879 3239 7805 9286 3863 9965 2671 6358 8293 4721 5105 3394 3254 1521 1498 8128 7923 4886 916 726 8807 7505 8813 2245 7282 4644 584 7188 470 3436 5810 4858 6108 4431 8796 6720 6702 922 9346 7599 4620 4560 7542 2114 1733 8074 5811 4370 916 3640 2843 6130 2796 8501 4241 4435 7043 4130 190 4304 653 6886 7393 1397 5013 3268 970 6678 2966 2184 7691 3604 7242 7056 8655 4229 2865 7852 2162 5255 735 4776 4032 7245 4370 2215 6819 9083 710 1579 3309 7103 2277 1049 6255 853 7280 7115 1628 9914 6559 8794 8700 3126 8332 8862 7155 425 373 4384 221 736 2799 9846 7754 7147 6371 2678 4328 3266 1148 1795 3014 5242 8150 2649 4859 415 4087 6390 9346 1921 2420 9110 665 4641 6267 9269 4786 254 2739 5568 387 1678 9057 3704 3186 1194 7500 2022 4396 3618 5336 3448 4521 344 3298 2996 8821 1147 9711 7169 9217 5535 9729 7899 3539 1191 9548 90 9588 3652 3243 7939 1962 3766 5785 1974 744 284 5757 1240 5523 7131 7607 4446 6668 3782 8380 552 9859 3482 1772 4786 4541 6082 1848 6016 2881 8376 5607 7778 1855 6249 3018 8790 7136 5827 2522 2006 6378 9137 1157 48 186 7607 270 2041 8601 764 8623 3856 7071 9626 5103 3388 9958 4058 8041 1704 8363 526 9489 2763 7785 3468 2100 1141 5797 7571 7131 2307 9797 4628 2689 854 5008 2781 6614 2658 6642 5700 3249 9789 1526 7874 4257 6485 1026 354 1937 8475 1851 28 7434 1024 5826 8416 3494 6567 6158 1737 2001 5442 1648 9151 4540 1823 2993 7110 1297 6449 6358 3858 425 2204 9178 3849 9648 3468 5246 9016 1760 4607 53 4818 318 2880 718 8559 5249 862 6207 5661 6374 9418 4641 4027 6572 4044 2846 5220 3111 1577 4832 4315 2708 5896 7102 3643 2323 7098 9535 2546 7308 9240 6745 9037 1999 4012 231 6190 5531 7576 980 7258 9810 2545 3611 7947 4066 7799 344 1023 5142 3226 8116 9190 8006 931 8050 3885 2364 6986 9135 4744 8700 68 9557 1855 7533 3711 9601 7683 5718 4383 645 409 1784 6768 9534 5458 1712 2941 6794 7489 7301 2334 8891 4173 1048 2324 8320 3710 5929 4038 2981 6082 1870 7637 6337 9456 6274 5352 8651 6540 6489 7317 4416 4774 2413 4481 2485 486 6865 8358 9554 2096 6242 9058 9316 5333 351 67 3959 3654 5920 880 498 6626 5831 1246 6082 5183 4864 4093 6618 5224 1930 7846 5285 5010 9320 3813 8541 9897 7056 5553 9619 2932 7668 5961 4071 7228 5707 4511 274 6452 1289 3258 4861 1490 6685 1443 9440 2857 5094 6801 9675 781 6646 7809 568 4409 5627 7397 5629 2100 6760 1320 1292 465 6010 5928 8606 7293 1171 2101 9669 4760 9969 7421 7683 3835 3397 4131 3783 8250 1661 9212 6139 9254 877 7198 3280 7946 4083 9608 3322 5686 8426 4519 8910 9979 6495 9808 7568 1523 8559 6455 2801 787 451 8472 164 400 327 1271 7848 3730 4798 5302 4382 3879 8626 9792 9325 9743 2327 7279 1576 3110 2758 1958 5647 9672 4600 8782 8442 6445 6456 9806 8058 2835 6976 4700 5673 4579 1519 3184 952 1061 2790 3902 8439 2083 3793 1643 5508 9949 4275 8905 3414 4405 3259 8370 9392 9418 7880 6458 5371 2373 9722 9784 4356 3766 3379 2888 8781 2035 1747 7461 1773 7380 9375 7526 6304 6256 9318 7418 3368 6027 2652 7302 6561 5946 32 5501 688 5194 5184 5694 8182 2964 4522 6560 2252 6371 549 9599 5741 3847 9315 9467 1706 9325 1023 8433 5926 3323 4330 9585 3827 3464 7649 764 9014 9240 7838 5288 7746 4170 8254 5144 1603 6046 3849 5332 8389 659 2534 3435 1410 2208 5628 9456 7786 335 9104 6914 3901 8099 4305 5454 7668 891 6712 7684 3563 4767 3411 2149 3532 5466 708 534 9679 755 8563 9169 8247 8061 6271 3274 7614 3650 6505 1278 181 6109 1931 6802 1854 5437 9232 7075 6825 4613 469 9653 6261 5852 7032 9367 9917 1567 9400 5663 373 5943 8932 7206 2224 7542 9952 7490 7967 4815 256 7693 9258 3237 1697 3216 5528 6163 4784 8977 1495 7561 9788 8041 3830 7579 3363 4581 3906 5408 3168 8133 5380 4886 1692 3188 35 8637 5025 9134 4125 5766 7523 7288 7217 5984 1279 7524 1549 1800 1504 8764 8074 7653 8962 9050 5022 5745 6532 9374 931 8122 3967 4797 116 1281 7599 9365 8431 6388 6824 2110 8493 5829 7870 7988 9296 6250 5942 4535 6909 3083 6990 5567 2911 569 40 2241 916 852 4485 7966 215 2450 5375 1948 8920 1522 4501 744 7236 3207 8831 3315 8374 6985 8133 2176 9548 1680 4914 6923 6125 7257 6093 1341 6881 1944 3275 7548 9172 2137 7586 5 7210 6812 3493 5222 441 8277 912 4687 8709 2649 5577 5758 6564 9793 7532 8414 6185 6956 7848 1865 1106 9176 4122 14 5780 3970 8715 5755 7215 6644 6486 2468 8101 5056 5220 4232 8220 349 5099 860 5222 93 9169 7662 3388 6855 4536 4761 1494 3233 1164 4923 8709 1176 8056 9491 1541 1413 3926 7460 9380 8330 4237 5648 1385 6848 8917 6929 1476 3825 4668 6541 260 5350 4454 2532 5195 8818 485 8695 1325 758 9280 6134 992 6751 765 1506 9265 2049 2845 5512 2991 2216 7676 8262 1514 3751 2446 8693 1079 9515 1669 2271 7742 2170 7815 5209 4277 7920 4980 8639 9148 9637 5722 3340 3161 3006 3237 4331 5085 6509 765 5921 8390 8574 3057 6641 9614 5950 3601 1140
```
```4308249
```

Test Case 5

`10000`

• #238
Abhishek Tyagi
Keymaster
```def solve(l1, l2):
n = len(l1)

if n == 0:
return (0)

ans = [0 for i in range(n + 1)]

ans[n - 1] = max(l1[n - 1], l2[n - 1]) - min(l1[n - 1], l2[n - 1])

for i in range(n - 2, -1, -1):
vert = max(l1[i], l2[i]) - min(l1[i], l2[i]) + ans[i + 1]
horz = max(l1[i], l1[i + 1]) - min(l1[i], l1[i + 1]) + max(l2[i], l2[i + 1]) - min(l2[i], l2[i + 1]) + ans[
i + 2]
ans[i] = max(vert, horz)

return (ans[0])

nstr = input()
# Value of n not needed in Python
#  n = int(nstr.strip())

# Read and parse first row of numbers
line1str = input().strip()
line1strlist = line1str.split()
line1 = []
for s in line1strlist:
line1.append(int(s))

# Read and parse second row of numbers
line2str = input().strip()
line2strlist = line2str.split()
line2 = []
for s in line2strlist:
line2.append(int(s))

print(solve(line1, line2))```