481  What Goes Up
Moderator: Board moderators
481I/O needed
some test cases for 481 What goes up, please.
this nasty WA...
this nasty WA...
481What Goes Up
Last edited by serur on Mon Apr 03, 2006 9:33 pm, edited 1 time in total.
481ACCC!
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!
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!
481  About arrays...
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!
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!
i think that problem 481 could be done using a "onepass" algorithm. so you can read the numbers in input onebyone without put them into an array! take a look at this http://www.lcs.mit.edu/publications/pub ... TR931.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??
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!
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!
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!
Q481  How to input ?
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.
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
Last edited by chensc on Sat Aug 05, 2006 3:44 pm, edited 1 time in total.

 Experienced poster
 Posts: 122
 Joined: Sun Nov 13, 2005 10:25 am
 Location: Taiwan
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.
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=max1, j=max_index1; 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;
}
I'm a Taiwaness. So I couldn't master English well.XD
Re: 481 What goes up  help!
Doesn't the predecessor array keep track of this for you?IRA wrote:But that only know the longest length value,doesn't know the real increase subsequence content.
SOME TEST CASES, PLEASE
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?
regards,
nymo
nymo