Odd Jolly Jumpers problem

[galiwocky]

I am currently trying to solve a problem which is a modification of the Jolly Jumpers problem listed in several popular online judges. It's called Odd Jolly Jumpers, which may probably give you a hint of what was modified from the original Jolly Jumpers problem.

Here are the specs:

Problem Description

A sequence of n > 0 integers is called an Odd Jolly Jumper if the absolute values of the differences between successive elements take on all possible ODD values 1 through n - 1 only. For example, the sequence 1 4 3 6 is an Odd Jolly Jumper, because the absolute differences of successive values in the said sequence are 1 and 3 only. In contrast, 1 4 2 3 is not an Odd Jolly Jumper.

Input Format

Each line of input contains an integer n ≤ 3,000 followed by n integers representing the sequence.

Output Format

For each line of input generate a line of output saying "Odd Jolly" or "Not Odd Jolly".

Sample Input

4 1 4 3 6
4 1 4 2 3

Sample Output

Odd Jolly
Not Odd Jolly

One difference from the Jolly Jumpers problem is that the absolute differences of successive values may not be unique from other differences. In the first sample input, the absolute differences are 3 1 3, even the 3 was repeated, it was still considered an odd jolly jumper.

Problem is the online judge offering this problem doesn't accept my solution as CORRECT and I can't find where I have gone wrong. I tried various sample inputs and by judging the results according to the specifications, they are actually correct. Here's my code:

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

bool inOddList (int diff, int n) 
{
	for (int k = 1; k < n; k += 2) //from 1 to n-1, incrementing by 2 for each loop (all odd indexes)
	{
		if (k == diff)  //if the difference is within the range of odd values from 1 to n-1, return true
			return true;
	}
	return false;
	
}

string process (int x[], int n)
{
	int difference[n-1]; //the number of successive differences of n values is n - 1
	for (int j = 0; j < n - 1; j++) //compute absolute diff and check if it is even or out of range
	{  
		difference[j] = fabs( x[j] - x[j + 1] );
		if (difference[j] % 2 == 0) //if an absolute difference is even, immediately return "Not Odd Jolly"
			return "Not Odd Jolly";
	}
	
	int Jollycount = 0; //counter of absolute differences qualified as an odd jolly jump
	for (int l = 0; l < n - 1; l++) //traverse through each absolute difference
	{
		if (inOddList(difference[l], n)) //check if the absolute difference is within the range of 1 to n-1 odd integers, increment Jollycounter if true
			Jollycount++;		
	}
	if (Jollycount == n - 1) //if all of the absolute differences are in the odd list, return odd jolly
		return "Odd Jolly";
	else
		return "Not Odd Jolly";
	
}

int main() 
{
	int n;
	while ( cin >> n )
	{
		int x[n];
		for (int i = 0; i < n; i++) 
		{
			cin >> x[i]; //input x[i]
		}
		cout << process(x, n) << endl; //process the sequence
	}
	return 0;
}

I tried the following as inputs

4 1 4 3 6
4 1 4 2 3
5 7 10 13 12 9
2 0 1
11 10 1 4 1 4 9 4 3 6 15 8
5 2 4 6 7 8
9 1 2 1 4 9 16 7 9 12
10 1 2 11 4 7 14 9 10 5 14

And the corresponding outputs:

Odd Jolly
Not Odd Jolly
Odd Jolly
Odd Jolly
Odd Jolly
Not Odd Jolly
Not Odd Jolly
Odd Jolly

Correct me if I'm wrong but I think the results are pretty correct.

Could you give me some test cases to verify the correctness of the algorithm? What would I fix in order to get CORRECT judgment from the online judge? Any ideas are welcome. TIA!

[TheIdeasMan]

Hi galiwocky,

Something I noticed that might not make any difference to your results, but might be considered wrong by the judge.

string process (int x[], int n)

fabs( x[j]

x is an array of ints, but you have used fabs, which absolute of a float. So now you are putting a float into difference which is an array of int. Have a go with the abs function, which is for ints.

Hop this helps

[galiwocky]

Thanks for pointing that out. I changed it to abs function instead of fabs. Results of the test inputs remained the same. But still had an INCORRECT verdict from the onlineJudge. The last time I placed a wrong data type for an argument of a function, the verdict was a COMPILATION ERROR!

[ne555]

4 2 5 8 11
Odd Jolly

Wrong answer.

[fg109]

The example input given for an Odd Jolly Jumper was:

4 1 4 3 6

The first 4 tells you that the sequence of numbers should be 4 numbers long. So the number sequence is:

1 4 3 6

So n is 4, which makes n - 1 = 3. All odd integers between 0 and n - 1 are the set of integers {1, 3}.

The absolute values of the differences between each integer in the sequence is

 3 1 3 

Since all the differences are inside the set {1, 3}, and all members of the set {1, 3} are represented in the differences, then the number sequence is an Odd Jolly Jumper.

Your code checks everything but the last step; whether or not all members of the set are represented.

[galiwocky]

I see. Thanks a lot guys!

[galiwocky]

I have solved the issue of not checking whether all possible odd values from 1 to n-1 is checked. Still I'm getting INCORRECT verdict in the online judge.

Here's the modified code:

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

bool oddValInDifference (int diff[], int val, int n)
{
	for (int k = 0; k < n - 1; k++) //from 1 to n-1, incrementing by 2 for each loop (all odd indexes)
	{
		if (diff[k] == val)  //if the difference is within the range of odd values from 1 to n-1, return true
			return true;
	}
	return false;

}

string process (int x[], int n)
{
	int difference[n-1]; //the number of successive differences of n values is n - 1
	for (int j = 0; j < n - 1; j++) //compute absolute diff and check if it is even or out of range
	{
		difference[j] = abs( x[j] - x[j + 1] );
		if (difference[j] % 2 == 0) //if an absolute difference is even, immediately return "Not Odd Jolly"
			return "Not Odd Jolly";
	}

	for (int l = 1; l < n; l+= 2)
	{
		if (!oddValInDifference(difference, l, n))
			return "Not Odd Jolly";
	}
	return "Odd Jolly";
}

int main()
{
	int n;
	while ( cin >> n )
	{
		int x[n];
		for (int i = 0; i < n; i++)
		{
			cin >> x[i]; //input x[i]
		}
		cout << process(x, n) << endl; //process the sequence
	}
	return 0;
}

What could still be wrong on this? Any suggestions? Any sample outputs to test the correctness of the algorithm?