Ufff.... Getting Wrong Answer !!!

[Maggi Iggam]

Here's the question :-

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.
Input format
The first line of the input contains a single integer N indicating the number of stations. The next N lines (lines 2, 3, ..., N+1) describe the profitability of the N stations. Line i+1 contains a single integer denoting the expected profit at station i.
Output format
The first line contains a single integer indicating the minimum possible profit/loss among all segments. The second line contains two integers indicating the starting and ending point of the longest sequence with this minimum profit/loss. If there is more than one answer, it suffices to print one.
Test Data:
You may assume N ≤ 100000. You may further assume that in 40% of the inputs N ≤ 4000.
Example:
Here is the sample input and output corresponding to the example discussed above.
Sample Input
8
-20
90
-30
-20
80
-70
-60
125
Sample Output
-5
6 8

Here's my solution for it :-

#include<iostream>
#include <stdlib.h>
using namespace std;
int main() {
    int i,j,n,list[1000],mp=100000,tp,ll,ul,tc;
    cin>>n;
    for (i=0;i<n;i++) cin>>list[i];
    for (i=0;i<n-1;i++) {
        tc=list[i];
        if (abs(tc)<abs(mp)) {mp=tc;ll=i;ul=i;}
        for (j=i+1;j<n;j++) {
            tc+=list[j];
            if (abs(tc)<abs(mp)) {mp=tc;ll=i;ul=j;}
        }
    }
    cout<<mp<<endl<<ll+1<<" "<<ul+1;
}

It gives me "Correct answer" for 3 test cases but gives me "Wrong Answer" for rest of the 7 test cases ! I can't find sample output that gives me wrong,unexpected output , can anyone provide such test data or tell me debug in my code ???

[ne555]

¿Why you don't respect the limits?

If there is more than one sequence with this minimum absolute value then he would like to hand over the longest one.

You never check that.

TLE

[Maggi Iggam]

Yeah , you were correct there , now i am checking the longest chain too , but now its giving just 2 test cases as "Correct Answer" while rest 8 as "Wrong Answer" , here's the edited code , can you please find any mistake or any test case where it gives wrong answer ???

#include<iostream>
#include <stdlib.h>
using namespace std;
int main() {
    int i,j,n,list[1000],mp=1000000,tp,ll,ul,tc;
    cin>>n;
    for (i=0;i<n;i++) cin>>list[i];
    for (i=0;i<n-1;i++) {
        tc=list[i];
        if (abs(tc)<abs(mp)) {mp=tc;ll=i;ul=i;}
        if (abs(tc)==abs(mp) && ((ul-ll)<(j-i))) {ll=i;ul=i;}
        for (j=i+1;j<n;j++) {
            tc+=list[j];
            if (abs(tc)<abs(mp)) {mp=tc;ll=i;ul=j;}
            if (abs(tc)==abs(mp) && ((ul-ll)<(j-i))) {ll=i;ul=i;}
        }
    }
    cout<<mp<<endl<<ll+1<<" "<<ul+1;
}

[coder777]

So you abandon the previous exercise?

[Maggi Iggam]

I am not sure , about which exercise you are talking about ?
If it is about previous question (booklist) then i have done it , can you please give a more subtle hint ?

[coder777]

This http://www.cplusplus.com/forum/general/65565/#msg354340

[Maggi Iggam]

Oh , this one , yeah i have not actually abondoned it but postponed it , first i am thinking to do other easier exercises given .

[coder777]

To your problem: On line 10/11 you take single station into account. As far as i understand that's wrong. Remove those lines.

Better use more desciptive variables.

Line 15: You can put an else before that if. This {ll=i;ul=i;} needs to be {ll=i;ul=j;} // Note: ul=j instead of i

[Maggi Iggam]

Yeah , you correctly pointed that 'j' should come in place of 'i' on Line 15 .
But on Line 10/11 i was taking one station into account because j is always initialized as 'i+1' , thus if station i had minimum possible profit/loss than any other sequences , so it was necessary to check that i station every time .

Anyways , i corrected Line 15 and submitted but still getting Wrong Answer msg for 8 test case and also i tried removing Line 10/11 , but still it is giving the same .

And yes i would try to use more descreptive variables and comments :)

[coder777]

But on Line 10/11 i was taking one station into account because j is always initialized as 'i+1' , thus if station i had minimum possible profit/loss than any other sequences , so it was necessary to check that i station every time .

hm? No, these lines are definitely wrong.

Try this 2 -1 10 -1
Correct result: 1
1 2
Your result: 1
2 2
Without lines 10/11: 1
1 2

Currently i cannot find a scenario where your calculation goes wrong. But maybe the loss should prevail?

[ne555]

The thing is that we keep telling you this stuff over and over again.

¿Want to crash it? use n >= 1000
¿Want wrong answer? Put all stations with abs(value) > 1e6

Considering what coder777 says, if the station is just plain better then it becomes the start.
But it may be added to the chain and produce the same result (making a longer chain then)

[bluecoder]

code looks little more complicated .. is there any simple way of doing it ?
like bubble sort .. and saving the index .. or some thing like that .. as i look it is
same as bubble sort . .. here we do not swap the values but only store the least of it will the index (both ) .

[coder777]

Now I tested some more scenarios and I found the problem:

#include<iostream>
#include <stdlib.h>
using namespace std;
int main() {
    int i,j,n,list[1000],mp=1000000,tp,ll,ul,tc;
    cin>>n;
    for (i=0;i<n;i++) cin>>list[i];
    for (i=0;i<n-1;i++) {
        tc=list[i];
        for (j=i+1;j<n;j++) {
            tc+=list[j];
            if (abs(tc)<abs(mp)) {mp=tc;ll=i;ul=j;}
            if (abs(tc)==abs(mp) && ((ul-ll)<(j-i))) {mp=tc;ll=i;ul=j;} // You need to set the result here!
        }
    }
    cout<<mp<<endl<<ll+1<<" "<<ul+1;
}

EDIT: the list array must be 100000 (two more 0). Don't forget that

[Maggi Iggam]

Yeah @coder777 you correctly pointed that mp should have atleast 2 more 0s and also that i hadn't set the value at line 13.
Still i am getting only 20 points and msg "Wrong Answer".
I am not able to figure out more mistake other than u said .

Also @ne555 , you also correctly pointed that out , but i didn't understand what you meant by your last two lines -> (plain better) . Also where do you want me to use

n>=1000

???

@Bluecoer , umm... i believing using sort and indexing , maybe we will be more faster but code will become more complicated as we require to find least possible value of contagious segment , ie continuos segment . So finding all possible station's profit/loss and taking least magnitudly should be far easier ( & far less complicated as far as i understand).

[coder777]

Maggi Iggam wrote:

that mp should have atleast 2 more 0s

Nope

I wrote:

the list array must be 100000 (two more 0)

[Maggi Iggam]

Oh ! :D