11240 - Antimonotonicity

[StatujaLeha]

You can look at the sample solution at the Waterloo site (google for it). It is a quadratic time complexity solution. They missed a crucial observation to make it linear, but it is not very hard to find.

Can you give me the address of the website? There's so much websites called "Waterloo"...

Thanks

http://plg.uwaterloo.ca/~acm00/

[joy]

I got WA...
please help me... i cannot find any wrong

Code: Select all

#include<stdio.h>

int a[30005];

void main()
{
	int t, test, j, cnt, max, i, n;
	scanf("%d", &test);
	for(t=0; t<test; t++)
	{
		max=0;
		scanf("%d", &n);
		for(i=0; i<n; i++)
			scanf("%d", &a[i]);
		for(i=0; i<n; )
		{
			cnt=1;
			for(j=i+1; j<n; j++)
			{
				if(i%2==j%2)
				{
					if(a[j]>a[j-1])
						cnt++;
					else
						break;
				}
				else
				{
					if(a[j]<a[j-1])
						cnt++;
					else
						break;
				}
			}
			i=j;
			if(cnt>max)
				max=cnt;
			if(cnt>1)
				i--;
		}
		printf("%d\n", max);
	}
}

thanks in advance...

[saiful_sust]

Hi joy.........
ur code give worng output for this case

try more happy coding

Input :

Code: Select all

4
15 2 4 5 1 3 6 1 2 5 9 3 2 1 25 1
15 2 4 5 1 3 2 1 2 5 9 3 4 1 25 1
15 2 4 5 1 3 3 1 2 5 9 3 2 1 25 1
15 2 4 5 1 3 5 1 2 5 9 3 6 1 25 1

Output :

Code: Select all

8
10
8
10

• IMPOSSIBLE MEANS I M POSSIBLE....................................

[SePulTribe]

Don't forget that if after the first maximum point you encounter a monotonic sequence, the most extreme point of the monotonic sequence will replace the current last element of the subsequence that has been observed so far.