Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Problem Link - http://opc.iarcs.org.in/index.php/problems/EQGIFTS

It is Lavanya's birthday and several families have been invited for the birthday party. As is customary, all of them have brought gifts for Lavanya as well as her brother Nikhil. Since their friends are all of the erudite kind, everyone has brought a pair of books. Unfortunately, the gift givers did not clearly indicate which book in the pair is for Lavanya and which one is for Nikhil. Now it is up to their father to divide up these books between them.

He has decided that from each of these pairs, one book will go to Lavanya and one to Nikhil. Moreover, since Nikhil is quite a keen observer of the value of gifts, the books have to be divided in such a manner that the total value of the books for Lavanya is as close as possible to total value of the books for Nikhil. Since Lavanya and Nikhil are kids, no book that has been gifted will have a value higher than 300 Rupees...

For the problem, I couldn't think of anything except recursion. The code I wrote is given below. But the problem is that the code is time-inefficient and gives TLE (Time Limit Exceeded) for 9 out of 10 test cases! What would be a better approach to the problem?

Code -

#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;

int n,g[150][2];

int diff(int a,int b,int f) {
    ++f;
    if(f==n) {
               if(a>b) {
                       return a-b;
               }
               else {
                    return b-a;
               }
    }
    return min(diff(a+g[f][0],b+g[f][1],f),diff(a+g[f][1],b+g[f][0],f));
}

int main() {
    int i;
    scanf("%d",&n);
    for(i=0;i<n;++i) {
                     scanf("%d%d",&g[i][0],&g[i][1]);
    }
    printf("%d",diff(g[0][0],g[0][1],0));
}

Note - It is just a practice question, & is not part of a competition.

share|improve this question
    
Your program is slow most likely because it doesn't properly utilize price differences. Sort books by value, then sort "neighbor" book pairs in that sorted collection by price difference, then use this information while distributing books –  gnat Oct 31 '12 at 13:14
add comment

3 Answers 3

up vote 7 down vote accepted

Just winging this off the top of my head before morning status meeting:

Sort books descending by value
Give first book to Lavanya
while books remain
    while Nikhil's values < Lavanya's values
        Give first book to Nikhil
    while Lavanya's values < Nikhil's values
        Give first book to Lavanya

Will that do it?

share|improve this answer
    
Oh - forgot to add that sorting can be O(n) because you know the value range, so you needn't use a general purpose sort. –  Ben Oct 31 '12 at 12:53
1  
Wouldn't this be an if conditonal rather than a while loop conditional? while Nikhil's values < Lavanya's values Otherwise a great answer. –  maple_shaft Oct 31 '12 at 12:59
3  
You're pretty close. You need to sort by the difference of values of each pair and start with the largest difference. That way a set with the largest gap but having the smallest individual values won't throw the equality off at the end. –  Karl Bielefeldt Oct 31 '12 at 13:01
    
@maple_shaft Yeah, that would be simpler and have the same result. Thanks. –  Ben Oct 31 '12 at 13:02
    
@Karl - thanks! I think I noticed that at the same time and updated. I shouldn't write algorithms before my coffee. :) –  Ben Oct 31 '12 at 13:03
show 3 more comments

Kevin Cline already said it, but deleted his answer, so I'll repeat and explain: This problem is a knapsack problem. Each pair of books can be represented by the price difference of those two books. Those price differences should be equally distributed, which equals to finding a subset of the price differences of which the sum is half the total sum of all price differences.

Example:

Pair   Book1   Book2  Difference
1      100     60     40
2      90      40     50
3      70      50     20
4      65      55     10

Examining the set of differences, {40,50,20,10}, the total is 40+20+50+10 = 120, so we look for a subset with a sum close or equal to 120/2 = 60. Using one of the existing algorithms for the knapsack problem, we get e.g. {50,10}. This subset can be mapped back to the pairs, so one child gets the more expensive book of pairs 2 and 4, while the other kid gets the more expensive book of pairs 1 and 3.

http://en.wikipedia.org/wiki/Knapsack_problem#Approximation_algorithms explains algorithms for approximating the solution of knapsack problems.

share|improve this answer
add comment

There appears to be some confusion about my comment on Ben's answer, so here's my solution standalone:

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stdlib.h>
using namespace std;

typedef pair<int, int> BookPair;
typedef vector<BookPair*> BookList;

void readBookList(BookList &books)
{
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        int cheapBook = min(a, b);
        int expensiveBook = max(a, b);
        BookPair *bookPair = new BookPair(cheapBook, expensiveBook);
        books.push_back(bookPair);
    }
}

bool diffsort(BookPair *p1, BookPair *p2)
{
    return abs(p1->first - p1->second) > abs(p2->first - p2->second);
}

void allocate(BookList &books)
{
    int lavanya = 0;
    int nikhil = 0;

    for (BookList::iterator it = books.begin(); it != books.end(); ++it)
    {
        int cheapBook     = (*it)->first;
        int expensiveBook = (*it)->second;

        if (lavanya < nikhil)
        {
            lavanya += expensiveBook;
            nikhil += cheapBook;
        }
        else
        {
            nikhil += expensiveBook;
            lavanya += cheapBook;
        }
    }

    cout << abs(lavanya - nikhil) << endl;
}

int main(int argc, char* argv[])
{
    BookList books;

    readBookList(books);
    sort(books.begin(), books.end(), diffsort);
    allocate(books);

    return 0;
}

Basically, you sort the pairs of books by the difference in price between them, largest difference first. (1, 3) would go before (300, 300). Then you allocate the books one pair at a time, giving the cheapest book to the child whose previous pile costs the most.

You sort by the difference instead of the absolute value of the book, because the difference is what you're trying to equalize. This avoids problems with sets such as (1, 201) (150, 300), (150,300). The fairest allocation is for one child to get both 300 rupee books and the 1 rupee book. This gives them only 100 more rupees than the other child.

If you sort instead by largest absolute value, each child will get one 300 rupee book, but one child will end up with 200 more rupees than the other child.

share|improve this answer
    
Ties should go to Lavanya, since it was her birthday after all :) –  Tacroy Oct 31 '12 at 17:50
    
would this work for 300, 5, 4, 3, 2, 1? I ask because the way you describe ("one pair at a time") it sounds like this will end with both kids owning 3 books each, while solution should be 300 and 15, 4, 3, 2, 1 –  gnat Oct 31 '12 at 18:10
    
Read the problem again, @gnat. One book from each of the pairs must go to each of the kids. –  Karl Bielefeldt Oct 31 '12 at 18:36
    
ah! now that makes perfect sense - thanks Karl –  gnat Oct 31 '12 at 22:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.