11158 - Elegant Permuted Sum

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

Moderator: Board moderators

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh
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
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

extended greedy

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
New poster
Posts: 5
Joined: Tue Mar 15, 2005 10:33 pm
Location: Joao Pessoa, Paraiba, Brasil
A1 wrote: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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11158 - Elegant Permuted Sum

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

Keep posting

zyxw
New poster
Posts: 24
Joined: Sat Mar 22, 2008 5:49 am
Location: Chennai
Contact:

Thanks!!

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
I am not totally useless, because I can still be used as a bad example

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

WA: 11158 - Elegant Permuted Sum

can someone post me some critical I/O of( 11158 - Elegant Permuted Sum ).
Thanx for your reply.
ACC.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

matheuscscp
New poster
Posts: 1
Joined: Sun Mar 15, 2015 4:45 am

Re:

A1 wrote: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?