My solution (with extra diagnostic output added) gives:
Day: 1 out of 8 Good
Day: 2 out of 8 Good
Day: 3 out of 8 Good
Day: 4 out of 8 Not good - price is 431 on day 3 which is <= 629
Day: 5 out of 8 Not good - price is 431 on day 3 which is <= 611
Day: 6 out of 8 Good
Day: 7 out of 8 Not good - price is 412 on day 6 which is <= 420
Day: 8 out of 8 Good
5
I marked a price good if it is less than the minimum of the prices of the previous five days.
I am getting WA for this code. Is the algorithm wrong?
Thanks
Here’s my code below:
#include <iostream>
using namespace std;
int main() {
// your code goes here
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int arr[n];
for(int i=0;i<n;++i)
cin >> arr[i];
int min = arr[0];
int cnt=1;
for(int i=1;i<n;++i)
{
if(arr[i] < min)
{
cnt++;
min = arr[i];
continue;
}
if(i>=5)
{
int minm = arr[i-5];
for(int j=i-5;j<i;++j)
{
if(arr[j] < minm)
minm = arr[j];
}
min = minm;
}
}
cout << cnt << endl;
}
return 0;
}
On my machine, it gives the wrong answer for the following testcase:
1
8
489 377 605 548 741 625 682 420
The answer should be 3:
Day: 1 out of 8 Good
Day: 2 out of 8 Good
Day: 3 out of 8 Not good - price is 377 on day 2 which is >= 605
Day: 4 out of 8 Not good - price is 377 on day 2 which is >= 548
Day: 5 out of 8 Not good - price is 548 on day 4 which is >= 741
Day: 6 out of 8 Not good - price is 548 on day 4 which is >= 625
Day: 7 out of 8 Not good - price is 625 on day 6 which is >= 682
Day: 8 out of 8 Good
3
@ssjgz thank you for explanation, my logic was correct but i had done a mistake when sorting vector in “ist” function. This is my solution, plz review it.
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
StringBuilder sb=new StringBuilder();
while(t–>0)
{
int n=Integer.parseInt(br.readLine());
String in[]=new String[n];
in=br.readLine().split(" “);
int c=0;
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=Integer.parseInt(in[i]);
int m=Integer.MAX_VALUE;
for(int j=i-1;j>=Math.max(0,i-5);j–)
{
if(arr[j]<m)
m=arr[j];
}
if(arr[i]<m)
c++;
}
sb.append(c+”\n");
}
System.out.print(sb);
}
}
This code is getting accepted but for the following test input, the ans should be 2 ,but this code is giving 3 as ans. How come this code is getting accepted?
input-
1
7
375 300 900 723 662 647 200
o/p = 3 which is wrong, but still this code is getting accepted. Why?