What is wrong with the solution to this problem

Question

I am trying to solve: https://www.spoj.com/problems/ANARC05B/

I am using Binary Search to solve this problem. I think I have followed the correct approach. Can anybody help me with a test case that would fail?

Below is my code, it passes on the sample test cases, i dont see a problem with my code but still not sure why i get WA!! Please help!!

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

int BinarySearch(vector<int> arr, int key)
{
    int minNum = 0;
    int maxNum = arr.size() - 1;

    while (minNum <= maxNum)
    {
        int mid = (minNum + maxNum) / 2;
        if (key == arr[mid])
        {
            return mid;
        }
        else if (key < arr[mid])
        {
            maxNum = mid - 1;
        }
        else
        {
            minNum = mid + 1;
        }
    }
    return -1;
}

signed long Solve(vector<int> First, vector<int> Second)
{

    // Find the intersections in both the arrays and store the indices for them.
    vector<int> FirstInterIndices;
    vector<int> SecondInterIndices;
    for (int i = 0; i < Second.size(); i++)
    {
        int idx = BinarySearch(First, Second[i]);
        if (idx != -1)
        {
            SecondInterIndices.push_back(i);
            FirstInterIndices.push_back(idx);
        }
    }

    if (FirstInterIndices.empty())
    {
        FirstInterIndices.push_back(FirstInterIndices.size() - 1);
        SecondInterIndices.push_back(SecondInterIndices.size() - 1);
    }
    //Find Intersections ends

    //Calc the sum upto intersections in both the arrays and store them
    vector<signed long> FirstInterSum;
    vector<signed long> SecondInterSum;

    for (int i = 0; i < SecondInterIndices.size(); i++)
    {
        int k = 0;
        signed long Sum = 0;
        if (i > 0)
        {
            k = SecondInterIndices[i - 1] + 1;
        }
        for (; k <= SecondInterIndices[i]; k++)
        {
            Sum += (signed long)Second[k];
        }
        SecondInterSum.push_back(Sum);
    }
    signed long SumLeft = 0;
    if (SecondInterIndices.size() > 0)
    {
        for (int k = SecondInterIndices[SecondInterIndices.size() - 1] + 1; k < Second.size(); k++)
        {
            SumLeft += (signed long)Second[k];
        }
        SecondInterSum.push_back(SumLeft);
    }


    for (int i = 0; i < FirstInterIndices.size(); i++)
    {
        int k = 0;
        signed long Sum = 0;
        if (i > 0)
        {
            k = FirstInterIndices[i - 1] + 1;
        }
        for (; k <= FirstInterIndices[i]; k++)
        {
            Sum += (signed long)First[k];
        }
        FirstInterSum.push_back(Sum);
    }

    if (FirstInterIndices.size() > 0)
    {
        SumLeft = 0;
        for (int k = FirstInterIndices[FirstInterIndices.size() - 1] + 1; k < First.size(); k++)
        {
            SumLeft += (signed long)First[k];
        }
        FirstInterSum.push_back(SumLeft);
    }
    // Calc sum upto intersections ENDs

    // Compare corresponding elements (sum upto intersections) and add the max from First and Second
    signed long MaxSum = 0;
    int j = 0;
    for (; j < FirstInterSum.size(); j++)
    {
        if (j < SecondInterSum.size())
        {
            if (FirstInterSum[j] > SecondInterSum[j])
            {
                MaxSum += FirstInterSum[j];
            }
            else
            {
                MaxSum += SecondInterSum[j];
            }
        }
    }

    // If Any sum exists after last intersection add that as well.
    if (j < FirstInterSum.size())
    {
        MaxSum += FirstInterSum[FirstInterSum.size() - 1];
    }
    if (j < SecondInterSum.size())
    {
        MaxSum += SecondInterSum[SecondInterSum.size() - 1];
    }
    return MaxSum;
}

vector<int> getArray()
{
    vector<int> res;
    int n;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        res.push_back(x);
    }
    return res;
}

int main()
{
    for (;;)
    {
        vector<int> First = getArray();
        if (First.size() == 0)
            return 0;
        vector<int> Second = getArray();
        cout << Solve(First, Second);
    }
    return 0;
}

Answer 1

You get WA because the output format is incorrect. I ran your code, and the output looks like this:

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0450
2100
Program ended with exit code: 0

but the expected format should be:

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0
450
2100
Program ended with exit code: 0

difference is 0 and 450 are not on the same line.

Answer 2

But this problem does not require neither binary search nor dynamic programming (as it is marked at the site) and might be solved in linear time (the best possible)

Make two indices - for the first array and for the second one.

At every step move index that refers to smaller element (like in merge procedure of merge sort). When moving, calculate current sum (sum between intersection points).

When both indices point to equal values, you have found intersection point. Choose larger current sum from both arrays, add it and intersection item to result, reset sums to zero.

Pseudocode sketch

if a[ia] < b[ib]) 
   asum += a[ia++]
else 
  if a[ia] > b[ib]) 
      bsum += b[ib++]
  else
     result += max(asum, bsum) + a[ia]
     asum = bsum = 0
     ia++
     ib++