481 - What Goes Up

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

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

481-I/O needed

Post by serur » Thu Mar 30, 2006 11:41 pm

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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

481-What Goes Up

Post by serur » Fri Mar 31, 2006 12:21 am

Last edited by serur on Mon Apr 03, 2006 9:33 pm, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

481-ACCC!

Post by serur » 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! :D

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

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

DasBoot
New poster
Posts: 1
Joined: Thu Oct 13, 2005 10:06 pm

Post by DasBoot » 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.
:evil:

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Sun Apr 16, 2006 9:17 am

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

Quake2
New poster
Posts: 1
Joined: Wed May 24, 2006 7:28 pm

481 - About arrays...

Post by Quake2 » 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!

feanor
New poster
Posts: 3
Joined: Tue Jun 06, 2006 12:17 pm

Post by feanor » 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! 8) 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
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

481 What goes up --- help!

Post by IRA » 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)
Thanks in advance!

chensc
New poster
Posts: 2
Joined: Thu Aug 03, 2006 4:01 pm
Location: Taiwan, ROC
Contact:

Q481 - How to input ?

Post by chensc » 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
Last edited by chensc on Sat Aug 05, 2006 3:44 pm, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Aug 04, 2006 6:45 pm

I just checked my code and my MAX is 200010.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sat Aug 05, 2006 9:32 am

max = 100000 is enough

chensc
New poster
Posts: 2
Joined: Thu Aug 03, 2006 4:01 pm
Location: Taiwan, ROC
Contact:

Post by chensc » 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;
}
I'm a Taiwaness. So I couldn't master English well.XD

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Re: 481 What goes up --- help!

Post by daveon » 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?

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

SOME TEST CASES, PLEASE

Post by nymo » Sun Dec 03, 2006 4:27 pm

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

Post Reply

Return to “Volume 4 (400-499)”