The problem here , requires me to find the best possible combination of values in an array which is nearest to 0 and are adjacent to each other , here is an little excerpt from it,

The government of Siruseri has just commissioned one of the longest and most modern railway routes in the world. This route runs the entire length of Siruseri and passes through many of the big cities and a large number of small towns and villages in Siruseri.

The railway stations along this route have all been constructed keeping in mind the comfort of the travellers. Every station has big parking lots, comfortable waiting rooms and plenty of space for eateries. The railway authorities would like to contract out the catering services of these eateries.

The Siruseri Economic Survey has done a through feasibility study of the different stations and documented the expected profits (or losses) for the eateries in all the railway stations on this route. The authorities would like to ensure that every station is catered to. To prevent caterers from bidding only for profitable stations, the authorities have decided to give out catering contracts for contiguous segments of stations.

The minister in charge realises that one of the bidders is his bitter adversary and he has decided to hand out as useless a segment as possible to him. On the other hand, he does not want to be seen to be blatantly unfair by handing out a large loss-making section to the adversary. Instead he wants to find the largest segment whose sum is closest to 0, so that his adversary spends all his time running a large number of canteens and makes either a small loss or a small profit or, even better, nothing at all!

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.

For example, suppose there are 8 stations along the line and their profitability is as follows:

Station 1 2 3 4 5 6 7 8
Expected Profits -20 90 -30 -20 80 -70 -60 125

If the adversary is awarded the section 1 through 4, he will make a net profit of 20. On the other hand if he is given stations 6, 7 and 8, he will make loss of 5 rupees. This is the best possible value.

My first approach was to make an 2d array and calculate the sums by , first adding up the number adjacent to current index the use that to add with the next adjacent number and calculate the whole matrix which eventually can give me the number nearest to 0 and their position , but due to huge number of stations , the code gave runtime errors.

Hence changed to a simple solution where you dont have to save each and every result and also break the loop when the output is the minimum possible value that is 0.

The code ran fine with a couple of time limit exceeded cases , but the most astonishing fact is it landed up with 4 wrong answers , the TLE's were expected but wrong answers? I then tested against the test cases , yes couple of them takes a lot of time about 5-6s , but no wrong answers (the set of vertices were different but the question says I can print any set of vertices given the output is minimum) , so probably its a bug in the server.

Here is my code:

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

int main(){
    int n;
    std::ios_base::sync_with_stdio(false);
    std::cin>>n;
    std::vector<int>profit(n);
    for(int i=0;i<n;i++){
        std::cin >> profit[i];
    }

    int min = INT_MAX ;
    int sVertex,eVertex;
    for(int i=1;i<n;i++){
        int prevCost = profit[i] + profit[i-1];
        if(std::abs(prevCost) < std::abs(min)){
            min = prevCost;
            sVertex = i;
            eVertex = i;
        }
        for(int j=i+1;j<n;j++){
            int prof = prevCost + profit[j];
            if(std::abs(prof) < std::abs(min)){
                min = prof;
                sVertex = i;
                eVertex = j;
                if(min == 0){
                    std::cout << min << std::endl;
                    std::cout << sVertex << " " << eVertex+1 << std::endl;
                    return 0;
                }
            }
            prevCost = prof;
        }
    }

    std::cout << min << std::endl;
    std::cout << sVertex << " " << eVertex+1 << std::endl;

    return 0;
}

Anyone having a better approach for this problem?

Here are the testcases.

  • You should have a look at std::deque, which is highly efficient for such tasks. – miscco Oct 18 '16 at 14:56
  • how? can you explain it a bit? – hellozee Oct 18 '16 at 15:05
  • 1
    "the question says I can print any set of vertices" - no, it says to print the longest. – vnp Oct 18 '16 at 18:29
  • std::deque has the advantage, that you can efficiently add elements both at the start as well as at the end. Therefore, it is really nice for stuff that requires subslices of vectors. – miscco Oct 18 '16 at 18:56
  • @vnp ohh I have mistaken that for any pair , my fault should pay a little more concentration – hellozee Oct 19 '16 at 8:49
up vote 3 down vote accepted
+50

Bug #1

The main bug that is probably causing your incorrect answers is due to your misreading of the problem. The problem says that if two or more segments have the same score, then you need to return the longest segment. Then, if there are multiple segments of the same score and length, you can return any of these segments.

Currently, your code only finds the first segment with the lowest score. You could trivially modify your program to also record the best segment length and use it as a tiebreaker when you find a new segment of the same score.

Possible Bug #2

Depending on the problem intention, it could be a bug that your program does not consider segments of length 0 (i.e. a segment containing just one station). Your program currently only considers segments with a minimum of 2 stations. Thus, given the input 1 2 3 4 5, your program would find the segment 1 2 instead of the segment 1 1. Of course, if 0 length segments are not allowed, then your program is fine.

