Search code examples
c++algorithmtestcase

I need a Test Case to prove my algorithm/code wrong

I am making a program which finds the maximum-length subarray whose sum is closest to 0. Actually i was trying to solve this question: http://opc.iarcs.org.in/index.php/problems/DEVIOUS , but when i submit my code, it gives correct answer to only 50% of test cases. My code is working fine, and even giving correct answer for my own test cases, so i need a test case to prove my code/algorithm wrong, so that i can find the mistake in my code.

This is my algorithm,

  1. Create an array 'temp' equal to the size of the input array, initialize all the elements of temp such that, temp[i] = sum of all elements up to input[i]
  2. Sort the array temp, find 'i' in temp such that temp[i-1] - temp[i] is closest to 0

Here is my code to solve the problem from the link above.

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <limits.h>

using namespace std;

struct element{
    int index;
    int value;
};

bool compare(element a, element b){
    return a.value < b.value;
}

int main(){
    int n;
    cin >> n;
    int array [n];
    element elements[n];
    int sum = 0;

    for(int i = 0 ;i < n; i ++){
        cin >> array[i];
        sum = sum + array[i];
        elements[i].index = i;
        elements[i].value = sum;
    }

    sort(elements,elements+n,compare);

    int diff = INT_MAX;
    int i1 = 0,i2 = 0;
    for(int i = 1;i < n;i ++){
        int temp = elements[i].value - elements[i-1].value;
        if(temp < diff){
            diff = temp;
            i1 = elements[i].index;
            i2 = elements[i-1].index;
        }
        else if(temp == diff){
            if(abs(elements[i].index - elements[i-1].index) > abs(i1-i2)){
                i1 = elements[i].index;
            i2 = elements[i-1].index;
            }
        }
    }

    diff = 0;
    int s,e;
    if(i1 >= i2){
        e = i1, s = i2+1;
    }else{
        s = i1+1, e = i2;
    }

    for(int i = s;i <= e ; i++){
        diff = diff+array[i];
    }
    cout << diff << endl;

    cout << s+1 << " " << e+1;

    return 0;
}

EDIT: I found a mistake in my code and edited it, it now gives correct answer for 80% of the inputs

Solution

  • In other words, if the profits/losses at the stations are p1, p2, ..., pN the minister would like to handover a sequence i, i+1, ..., j such that the absolute value of pi + pi+1 + ... + pj is minimized. If there is more than one sequence with this minimum absolute value then he would like to hand over the longest one

    I think your algorithm is slightly wrong:

    temp[i] = sum of all elements up to input[i] Sort the array temp

    The start of the sequence may well be another position than the start of the array - it can be a sub-sequence don't forget.

    -1 | -2 | 10 | 5 |-10 | 6

   |    |    | x | x  | x

    edit2: Removed wrong explanation now I looked at the code - 

    if(temp < diff){
        diff = temp;
        i1 = elements[i].index;
        i2 = elements[i-1].index;
    }

    You do have a preference for -ve numbers (loss). Could it be that the misses are where there is a nearer number to zero because it is either slightly less -ve or +ve (but where the abs value is smaller)?