Page 3 of 6

### 481-I/O needed

Posted: Thu Mar 30, 2006 11:41 pm
some test cases for 481- What goes up, please.
this nasty WA...

### 481-What Goes Up

Posted: Fri Mar 31, 2006 12:21 am

### 481-ACCC!

Posted: Fri Mar 31, 2006 10:27 am
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!

Posted: Mon Apr 10, 2006 12:40 am
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.

Posted: Sun Apr 16, 2006 6:40 am
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.

Posted: Sun Apr 16, 2006 9:17 am
Try this:
5
2
3
4
1
3
I got this sample from adrian.

Posted: Wed May 24, 2006 7:38 pm
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!

Posted: Tue Jun 06, 2006 12:25 pm
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??

### 481 What goes up --- help!

Posted: Thu Jul 20, 2006 3:02 am
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)

### Q481 - How to input ?

Posted: Fri Aug 04, 2006 3:33 pm
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
``````

Posted: Fri Aug 04, 2006 6:45 pm
I just checked my code and my MAX is 200010.

Posted: Sat Aug 05, 2006 9:32 am
max = 100000 is enough

Posted: Sat Aug 05, 2006 3:46 pm
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;
}``````

### Re: 481 What goes up --- help!

Posted: Mon Aug 07, 2006 1:52 am
IRA wrote: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?