SPOJ: DCOWS Why a Greedy algorithm does not work?

Question

Question Link: https://www.spoj.com/problems/DCOWS/

I am trying to figure out why my greedy approach to solve the above problem does not work.

Given two lists B & C with corresponding sizes of N & M with (M > N), consisting of heights of bulls and cows respectively as inputs to this question, my approach to solve this problem is as follows:

• Sort both lists B & C in non-decreasing order
• Set k = 0
• For each item B_i in list B
  • Using modified binary search on C[k..M-N+i] find an element C_j at position j, 0<=j<=M-N in list C which has the minimum absolute difference with B_i
  • Add abs(B_i - C_j) to the result
  • Update k = j + 1 for next iteration of the loop

Here is the code:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int my_bsearch(long *arr, int lo, int hi, long x)
{
    int mid = lo + (hi - lo)/2;
    if (lo == mid)
    {
        if (abs(x - arr[lo]) <= abs(x - arr[hi])) return lo;
        else                  return hi;
    }

    if ((mid-1 >= 0) && (abs(x - arr[mid-1]) <= abs(x - arr[mid])))
        return my_bsearch(arr, lo, mid, x);
    else
        return my_bsearch(arr, mid, hi, x);
}

int main() {
    int M, N;
    cin >> N >> M;

    long bulls[N], cows[M];
    for (int i=0; i<N; i++) cin >> bulls[i];
    for (int i=0; i<M; i++) cin >> cows[i];

    sort(bulls, bulls + N);
    sort(cows, cows + M);

    long long min_val = 0, lo = 0, hi = M-N;
    for (int i=0; i<N; i++) {
        lo = my_bsearch(cows, lo, hi, bulls[i]);
        min_val += abs(bulls[i] - cows[lo]);
        lo++, hi++;
    }
    cout<< min_val << endl;

    return 0;
} 

Answer 1

As described in this similar question Can we solve the “printing neatly” problem using a greedy algorithm, a greedy solution is often led astray. Consider this data:

Bulls: 5, 5

Cows: 1, 6, 15

Your algorithm outputs minimum distance of 11 (pairs 5 to 6, and then 5 to 15). But the optimal solution is clearly 5 (pairing 5 to 1, and 5 to 6).