Page 3 of 3

Posted: Fri Jul 20, 2007 3:21 pm
by StatujaLeha
WingletE wrote:
little joey wrote: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/

WA

Posted: Tue Aug 28, 2007 9:28 pm
by 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...

Re: WA

Posted: Tue Sep 28, 2010 5:44 pm
by 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....................................

Re: 11240 - Antimonotonicity

Posted: Sun Nov 14, 2010 8:30 am
by 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.