481 - What Goes Up

[serur]

some test cases for 481- What goes up, please.
this nasty WA...

[serur]

[serur]

OK, in the long run I got it accepted!
If you need for Output you should feel free to ask me...
I'm grateful to Stephanus Indra & Steven Halim for their explanation of LIS algorithm on their website.
and another related 497-"Defence" AC!

[Moha]

For each element you can store its papa. and tracing back all the papa to read null, would results in sequence. Think about it, you can figure it.

[DasBoot]

I keep getting WA.
Can someone post some test cases for this?
I went through all the posts, and my program gives the correct answer for everything discussed so far.

This problem is driving me crazy.

[Moha]

Try this:
5
2
3
4
1
3
I got this sample from adrian.

[Quake2]

Hi! I just solved problem 481 and I'm fifth, but I was wondering if my solution was fair, since I've used big arrays for almost anything (and used crazy I/O routines, something that usually I don't use for normal I/O operations), since most of the time was taken during I/O (e.g. I did some timing with rdtsc (reads the internal time stamp counter), my LIS algorithm ran in about 20 million cycles (using an input file of 50000 numbers), my first version of the I/O routines in about 60 milion cycles (both for input and output), solving this and others problems, makes me wonder if we are challenged to write fast I/O routines or fast algorithms, I know that with today hardware memory is not an issue, but keep in mind that on some(old) architectures there is still the 4gb limit, I think that problems sholud have a well defined number of test cases, e.g. the first line of problem 481 should be the total number of numbers to read, this way memory usage could be reduced a lot
anyway, I noticed that this was an issue with older problems, most of the modern ones are well defined
let me know what you think...
Bye!

[feanor]

i think that problem 481 could be done using a "one-pass" algorithm. so you can read the numbers in input one-by-one without put them into an array! take a look at this http://www.lcs.mit.edu/publications/pub ... TR-931.pdf ...
i've implemented the algorithm described in this article but the judge give me compile error! even i've tried my implementation with huge input! can you give some I/O? or can you take a look to my code??

[IRA]

When I read the LIS algorithm which time complexity is O(nlogn).
But that only know the longest length value,doesn't know the real increase subsequence content.
How could I do to find the correct subsequence in this algorithm?
Who can show me some opinion?
This is my reference as fallow.......
http://www.comp.nus.edu.sg/~stevenha/pr ... _(LIS/LDS)
Thanks in advance!

[chensc]

Umm...I know this problem should be solved by LIS.
But I don't know how to input.
Fllowing is my code , would you give me any suggestion?
It've got RE for so many times.
Thanks.

Code: Select all

Removed After TLE...XD

[Darko]

I just checked my code and my MAX is 200010.

[Wei-Ming Chen]

max = 100000 is enough

[chensc]

Umm...Thank you.
But after the array=100000, It became to get TLE.
Fllowing is my new code, could you give me a hand?
That's very kind of you.

Code: Select all

#include <stdio.h>
#define MAX 100000

int main(){
	register short num[MAX];
	register short length[MAX]={0};
	register short lis[MAX];
	register unsigned short index=0;
	while(scanf("%d",num[index++]));

	length[0]=1;
	register unsigned short max=1,max_index=0;
	for(register unsigned short i=0; i<index; i++){
		register unsigned short tmp=0;
		for(register unsigned short j=0; j<i; j++)
			if(num[j]>num[i] && length[j]>tmp)
				tmp=length[j];
		length[i]=tmp+1;
		if(length[i]>max)
			max=length[i], max_index=i;
	}

	lis[max]=num[max_index];
	for(register unsigned short i=max-1, j=max_index-1; i>0; j--)
		if(num[j]<num[max_index] && length[j]==i)
			lis[i--]=num[j], max_index=j;

	printf("%d\n-\n",max);
	for(register unsigned short i=0; i<=max; i++)
		printf("%d\n",lis[i]);
	return 0;
}

[daveon]

But that only know the longest length value,doesn't know the real increase subsequence content.

Doesn't the predecessor array keep track of this for you?

[nymo]

Hi, I 've used an INT array of size 50000 and getting WA. Can someone provide some IOs? [I 've tried IOs posted on other threads]... THANKS. and THERE IS ONLY ONE TEST CASE, RIGHT?