## 11240 - Antimonotonicity

Moderator: Board moderators

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
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
Contact:

### WA

I got WA...

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);
}
}``````
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

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

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.