Where is my solution to kickstart 2020 problem record breaker wrong? if you all can provide some test cases?

general
1

import java.util.;
import java.io.;
import java.lang.*;
class Solution
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t,n,i,max,curr,prev,count,j;
t=sc.nextInt();
j=t;
while(t>0)
{
n=sc.nextInt();
max=count=0;
prev=sc.nextInt();
for(i=0;i<n-1;i++)
{
curr=sc.nextInt();
if(prev>max)
{
max=prev;
if(curr<prev)
count++;
}
prev=curr;
}
if(prev>max)
count++;
System.out.println(String.format(“Case #%d: %d”, (j-t+1), count));
t–;
}
}
}

2

Solve it by dp.
dp(i,j) i is index, j is last taken alphabet.

3

Just do what the problem statement says.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i)
    {
        int n;
        cin >> n;
        vector <int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        int m = -1, ans = 0;
        for (int i = 0; i < n-1; ++i)
        {
            if (a[i] > m)
            {
                m = a[i];
                if (a[i] > a[i+1]) ++ans;
            }
        }
        if (a[n-1] > m) ++ans;
        cout << "Case #" << i << ": " << ans << '\n';
    }
}

No need of DP. From the 1st to second last numbers, just check if the current number is greater than the max number till there and if it’s greater than the next number. And then manually check if the max number till the last number is less than it.

1 Like
4

i did the same implementation as you have done and got the sample test case correct as well don’t know why i got WA. still thanks.

5

My bad. This is for 2nd problem.

6

Make sure it gives 1 as output for n=1

1 Like
7

thanks n=1 and max intial value (should be less than 0)were causing the prblm .
just got accepted.

8

That can be solved without dp as well.
My approach.

1 Like
9

Try chaning initial value of max to -1 instead of zero. Read contraints carefully next time. Good luck :slight_smile:

1 Like
10

Can u explain the whole solution? I solved with greedy but not getting the dp approach

12

You should try initiating max with -1 or INT_MIN. do not put it’s value as 0 .
I was facing the same issue and at last I found that.

1 Like
13

Yes , its easy, dp not required.

14

you should check saperately if there is only one element