wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Minimum Set S
        
(Message started by: R on Sep 26^th, 2009, 12:28am)

Title: Minimum Set S
Post by R on Sep 26^th, 2009, 12:28am

Make a set of positive integers S, such that using at most 2 integers at a time from S, you can make all possible number in the range [1,n].
Part 1. Minimize |S|, i.e. the number of integers in set S.
Part 2. Minimize the total sum of integers in S.

[hide]An extension to the weekly puzzle of PuzzleUp.[/hide]

Title: Re: Minimum Set S
Post by R on Sep 26^th, 2009, 12:35am

Just give me a hint, not the complete solution/answer.

Title: Re: Minimum Set S
Post by sidharth on Sep 27^th, 2009, 8:23am

Giving an iterative approach to the solution. Believe a better solution does exist

[hide]
let n=20
Step 1: create the initial list using the following:
for each X ( 1 <= X <= n), X = largest element of set + y.
If y does not belong to S, add y.
After step 1, S = {1,2,3,4,5,6,7,8,12}
Step 2:
Now beginning with the 2nd largest element (X) till end of set, check whether the larger elements can be replaced using a combination of the other elements or addition of new elements where sum of new elements < sum of to be replaced elements.
After step 2: 8, 12 are replaced by 13.
S = {1,2,3,4,5,6,7,13}
[/hide]

Title: Re: Minimum Set S
Post by Grimbal on Sep 28^th, 2009, 12:36am

I solved that with a program.
There are patterns that work quite well, such as:
{1, 2, 3, ..., k-2, k-1, 2k-1, 3k-1, ...}
but you still need to find the best k and the solution isn't always optimal.

Title: Re: Minimum Set S
Post by R on Sep 28^th, 2009, 3:43am

Looking for patterns is hard. Harder is seeing varying patterns. :P
Doesn't any of greedy strategy, dynamic programming or anything help here?