10684 - The jackpot

[_.B._]

Greetings!
I thought this problem was not supposed to be a tough one, but I'm getting a hard time to get it ACed.
Please, what's the right output for this input?:

Code: Select all

4
0 0 0 0
4
0 0 0 -1
6
12 -4 -10 4 4 9
6
12 -4 -10 4 0 9
5
4 9 -10 -4 12
0

Hopefuly it'll help me understand the meaning of the "Streak".
Thanks in advance!

[sohel]

I get the following output for your input:

Losing streak.
Losing streak.
The maximum winning streak is 17.
The maximum winning streak is 13.
The maximum winning streak is 13.

Hope it helps.

[Maniac]

a streak in this problem is a continuous subsequence of the given sequence of numbers.

[_.B._]

Greetings!
Sohel, thanks once again. Thanks Maniac.
I'm still getting WA
Some problems make me feel like Manzoor... some others make me feel so ignorant.

Keep posting!

[anupam]

My algo is as following:
let pre=previous profit.
max=maximum profit
then for a single input number a
if pre+a>0 pre=pre+a;
else pre=0;
if(pre+a>max) max=pre+a;

print just max.
I think this will help you getting wrong part of your algorithm and any two for loop system will get Tle (i think). So use )(n) solution.

[_.B._]

Greetings!
Well, don't FLAME me for this but... I forgot to print the '.' after the Maximun
Anyway, Anupam, thanks a lot for the algo, I re-estructured mine.
Thanks to all!, and keep posting!

Best regards.

[anupam]

You are not the one who forget to put '.', many times I forget such characters. That is why now, I just copy the output from the sample output of the problem and then replace if necessary.
Good luck:-)

[yiuyuho]

hey anupam,

so the problem comes down to MCSS, but I though the problem states :
he can identify patterns of consecutive wins and elaborate a win-win strategy.
A bet is an amount of money and is either winning (and this is recorded as a positive value).

So shouldn't consecutive wins be a continuous subsequence of "positive" subsequence rather then just a subsequence?

[anupam]

Yeah, I also think so. It is a positive subsequence for win conds.

[yiuyuho]

so the judge data is incorrect!

because
3
10 -1 10

will produce 19 with MCSS algorithm (AC), but consecutive positive values should just give 10 (Result according to problem wording).

[anupam]

O O, I think I failed to understand what you were talking about.

>>he can identify patterns of consecutive wins and elaborate a win-win strategy. A bet is an amount of money and is either winning (and this is recorded as a positive value). So shouldn't consecutive wins be a continuous subsequence of "positive" subsequence rather then just a subsequence?<<
consecutive wins doesn't mean consecutive sequence, I may not be correct. as in your example,
10 -1 10
The first win is when you got 10.
then you lose -1
and again got 10 so, now you won total 19.
So, there are two win situations(not consecutive) and 1 fail situation. I think, judge had the same thought in mind.

[shu]

hmm.. i don't understand. I think there's an invalid statement in this problem.

Each bet is an integer greater than 0 and less than 1000.

which means 0 < bet < 1000, right?

but i got WA because of this one...

Code: Select all

if ( result < 0 ) puts( "Losing streak." );

and i got AC when..

Code: Select all

if ( result <= 0 ) puts( "Losing streak." );

could anyone explain to me how to get maximum result = 0 without any single 0 bet

[Martin Macko]

hmm.. i don't understand. I think there's an invalid statement in this problem.

Each bet is an integer greater than 0 and less than 1000.

which means 0 < bet < 1000, right?

but i got WA because of this one...

Code: Select all

if ( result < 0 ) puts( "Losing streak." );

and i got AC when..

Code: Select all

if ( result <= 0 ) puts( "Losing streak." );

could anyone explain to me how to get maximum result = 0 without any single 0 bet

What does result mean in your solution? Have you initialised it properly?

[shu]

result is a variable containing the maximum-streak from each testcase. Ofcourse I have it initialized properly.

In the problem description, we can found that there will be NO 0 (zero) bet in each input-set, only negative or positive value will exists. Do we agree with this? If so, I think it's clear that it is impossible to get 0 (zero) maximum-streak from that condition.

My WA code went wrong because there're exists input-set such maximum-streak is 0. The only explanation I could think is there're 0 (zero) bets.

I have checked the judge-input, and I found 0 bet there.

[yoyakazuma]

Code: Select all

#include<iostream> 
using namespace std;

int main(){
    int check[10005][10005],money[10005],a,b,n;
    while(cin >> n){
       if(n==0) break;
       int sum=0;
       for(a=0;a<n;a++){
          cin >> money[a];
          check[a][a]=money[a];
          if(check[a][a]>sum)
             sum=check[a][a];
       }
       for(a=0;a<n-1;a++){
          for(b=a+1;b<n;b++){
             check[a][b]=check[a][b-1]+money[b];
             if(check[a][b]>sum) 
                sum=check[a][b];
          }
       }
       if(sum<=0)
          cout << "Losing streak." << endl;
       else
          cout << "The maximum winning streak is " << sum << "." << endl;
    }
    return 0;
}

why??
I can't find any problem...