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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sat Feb 03, 2007 8:54 am

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:

Post by DP » Sat Feb 03, 2007 11:14 am

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Feb 03, 2007 4:36 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

extended greedy

Post by Sedefcho » Sat Feb 03, 2007 5:22 pm

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

Post by guma » Sun Mar 04, 2007 10:30 pm

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 :P
Thank you very much man.

8)

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11158 - Elegant Permuted Sum

Post by Chirag Chheda » Mon Jun 23, 2008 11:17 am

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!!

Post by zyxw » Fri Jul 18, 2008 2:39 pm

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 :P

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

WA: 11158 - Elegant Permuted Sum

Post by sazzadcsedu » Sat Aug 08, 2009 10:48 pm

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:

Post by matheuscscp » Sun Mar 15, 2015 4:55 am

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?

Post Reply

Return to “Volume 111 (11100-11199)”