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.
