11240 - Antimonotonicity

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Fri Jul 20, 2007 3:21 pm

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/

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

WA

Post by joy » Tue Aug 28, 2007 9:28 pm

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...
form kisui na ... class tai asol....
iF U hv d class u get the form....

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: WA

Post by saiful_sust » Tue Sep 28, 2010 5:44 pm

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
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Re: 11240 - Antimonotonicity

Post by SePulTribe » Sun Nov 14, 2010 8:30 am

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.

Post Reply

Return to “Volume 112 (11200-11299)”