Possible Bug #3

Depending on the input, you may be overflowing your integer variables when you do things like:

int prof = prevCost + profit[j];

If this addition overflows past MAX_INT, then prof will turn negative when it actually should be a large positive value. For example, if prevCost and profit[j] were both 0x7fffffff, then the addition will result in the value 0xfffffffe which should be over 4 billion, but when treated as a signed int is -2.

Better algorithm

@PeterTaylor already demonstrated an \$O(n \log n)\$ solution that is probably the simplest to understand. I had come up with another \$O(n \log n)\$ algorithm that works in a similar way. Both are based on the fact that \$S(j) - S(i)\$ gives you the profit of a segment.

  1. Create a std::map, which will use running sums (sum[i]) as keys and indices (i) as values. Note that std::map has guaranteed logarithmic insertion and find time, because it uses some form of a a balanced binary tree implementation.
  2. Loop i from 0..n, keeping a running sum of profit[0..i].
  3. Search the map for the closest match to the current sum. If this closest match is better than the previous best match (by both score and by segment length), then record it as the new best match.
  4. If sum does not exist in the map, insert it. If it already exists, do not insert it because the earlier index with the same sum will give a longer segment so we can throw away the current index. Then go back to step #2.

Sample implementation using std::map

#include <iostream>
#include <cmath>
#include <climits>
#include <map>

int main()
{
    int n;
    std::ios_base::sync_with_stdio(false);
    std::map<int, int> sumMap;
    int sum       = 0;
    int bestScore = INT_MAX;
    int bestLen   = 0;
    int bestStart = 0;
    int bestEnd   = 0;

    std::cin >> n;

    // Need to add a sum of 0 with index -1 so that we can find sequences
    // starting at the first station.
    sumMap[0] = -1;

    for (int i=0;i<n;i++) {
        bool alreadyExists = false;
        int  profit;
        std::map<int, int>::iterator it;

        // Maintain running sum of profit[0..i]
        std::cin >> profit;
        sum += profit;

        // Search map for closest match to sum.  Need to search twice.
        for (int loop = 0; loop < 2; loop++) {
            if (loop == 0) {
                // On the first loop, find the closest match >= sum, if
                // there is one.  Use lower_bound() to find this.
                it = sumMap.lower_bound(sum);
                if (it == sumMap.end())
                    continue;
            } else {
                // On the second loop, find the closest match < sum.  We can
                // find this by just decrementing the previous lower_bound.
                if (it == sumMap.begin())
                    break;
                it--;
            }
            // Replace the best match if this match is better.
            int prevSum = it->first;
            int score   = std::abs(sum - prevSum);
            int len     = i - it->second;
            if (score < bestScore || (score == bestScore && len > bestLen)) {
                bestScore = score;
                bestLen   = len;
                bestStart = it->second;
                bestEnd   = i;
            }
            if (score == 0)
                alreadyExists = true;
        }
        // Add sum to map, if it doesn't already exist.
        if (!alreadyExists)
            sumMap[sum] = i;
    }
    std::cout << bestScore << std::endl;
    std::cout << bestStart+2 << " " << bestEnd+1 << std::endl;

    return 0;
}

Sample implementation using sort

Out of curiosity, I wrote a solution using @PeterTaylor's algorithm that used a sort. You can decide whether you think this one is easier to understand than the one using a map. There is one tricky part here where if there are multiple answers all with score 0, you need to handle that specially in order to find the longest segment with score 0.

#include <iostream>
#include <cmath>
#include <climits>
#include <vector>
#include <algorithm>

int main()
{
    int n;
    std::ios_base::sync_with_stdio(false);
    std::vector<std::pair<int, int> > sums;
    int sum       = 0;
    int bestScore = INT_MAX;
    int bestLen   = 0;
    int bestStart = 0;
    int bestEnd   = 0;
    std::pair<int, int> sumPair;

    std::cin >> n;

    // Need to add a sum of 0 with index -1 so that we can find sequences
    // starting at the first station.
    sumPair.first  = 0;
    sumPair.second = -1;
    sums.push_back(sumPair);

    // Create vector of sums.
    for (int i=0;i<n;i++) {
        int profit;
        std::cin >> profit;
        sum += profit;
        sumPair.first  = sum;
        sumPair.second = i;
        sums.push_back(sumPair);
    }

    // Sort vector by sum, then by element index.
    std::sort(sums.begin(), sums.end());

    // Iterate through vector looking for smallest sum distance between
    // adjacent entries.  There is a special case for distance 0 where we
    // need to find the max length segment.
    std::vector<std::pair<int, int> >::iterator it = sums.begin();
    int prevSum   = it->first;
    int prevIndex = it->second;
    for (it++; it != sums.end(); it++) {
        int sum   = it->first;
        int index = it->second;
        int score = std::abs(sum - prevSum);
        int len   = std::abs(index - prevIndex);
        if (score < bestScore || (score == bestScore && len > bestLen)) {
            bestScore = score;
            bestLen   = len;
            bestStart = prevIndex;
            bestEnd   = index;
        }
        if (score != 0)
            prevIndex = index;
        prevSum   = sum;
    }
    // Swap start and end if necessary.
    if (bestStart > bestEnd) {
        int tmp   = bestStart;
        bestStart = bestEnd;
        bestEnd   = tmp;
    }
    std::cout << bestScore << std::endl;
    std::cout << bestStart+2 << " " << bestEnd+1 << std::endl;

    return 0;
}

