11158 - Elegant Permuted Sum

[jan_holmes]

Anyone can give some tricky testcases ?

[sunny]

i dont know any tricky cases. although here are some random cases:
input:

Code: Select all

20
4 1 1 1 2 
4 7 8 7 8 
5 1 2 8 7 8 
5 7 7 8 8 8
41 449 328 474 150 709 467 329 936 440 700 117 258 811 952 491 993 931 823 431 359 590 899 153 292 370 404 698 699 876 442 705 757 527 868 893 642 273 18 885 675 788 
8 303 656 660 126 704 225 862 522 
2 630 725 
45 847 715 732 502 778 304 32 168 841 288 76 31 934 245 626 419 782 875 723 346 335 992 70 369 545 610 611 60 935 738 829 962 369 918 282 928 407 602 312 532 517 102 80 907 525 
39 84 635 629 682 921 964 304 642 364 16 717 898 53 264 824 751 558 92 496 963 277 152 618 333 743 632 559 27 40 323 149 925 703 953 427 76 161 990 326 
4 275 726 373 931 
35 177 749 197 570 416 922 479 17 397 139 900 559 744 654 393 353 597 517 527 477 568 37 599 326 281 806 365 9 592 998 321 176 649 460 273 
42 53 998 392 911 894 785 109 467 725 879 624 461 790 419 296 611 791 505 295 609 917 434 580 244 503 525 776 273 218 998 839 577 975 670 192 465 90 329 493 586 285 494 
2 175 445 
39 560 777 784 266 570 778 982 130 452 599 520 280 32 155 172 628 951 185 796 866 137 500 186 632 248 35 308 624 336 882 857 405 840 122 821 415 860 967 312 
36 11 694 554 448 865 365 70 702 598 508 983 843 844 674 388 780 240 407 998 575 158 275 61 395 589 734 823 902 165 152 696 172 957 298 366 664 
5 545 431 533 434 503 
4 42 697 750 123 
30 263 971 671 517 527 420 847 937 193 172 294 396 258 89 464 266 443 709 96 690 285 651 781 251 309 331 154 33 912 798 
47 925 309 729 293 539 623 955 481 140 173 202 122 159 530 430 162 456 32 638 266 413 236 4 128 481 741 629 173 305 470 995 166 4 769 896 941 384 192 622 451 410 305 799 305 849 348 139 
41 269 511 169 756 238 762 666 175 972 99 472 184 620 798 95 497 623 542 923 12 943 48 167 973 405 488 566 703 18 484 142 205 255 51 893 168 352 391 944 256 141 

ouput:

Code: Select all

Case 1: 2
Case 2: 3
Case 3: 25
Case 4: 4
Case 5: 18884
Case 6: 3278
Case 7: 95
Case 8: 23175
Case 9: 21569
Case 10: 1665
Case 11: 14184
Case 12: 18066
Case 13: 270
Case 14: 20176
Case 15: 17755
Case 16: 396
Case 17: 1990
Case 18: 13872
Case 19: 21627
Case 20: 21388

[jan_holmes]

ACed.... Thx for the testcases...

[aha2007]

Can any one tell me how to solve it. Is it a DP problem , if so then how to solve it.It seems to me a longest path problem. I used backtracking and got TLE. plz help me.

[jan_holmes]

I don't think DP is really needed to solve this problem...(at least, I didn't use it to solve this problem). Just think about the simple one (Hint : sort the numbers with smart brute force would be enough).

[emotional blind]

GREEDY

[asif_rahman0]

emotional,
Would you tell me the GREEDY approach as a hint?

[mrahman]

Here is the greedy approah. First sort the array.
Then try to construct the permutation array placing each pair(highest,lowest) of integer into a blank array. Place the highest and lowest number in the middle of the permutation array. Then place the second highest number neighbouring to the lowest number and second lowest number neighbouring to the highest number and so on...

After using all the number you can run through the created array to compute the elegant permuted summation.

For example,

The input:

Code: Select all

1
5 1 2 8 7 8

sorted array:

Code: Select all

1 2 7 8 8

Blank elegant permutation array:

Code: Select all

_ _ _ _ _

after placing highest and lowest number:

Code: Select all

_ _ 8 1 _

after placing 2nd highest and 2nd lowest number:

Code: Select all

_ 2 8 1 8

placing last number

Code: Select all

7 2 8 1 8

done....

Sorry for my poor english....

[deepesh]

how do you prove that the greedy approach gives you an optimal solution?

[paulmcvn]

Your approach is wrong for test 8 above.

[paulmcvn]

Sorry, you're right!

Just notice the case when there's one last number in A.

[Tommy Wu]

Sorry, you're right!

Just notice the case when there's one last number in A.

Sorry for my lack of knowledge, but would you explain what is "one last number in A"?

Thanks.

Sorry for my poor English grammar.

[Sedefcho]

After thinking a bit on this problem I invented
absolutely the same greedy idea as mrahman suggested

I implemented it and I got WA. So I read this thread and ...
if the I/O posted above is from an ACC program then
my program fails on test cases 12 and 8.

So, paulmcvn, what do you mean by "sorry, you are right" ?

If you mean that the greedy approach described above is correct ...

Well, apparently there're cases for which it is not correct
( if, of course, the test cases posted above
are from an ACC program ).

Actually I doubted that this is a greedy problem
because if it were then the restrictions that
1) count of numbers < 51
2) value of numbers is <= 1000
would just be useless. Anyway the greedy idea seemed
so convincing that I decided to try it out.

I tend to think now that greedy approach does
not give an optimal solution ( as I got WA ).

Any ideas are welcome.

Can someone give me a short counter-example
showing why this greedy idea is wrong?

For the Input posted above I get this output:

Code: Select all

Case 1: 2
Case 2: 3
Case 3: 25
Case 4: 4
Case 5: 18884
Case 6: 3278
Case 7: 95
Case 8: 23149
Case 9: 21569
Case 10: 1665
Case 11: 14184
Case 12: 18044
Case 13: 270
Case 14: 20176
Case 15: 17755
Case 16: 396
Case 17: 1990
Case 18: 13872
Case 19: 21627
Case 20: 21388

Regards

[rio]

I'm not sure, but this might be the test case you wanted.

Code: Select all

1
3 1 9 10

The answer is 17 (10 1 9). Are you handling this right?

[sohel]

Actually I doubted that this is a greedy problem because if it were then the restrictions that
1) count of numbers < 51
2) value of numbers is <= 1000
would just be useless. Anyway the greedy idea seemed
so convincing that I decided to try it out.

This is actually a greedy problem ...
The constraints were set low to allow other 'dp' solutions(if any) to get accepted within the time limit.

http://acm.uva.es/p/problemstatnew.php?prob=11158

Seems that Per Austrin is the only one who approached non-greedily .