11456 - Trainsorting

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

Moderator: Board moderators

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11456 - Trainsort

Post by lbv » Tue Jun 03, 2014 3:57 pm

jddantes wrote:Wouldn't you need to find the LIS and LDS with each car as the starting point?
Usually when you calculate the LIS/LDS of a sequence, you calculate all the partial results in one pass. That is, you calculate the LIS of the range [ 0 : i ] for 0 <= i < n.

Now, your question could also be written as:
(..) find the LIS and LDS with each car as the ending point, in the reversed sequence?

Which, as you can see, is an idea that has been suggested in previous comments, and can be implemented with only one pass. No need to calculate the LIS/LDS n times.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11456 - Trainsort

Post by jddantes » Mon Jun 09, 2014 8:25 am

Right, thanks :)

hanguyenqu
New poster
Posts: 1
Joined: Sun Nov 23, 2014 7:38 am

Re: 11456 - Trainsorting

Post by hanguyenqu » Wed Dec 03, 2014 2:36 pm

Hepl me. I don't understand why have Runtime error

Code: Select all

#include<stdio.h>

#define MAX 500

int n,arr[MAX],f[MAX],d[MAX];

int LIS(int k)
{
	int i,ma;
	
	if(f[k]!=-1)
		return f[k];
		
	f[k]=1;
	for(i=k+1;i<n;i++){
		if(arr[k]<arr[i]){
			ma=LIS(i)+1;
			if(ma>f[k])
				f[k]=ma;
		}
	}
	return f[k];
}

int LDS(int j)
{
	int i,min;
	
	if(d[j]!=-1){
		return d[j];
	}
	
	d[j]=1;
	for(i=j+1;i<n;i++){
		if(arr[j]>arr[i]){
			min=LDS(i)+1;
			if(min>d[j]){
				d[j]=min;
			}
		}
	}
	return d[j];
}

int main()
{
//	freopen("11456.inp","r",stdin);
	
	int t,it,i,max,li,ld;
	
	scanf("%d",&t);
	
	for(it=0;it<t;it++){
		max=1;
		scanf("%d",&n);
		
		for(i=0;i<n;i++){
			scanf("%d",&arr[i]);
		}
		
		for(i=0;i<n;i++){
			f[i]=-1;
			d[i]=-1;
		}
		
		for(i=0;i<n;i++)
		{
			li=LIS(i);
			ld=LDS(i);
			if(li+ld-1>max){
				max=li+ld-1;
			}
		}
		
		printf("%d\n",max);
	}
	
	return 0;
	
}
Last edited by brianfry713 on Wed Dec 03, 2014 9:17 pm, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11456 - Trainsorting

Post by brianfry713 » Thu Dec 04, 2014 12:59 am

The first line contains an integer 0 <= n <= 2000, the number of cars.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11456 - Trainsorting

Post by jddantes » Wed Dec 17, 2014 12:13 pm

AC
Last edited by jddantes on Thu Dec 25, 2014 2:23 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11456 - Trainsorting

Post by brianfry713 » Wed Dec 24, 2014 12:41 am

If n = 0 then print 0
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 114 (11400-11499)”