Wrong Answer in Cricket Tournament : RECCKT (RECursion Challenge-I)

general
, ,
1

I was doing a problem in Recursion Challenge - I. (problem link), and I comes up with an algorithm, but its not accepting my solution. Can someone please tell me where is the flaw.

Problem Description: You are given an array A of size N. You have to find the maximum fluctuation in the array.

Fluctuation = max (A[j]-A[i]) for all i,j satisfying 1 ≤ i < j ≤ N.

NOTE: fluctuation can be negative.

Constraints: 2 ≤ N ≤ 1000, 0 ≤ A[i] ≤ 10^9

My Algorithm (considering 1-based indexing)

function solve (N):
  max_difference = a[2]-a[1]
  smallest = a[1]
  for index in 2 to N:
    max_difference = max(max_difference, a[index]-smallest)
    if (max_difference < a[index]-a[index-1])
       max_difference = a[index]-a[index-1]
       smallest = a[index-1]
  return max_difference

Please help guys.

2

the mistake is in the line smallest=a[index-1]
instead it should be if(a[index]<smallest) smallest=a[index];

because the variable smallest holds the smallest value in array a from 1 to index.

You can also check my code http://www.codechef.com/viewsolution/6002802

3

But in that if block, I am calculating new max_difference according to that value i.e. a[index] - a[index-1]. So, new smallest will be a[index-1] indeed???
Can you give me a test case, where it fails?

4

Simple Solution is:

max_difference=INT_MIN
smallest=a[0]
for(i=1;i<N;i++)
    if(a[i]<smallest)
         smallest=a[i]
    else if(max_difference<a[i]-smallest)
         max_difference=a[i]-smallest

Hope you got it!

2 Likes
5

@saanc I got your point, and I appreciate that. But I want to know the flaw in my logic/algorithm. Can you help me in that, or provide a test case where it fails. Thanx anayways. :slight_smile:

6

hey @ks2bmallik

Check your output for this test case:

1
9
4 15 3 1 9 11 17 5 12

This Code: http://www.codechef.com/viewsolution/6005001

gives output 13 where as actual answer should be 16.