Defeating the bug(s) in the server

After examining the input and output files used by the server, I have come to the following conclusions:

  1. The server uses 32-bit integers and does not account for overflow. That is to say, some of the input files create segments with sums that overflow a 32-bit integer. But if you correctly solve the problem using 64-bit integers, the correct answers are marked wrong by the server. So you are expected to overflow your 32-bit integers and get the wrong answer.

  2. After accounting for the 32-bit issue, the server clearly has the wrong answer for input sets 1 and 8. For input set 1, you can find the answer of 6 18 19 by visual inspection, because the segment between stations 18 and 19 adds up to 6. The server expects the answer -48 6 8. Input set 8 should have answer 1 39396 47087 but the server expects answer -3 1021 21224.

My guess is that whoever "solved" the problem to create the "correct answers" used a buggy program to do it. The trick now is to recreate the same bug to get the same "correct" answers. I was able to submit a program that passed all tests by adding some code to the map implementation.

As you recall, the map implementation first checks the map for a sum >= target, then checks the map for a sum < target. The first check essentially finds a zero or negative profit answer. The second check finds a positive profit answer. Since the two mistaken answers both missed a correct positive profit answer, I put in some code that sometimes causes the second check to be skipped. This seemed to make the code match the buggy program code. Here is my submission that was accepted:

#include <iostream>
#include <cmath>
#include <climits>
#include <map>

int main()
{
    int n;
    // std::ios_base::sync_with_stdio(false);
    std::map<int, int> sumMap;
    int sum       = 0;
    int bestScore = INT_MAX;
    int bestDiff  = INT_MAX;
    int bestLen   = 0;
    int bestStart = 0;
    int bestEnd   = 0;

    std::cin >> n;

    // Need to add a sum of 0 with index -1 so that we can find sequences
    // starting at the first station.
    sumMap[0] = -1;

    for (int i=0;i<n;i++) {
        bool alreadyExists = false;
        int  profit;
        std::map<int, int>::iterator it;

        // Maintain running sum of profit[0..i]
        std::cin >> profit;
        sum += profit;

        // Search map for closest match to sum.  Need to search twice.
        for (int loop = 0; loop < 2; loop++) {
            if (loop == 0) {
                // On the first loop, find the closest match >= sum, if
                // there is one.  Use lower_bound() to find this.
                it = sumMap.lower_bound(sum);
                if (it == sumMap.end())
                    continue;
            } else {
                // On the second loop, find the closest match < sum.  We can
                // find this by just decrementing the previous lower_bound.
                if (it == sumMap.begin())
                    break;
                it--;
                // This block here is purely for the sake of skipping
                // a positive profit answer to match the server bug.
                {
                    int len = i - it->second;
                    if (len > 1 && len < bestLen)
                        break;
                }
            }
            // Replace the best match if this match is better.
            int prevSum = it->first;
            int score   = std::abs(sum - prevSum);
            int len     = i - it->second;
            if (score < bestScore || (score == bestScore && len > bestLen)) {
                bestScore = score;
                bestDiff  = sum - prevSum;
                bestLen   = len;
                bestStart = it->second;
                bestEnd   = i;
            }
            if (score == 0)
                alreadyExists = true;
        }
        // Add sum to map, if it doesn't already exist.
        if (!alreadyExists)
            sumMap[sum] = i;
    }
    std::cout << bestDiff << std::endl;
    std::cout << bestStart+2 << " " << bestEnd+1 << std::endl;

    return 0;
}
  • Thanks , I got the first bug , the second bug , yes it is there but the testcases dont have any answers like that, std::map , havent played with them but surely now will , and another note the algorithm solves the problem in time but the server is still saying wrong answers for about 4 testcases – hellozee Oct 21 '16 at 2:53
  • you can try the code , i have included the testcases – hellozee Oct 21 '16 at 2:54
  • @KuntalMajumder It could be bug #3 because my sample solutions used ints that could overflow. You could change those ints to long longs and see if that fixes the problem. – JS1 Oct 21 '16 at 5:46
  • umm nah this is still same , may be I misinterpreted the instructions ,here is the original one , you can take a look at it – hellozee Oct 21 '16 at 11:21
  • the brute force one takes too much time but it gets all the solution except one , which is probably a glitch in the test cases – hellozee Oct 21 '16 at 12:42

