### 11240 - Antimonotonicity

Posted:

**Sun Jul 15, 2007 3:32 am**Got TLE with DP (Top Down). How did you guys solve this problem without getting TLE ?

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=38&t=19322

Page **1** of **3**

Posted: **Sun Jul 15, 2007 3:32 am**

Got TLE with DP (Top Down). How did you guys solve this problem without getting TLE ?

Posted: **Sun Jul 15, 2007 5:05 am**

Hints:

There are only two direction. One is '<' & another is '>'.

Then make a table with memo[N][2]. That's all.

There are only two direction. One is '<' & another is '>'.

Then make a table with memo[N][2]. That's all.

Posted: **Sun Jul 15, 2007 6:07 am**

Hi, can I have some extra test cases?

Posted: **Sun Jul 15, 2007 6:30 am**

There can be at most 30000 numbers. Surely simple DP does not work, and you need further optimizations.

Posted: **Sun Jul 15, 2007 6:48 am**

...

Posted: **Sun Jul 15, 2007 10:02 am**

I did greedy.

My solution is O(n) without any extra memory(not even an array to store all numbers).

My solution is O(n) without any extra memory(not even an array to store all numbers).

Posted: **Sun Jul 15, 2007 11:54 am**

Could somebody tell me how to use DP in this problem?

Posted: **Sun Jul 15, 2007 12:22 pm**

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.WingletE wrote:Could somebody tell me how to use DP in this problem?

To sunny: I wouldn't call it 'greedy', I think technically it is still DP, but with a 'zero-dimensional DP-array'. Unless you have a different solution, of course.

Posted: **Sun Jul 15, 2007 2:13 pm**

Actually, I was little confused to call it greedy too. But as in my solution I always try to keep the bigger(if the sequence is towards to up)/smaller(if towards to down) values as last element , so I considered this as 'greedy'.little joey wrote: To sunny: I wouldn't call it 'greedy', I think technically it is still DP, but with a 'zero-dimensional DP-array'. Unless you have a different solution, of course.

Posted: **Sun Jul 15, 2007 2:53 pm**

Never mind the technicalities, we're talking about the same thing

Posted: **Sun Jul 15, 2007 4:31 pm**

My solution isn't based on DP. It works in O(n) and also can be modified to avoid storing of sequence in the array(but i use array for convenience).little joey wrote:To sunny: I wouldn't call it 'greedy', I think technically it is still DP, but with a 'zero-dimensional DP-array'. Unless you have a different solution, of course.WingletE wrote:Could somebody tell me how to use DP in this problem?

Posted: **Sun Jul 15, 2007 5:33 pm**

I am not going to comment on a linear solution (I believe that no correct greedy

solution exists).

My advice to people that are trying to look at this as a typical DP problem:

1. The n^2 solution is obvious.

Let L* be the length of the longest alternating (Mary) sequence ending *

at element i of the given (Fred or let call it A) sequence such that the

last element is a "low" element.

Let H* be the length of longest alternating (Mary) sequence ending at*

element i of the given A sequence such that the last element is a "high" element.

L* = max(H[j] + 1) for all j < i such that A[j] > A**.*

H* = max(L[j] + 1) for all j < i such that A[j] < A**.*

In code terms this looks something this:

for every i from 1 to n

for every j from 1 to i - 1 { do the above }

2. To reduce the complexity we use a common technique to reduce the inner loop.

Instead of iterating through every j in order to find the above mentioned

maximum we can do a range maximum query (RMQ) - which can be easily done in

logarithmic time leading to overall complexity of n * log(n).

In the above context the query is done over a range of VALUES (not indexes)

of elements of A looking for such a VALUE whose index i corresponds

to the largest H* (or L**). The mentioned query can be easily answered *

using an appropriate data structure such as segment tree, binary indexed

tree or whichever you prefer.

So we can replace the inner loop with something like this:

L* = get_max_H(A** + 1, n) + 1; insert_new_L();*

H[i] = get_max_L(1, A[i] - 1) + 1; insert_new_H();

The idea of this technique is worth remembering since it can be quite useful

in some DP problems.

solution exists).

My advice to people that are trying to look at this as a typical DP problem:

1. The n^2 solution is obvious.

Let L

at element i of the given (Fred or let call it A) sequence such that the

last element is a "low" element.

Let H

element i of the given A sequence such that the last element is a "high" element.

L

H

In code terms this looks something this:

for every i from 1 to n

for every j from 1 to i - 1 { do the above }

2. To reduce the complexity we use a common technique to reduce the inner loop.

Instead of iterating through every j in order to find the above mentioned

maximum we can do a range maximum query (RMQ) - which can be easily done in

logarithmic time leading to overall complexity of n * log(n).

In the above context the query is done over a range of VALUES (not indexes)

of elements of A looking for such a VALUE whose index i corresponds

to the largest H

using an appropriate data structure such as segment tree, binary indexed

tree or whichever you prefer.

So we can replace the inner loop with something like this:

L

H[i] = get_max_L(1, A[i] - 1) + 1; insert_new_H();

The idea of this technique is worth remembering since it can be quite useful

in some DP problems.

Posted: **Sun Jul 15, 2007 6:37 pm**

Please tell me what's wrong in my code? I couldnt find bug in my problem

Or send some critical input/output here :

Or send some critical input/output here :

Code: Select all

```
#include<stdio.h>
#include<math.h>
long a,b,c,i,j,k;
void main()
{
long par,inp,test,max,count,t;
scanf("%ld",&test);
for(t=1;t<=test;t++)
{
scanf("%ld",&inp);
max=0;count=0;
if(inp>0)
{
count=1;max=1;
par=0;
scanf("%ld",&a);
b=a;
for(i=2;i<=inp;i++)
{
scanf("%ld",&a);
if(par%2==0 && b>a)
{count++;par++;b=a;}
else if(par%2!=0 && b<a)
{par++;count++;b=a;}
else
{
if(count>max)
max=count;
count=1;
par=0;
b=a;
}
}
}
if(count>max)
max=count;
printf("%ld\n",max);
}
}
```

Posted: **Sun Jul 15, 2007 6:45 pm**

I'm trying to solve it in O(n), but don't understand what's wrong with this code

Please help me

subsequence can be not cosequtive

Please help me

Code: Select all

```
//deleted
```

Posted: **Sun Jul 15, 2007 6:53 pm**

There is a dp solution using O(n) time and O(1) memory, and it is trivial to prove that the algorithm is correct. It's a little surprising.Ivan wrote:I am not going to comment on a linear solution (I believe that no correct greedy

solution exists).