11158 - Elegant Permuted Sum

[A1]

Sedefcho;
Try to be little more greedy
For example you have 5 numbers : 1 2 3 4 7
first we take 7 1 (highest & lowest)
then the remaining numbers are 2 3 4
now in the remaining list 4 and 2 is the highest and lowest. we will try to put any of these two numbers in our output list's beginning or ending position. things will go like this:
_ 7 1 _
4 at end : _ 7 1 4 --> 3 (abs(1-4))
4 at begin : 4 7 1 _ --> 3
2 at end : _ 7 1 2 --> 1
2 at begin : 2 7 1 _ --> 5

so '2' at the beginning position of the output list gives us best result so we will put it there and the new output list will be: 2 7 1, and the remaining list is off course 3 4.
continue this process until the remaining list is empty and u will got the result..

[DP]

Hi Everyone,
I want to solve it by DP. But couldn't find the right sequence. How can i distinctly make the
tree edge for caching?

Please help me or some hints from someone who solved!!!
thanks

DP

[Sedefcho]

OK, I see. So it is greedy at the end of the day.

To rio: yes, I handle this test case as it exactly fits in the
greedy approach:
1) Choose the biggest number ( 10 ) and add it to the permutation
---> 10
2) Choose the the smallest number ( 1 ) and add it on one side
of the permutation formed so far:
---> 1, 10
or
---> 10, 1
(these two are equivalent)
3) take the next biggest number ( 9 ) and put it on one side
of the sequence formed so far (the side which generates higher
diff sum) - this way we get:
---> 9, 1, 10
or
---> 10, 1, 9
depending on which side we chose to put the number 1 on step 2.

So my program works OK in this case - it prints 17.

I will think a bit, I still fail on test cases
8 and 12 from the sample INPUT posted above.

So it seems the greedy idea works but I am missing
some small detail which makes my program print
incorrect results in some special cases.

[Sedefcho]

Thank you, A1 .

I slightly modified my program to use your "extended greedy idea"
and now I get ACC. So at each step we have 4 options to continue
(put minValue on the left, put minValue on the right,
put maxValue on the left, put maxValue on the right).

And in my previous algorithm I used to try only 2 of these
4 possible options at each step, that's why sometimes my
program was outputting non-optimal answers.

Thanks for all the replies.

[guma]

Sedefcho;
Try to be little more greedy
For example you have 5 numbers : 1 2 3 4 7
first we take 7 1 (highest & lowest)
then the remaining numbers are 2 3 4
now in the remaining list 4 and 2 is the highest and lowest. we will try to put any of these two numbers in our output list's beginning or ending position. things will go like this:
_ 7 1 _
4 at end : _ 7 1 4 --> 3 (abs(1-4))
4 at begin : 4 7 1 _ --> 3
2 at end : _ 7 1 2 --> 1
2 at begin : 2 7 1 _ --> 5

so '2' at the beginning position of the output list gives us best result so we will put it there and the new output list will be: 2 7 1, and the remaining list is off course 3 4.
continue this process until the remaining list is empty and u will got the result..

Man, I was stuck on this same exact thing. This example you gave was enought to realize what was happening and I got AC
Thank you very much man.

[Chirag Chheda]

thanx sunny and rio .your test cases were really helpfull.


Keep posting

[zyxw]

Thanks a lot to sunny for the test cases. It helped me to find the reason for WA.
Also, thanks to A1 for his idea, which helped me to get AC

[sazzadcsedu]

can someone post me some critical I/O of( 11158 - Elegant Permuted Sum ).
Thanx for your reply.

ACC.

[matheuscscp]

Sedefcho;
Try to be little more greedy
For example you have 5 numbers : 1 2 3 4 7
first we take 7 1 (highest & lowest)
then the remaining numbers are 2 3 4
now in the remaining list 4 and 2 is the highest and lowest. we will try to put any of these two numbers in our output list's beginning or ending position. things will go like this:
_ 7 1 _
4 at end : _ 7 1 4 --> 3 (abs(1-4))
4 at begin : 4 7 1 _ --> 3
2 at end : _ 7 1 2 --> 1
2 at begin : 2 7 1 _ --> 5

so '2' at the beginning position of the output list gives us best result so we will put it there and the new output list will be: 2 7 1, and the remaining list is off course 3 4.
continue this process until the remaining list is empty and u will got the result..

I implemented this solution and it worked. But what is the guarantee I have that adding the smallest or biggest number of the remaining (sorted) list to one of the two edges of the current (optimal) list keeps the permutation optimal? This is not clear for me. I mean, why it is not necessary to check positions between the elements of the current list? Why only checking the edges is enough?