If there are \$n\$ stations then your approach takes \$O(n^2)\$ time. I can't see a \$O(n)\$ time algorithm, but there is a simple \$O(n \log n)\$ time one:

Define \$S(i) = p_1 + p_2 + \ldots + p_i\$. Then you're trying to find \$s\$ and \$e\$ to minimise \$|S(e) - S(s)|\$. If you sort the values of \$S(i)\$ in \$O(n \log n)\$ time, the minimum difference will be between two consecutive values, so you can do a linear scan to find it.

  • @Ext3h, thanks, the inconsistencies between stacks over MathJax is a pain in the neck and I lose track of which ones have it. FYI \ldots is preferable to .... – Peter Taylor Oct 20 '16 at 15:18
  • The problem feels similar to this one: codereview.stackexchange.com/q/52270/31562 . I'm pretty sure that a O(n) algorithm is possible. – Simon Forsberg Oct 20 '16 at 15:30
  • @SimonForsberg: Well it is a variation of the maximum subarray problem and should therefore be solvable in O(n) by Kadane's algorithm. – Nobody Oct 20 '16 at 15:49
  • @Nobody My thought exactly. I almost started on an answer but I think you can write one ;) – Simon Forsberg Oct 20 '16 at 15:51
  • 1
    @SimonForsberg: I overlooked the fact that this is about minimizing the absolute value and not the signed value. IMHO this breaks the key requirement of the algorithm that negative prefixes can be ignored which is not the case here as they might cancel out "more perfectly" with previous positive prefixes. @Peter: Assuming values that are finite we could use for example radix sort to push down the complexity to O(n). Maybe it is even possible for unbounded numbers as there is a finite set (at most n different) of them. – Nobody Oct 20 '16 at 18:20

So here would be my take for the code using two std::vectors. The idea is that the first vector simply stores the individual profits, whereas the second vector starts with all the profits of the 2 segment chains, aka [i, i+1]. We determine the minimum of that vector. Now in the next step we increase vector2 by element i+2. So now it holds all the segments of length 3 (obviously in every step the last element gets ignored). We continue until we reach the full segment.

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::ios_base::sync_with_stdio(false);
    size_t numStations;
    std::cin>>numStations;

    std::vector<int> profits;
    profits.reserve(numStations);        
    for (size_t station = 0; station < numStations; ++station) {
        int profit;
        std::cin >> profit;
        profits.push_back(profit);
    }

    /* Define the total maximum as the sum of the first pair rather than INT_MAX*/
    size totalMin = std::abs(profit[0] + profit[1]);
    std::pair<size_t, size_t> range = std::make_pair(0, 1);

    std::vector<int> profitSum = profits;
    for (unsigned segmentLength = 2; segmentLength < numStations; ++segmentLength) {
        /* Erase the last segment, as it cannot be enlarged */
        profitSum.pop_back();

        /* Define a starting value for this segment length */
        size_t currentMin = (profitSum[0] + profits[segmentLength-1]); 
        std::pair<size_t, size_t> currentRange = std::make_pair(0, segmentLength-1);

        /* Iterate over all segments of lenth segmentLength and get their sum */
        for (unsigned i = 0; i < profitSum.size(); ++i) {
            profitSum[i] += profits[i+segmentLength-1];

            /* Update if appropriate */
            if (std::abs(profitSum[i]) < currentMin) {
                currentMin = std::abs(profitSum[i]);
                currentRange = std::make_pair(i, i + segmentLength-1);
            }

            /* If 0 is reached we can immediately stop as we can choose any equal sum so take the first */
            if (currentMin == 0) {
                break;
            }
        } 

        /* Update if appropriate. Note that equalness leads to an update, as we search for the longest segment */
        if (currentMin <= totalMin) {
            totalMin = currentMin;
            range    = currentRange;
        }
    }

    /* I opted to go for an absolute minimum instead of calling std::abs every time in the comparison. This is up to you. Obviously this loop would then be superfluous */
    int result = 0;
    for (unsigned i = range.first; i <= range.second; ++i) {
        result += profit[i];
    }
    std::cout << result << "\n";
    std::cout << range.first << " " << range.second << "\n";
}
  • that is almost like my approach , and probably quadratic , also your code is full of typos (how ironical is this) , thanks for taking a look at it – hellozee Oct 21 '16 at 11:24
  • Yeah, i wrote it in the editor, feel free to edit. The quadratic runtime is due to the requirement that the longest segment has to be taken and cannot be optimized any further. Even if you start with the longest sequences, you can only stop at 0 – miscco Oct 21 '16 at 18:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.