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

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

11240 - Antimonotonicity

Post by jan_holmes » Sun Jul 15, 2007 3:32 am

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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » 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.

DanS
New poster
Posts: 3
Joined: Mon May 21, 2007 8:55 pm

Post by DanS » Sun Jul 15, 2007 6:07 am

Hi, can I have some extra test cases?

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by Hackson » 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.
Solving problem is a no easy task...

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Jul 15, 2007 6:48 am

...
Last edited by sclo on Sun Jul 15, 2007 12:56 pm, edited 1 time in total.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » 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).

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Sun Jul 15, 2007 11:54 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Jul 15, 2007 12:22 pm

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

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Sun Jul 15, 2007 2:13 pm

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.
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'.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Jul 15, 2007 2:53 pm

Never mind the technicalities, we're talking about the same thing :)
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

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

Post by StatujaLeha » Sun Jul 15, 2007 4:31 pm

little joey wrote:
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.
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).

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » 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.

Parleen
New poster
Posts: 5
Joined: Wed Jun 20, 2007 8:27 pm
Location: DreamTown

Post by Parleen » 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 :

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

}
}  
Somebody help me

KirllButin
New poster
Posts: 6
Joined: Mon Feb 26, 2007 10:42 pm

Post by KirllButin » 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

Code: Select all

//deleted
subsequence can be not cosequtive
Last edited by KirllButin on Sun Jul 15, 2007 7:45 pm, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Sun Jul 15, 2007 6:53 pm

Ivan wrote:I am not going to comment on a linear solution (I believe that no correct greedy
solution exists).
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.

Post Reply

Return to “Volume 112 (11200-11299)”