EQGIFTS - Editorial

editorial
1

Prerequisite :- Dynamic Programming,Recursion.

Problem :- Given N pairs of books, The problem is about dividing pairs of books between Lavanya and Nikhil so that the difference in the total value of books assigned to them is minimized. Each pair of books has a cost, and Lavanya’s father needs to distribute them in a way that the total value of books for Lavanya is as close as possible to that of Nikhil. The task is to find the smallest possible difference between the total values assigned to Lavanya and Nikhil.

Explanation : -

Recursive approach to all possible combinations of assigning books to Lavanya and Nikhil.
At each step of the recursion, consider two choices: assigning the current book pair to Lavanya or to Nikhil.
By recursively exploring these choices for each book pair, the solution aims to find the combination that minimizes the difference in total book values assigned to Lavanya and Nikhil.

Memoization (Dynamic Programming):
To optimize the recursive approach, the solution uses memoization.
Memoization helps avoid redundant calculations by storing the results of already computed subproblems.
By storing these results in a table, the solution can quickly retrieve them when needed during the recursion, reducing the overall time complexity.

Base Case:
The recursion terminates when all book pairs have been considered.
At this point, the solution calculates the difference in total book values assigned to Lavanya and Nikhil and returns it as the result.

Choosing the Minimum:

  • During the recursion, consider two options for each book pair: assigning it to Lavanya or to Nikhil.
  • Choose the option that results in the minimum difference in total book values between Lavanya and Nikhil.
  • This ensures that the final result represents the smallest possible difference in total book values assigned to Lavanya and Nikhil.

C++ Solution :-

#include <bits/stdc++.h>

using namespace std;

int solve(int pos, int sum, vector < vector < int >> & dp, vector < pair < int, int >> & v) {
  if (pos == v.size()) return sum;
  if (dp[pos][sum] != -1) return dp[pos][sum];
  int dif = v[pos].first - v[pos].second;
  dif = abs(dif);
  int fans = INT_MAX;
  fans = solve(pos + 1, dif + sum, dp, v);
  fans = min(solve(pos + 1, abs(dif - sum), dp, v), fans);
  return dp[pos][sum] = fans;
}
int main() {
  // your code goes here
  vector < pair < int, int >> v;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int n1, n2;
    cin >> n1 >> n2;
    v.push_back({
      n1,
      n2
    });
  }
  vector < vector < int >> dp(n, vector < int > (n * 300 + 1, -1));
  cout << solve(0, 0, dp, v);

}
2

There is another dynamic programming solution:

Idea:
Let x be the total cost of books Lavanya got and let T be the cost of all books.
Then Nikhil must have the total cost of book he get to be T-x.
So the difference is |T-2x|.
Note: x is only valid when atleast one of the arrays formed by the pair has the sum x.
We can use Dynamic Programming to find all the valid x
Let dp[i][j] tell us if there is any arrays formed by the first i pairs sums to j.
Base Case: dp[0][0] = true
Let a, b be the elements of i'th pair.
If both a and b are greater than j,
dp[i][j] = false.
If a is greater than j,
dp[i][j] = dp[i-1][j-b].
If b is greater than j,
dp[i][j] = dp[i-1][j-a].
otherwise,
dp[i][j] = dp[i-1][j-b] | dp[i-1][j-a].
Note: ‘|’ operator means or operator.
Time complexity = O(NT)

n = int(input())
p = []
t = 0
for _ in range(n):
    x, y = map(int, input().split())
    p.append((x, y))
    t += x+y
dp = [[False]*(t+1) for _ in range(n+1)]
dp[0][0] = True
for i in range(1, n+1):
    a, b = p[i-1]
    for j in range(1, t+1):
        if a > j and b > j:
            continue
        if a > j:
            dp[i][j] = dp[i-1][j-b]
        elif b > j:
            dp[i][j] = dp[i-1][j-a]
        else:
            dp[i][j] = dp[i-1][j-a] or dp[i-1][j-b]
ans = float("inf")
for i in range(t+1):
    if dp[n][i]:
        ans = min(ans, abs(t-2*i))
print(ans)
4

Its ok if any one is C++ User. Use this code.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int t = 0;
    vector<pair<int, int>> p;
    for (int i=0; i<n; i++){
        int x, y;
        cin>>x>>y;
        t += x + y;
        p.push_back(make_pair(x, y));
    }
    vector<vector<int>> dp(n+1, vector<int>(t+1, 0));
    dp[0][0] = 1;
    for (int i=1; i<n+1; i++){
        int a = p[i-1].first, b = p[i-1].second;
        for (int j=1; j<t+1; j++){
            if (a > j && b > j) continue;
            if (a > j){
               dp[i][j] = dp[i-1][j-b]; 
            }else if (b > j){
               dp[i][j] = dp[i-1][j-a]; 
            }else{
               dp[i][j] = dp[i-1][j-a] || dp[i-1][j-b];
            }
        }
    }
    int ans = INT_MAX;
    for(int i=0; i<t+1; i++){
        if (dp[n][i]) ans = min(ans, abs(t- 2*i ));
    }
    cout << ans;
}
5

Space optimization - O(NT) to O(T)

n = int(input())
p = []
t = 0
for _ in range(n):
    x, y = map(int, input().split())
    p.append((x, y))
    t += x+y
prev = [False]*(t+1)
prev[0] = True
for i in range(1, n+1):
    curr = [False]*(t+1)
    a, b = p[i-1]
    for j in range(1, t+1):
        if a > j and b > j:
            continue
        if a > j:
            curr[j] = prev[j-b]
        elif b > j:
            curr[j] = prev[j-a]
        else:
            curr[j] = prev[j-a] or prev[j-b]
    prev = curr
ans = float("inf")
for i in range(t+1):
    if prev[i]:
        ans = min(ans, abs(t-2*i))
print(ans)
6

C++ code with space optimization:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int t = 0;
    vector<pair<int, int>> p;
    for (int i=0; i<n; i++){
        int x, y;
        cin>>x>>y;
        t += x + y;
        p.push_back(make_pair(x, y));
    }
    vector<int> prev(t+1, 0);
    prev[0] = 1;
    for (int i=1; i<n+1; i++){
        int a = p[i-1].first, b = p[i-1].second;
        vector<int> curr(t+1, 0);
        for (int j=1; j<t+1; j++){
            if (a > j && b > j) continue;
            if (a > j){
               curr[j] = prev[j-b]; 
            }else if (b > j){
               curr[j] = prev[j-a]; 
            }else{
               curr[j] = prev[j-a] || prev[j-b];
            }
        }
        prev = curr;
    }
    int ans = INT_MAX;
    for(int i=0; i<t+1; i++){
        if (prev[i]) ans = min(ans, abs(t- 2*i ));
    }
    cout << ans;
}
7

The key to the space optimization is:
dp_i = curr
dp_{i-1} = prev