501 - Black Box

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

Moderator: Board moderators

Anderson
New poster
Posts: 6
Joined: Thu Apr 18, 2002 12:47 pm

501 - Black Box

Post by Anderson » Fri Apr 19, 2002 2:43 am

bacause I `m afraid my program will get Time Exceed!

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Fri Apr 19, 2002 5:51 am

Some hints you could've also found in the problem ranklist: minheap+maxheap, sandglass. Question: why don't you try some ideas first before asking? If you're always "afraid" that you can't do it, then you'll never invent sth yourself.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Mon Apr 22, 2002 12:59 am

If you are serious about Computer Science, you should pick up a couple of algorithm books (Dijkstra, Skienka, the MIT introduction one). They should give you some basic idea of the tools at your disposal. Then you should be able to apply the right one or even DEVELOP it. After all, Computer Science is only Applied Computational Mathematics. Induce and deduce:)

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Apr 22, 2002 3:57 am

What book of Dijkstra are you referring to? That sounds interesting, I never heard of it...

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Mon Apr 22, 2002 8:19 pm

I was thinking about A Discipline of Programming by Edsger Wybe Dijkstra. It teachs formal algorithmic proofs that transcend time and language. He tries to teach you his thinking processes. It is a bit harder read than Skiena, but well worth it.

Huangs
New poster
Posts: 1
Joined: Wed Apr 24, 2002 9:39 pm
Location: Taiwan
Contact:

Re: for 501 : Is there any efficient algorism to be used ?

Post by Huangs » Wed Apr 24, 2002 9:40 pm

Anderson wrote:bacause I `m afraid my program will get Time Exceed!
1) Two Heaps
2) Red-Black Tree

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Apr 25, 2002 5:00 am

1) I already said that days ago.
2) Confusing, you don't need that. One could use a map in C++ which is probably implemented as a RB-tree, but I wouldn't implement my own one for it.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Apr 25, 2002 5:09 am

STL has all these nice ADTs:)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Oct 28, 2002 1:07 pm

hello all,
I have posted my code here,
because i have tried in many ways to get ac but :oops: :oops:
i have got w ans.
please check it.
code:[c]

Code: Select all

[b]
#include<stdio.h>
#define NUM 30100
main()
{
	long long int m,i,j,
	k,n,l,s,p,
	c[NUM],d[NUM],a[NUM];
	scanf("%lld%lld",&m,&n);
	s=0;
	for(i=0;i<m;i++)
		scanf("%lld",&c[i]);
	for(i=0;i<n;i++)
		scanf("%lld",&d[i]);
	l=p=0;
	for(i=0;i<m;i++)
	{
		for(j=0;j<s;j++)
			if(a[j]>c[i])
				break;
		if(j==s) a[j]=c[i],s++;
		else
		{
			for(k=s;k>j;k--)
				a[k]=a[k-1];
			a[j]=c[i];s++;
		}
		a[s]=0;
		while(1)
		{
			if(d[l]==n) break;
			if(d[l]!=(i+1)) break;
			l++;
			p++;
			printf("%lld\n",a[p-1]);
		}
	}
	return 0;
}

any help is welcome[/b]
[/c][/cpp]
"Everything should be made simple, but not always simpler"

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

501 - Black Box : What should be the data structure ?

Post by Mohammad Mahmudur Rahman » Mon Apr 11, 2005 9:47 pm

I used insertion sort in this problem due to the fact that each time a new value is entered into a sorted list. But this procedure recieves a TLE. Can someone tell me what data structure should I use to speed the things up? :roll:
You should never take more than you give in the circle of life.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Apr 11, 2005 10:11 pm

I used AVL tree, and got .379 sec.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Apr 11, 2005 11:16 pm

Thanks mf. :)
You should never take more than you give in the circle of life.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Apr 24, 2005 6:35 am

Maybe there is something I don't understand about this problem. I tried coding it twice, and I always get WA. Could anyone give me a hint? I simply use a set to store the numbers and an iterator into that set pointing the the last number that I accessed. I use a set of pairs to take care of duplicate elements.

Code: Select all

Oll Korrect now.
Last edited by Abednego on Sun Apr 24, 2005 8:26 pm, edited 1 time in total.
If only I had as much free time as I did in college...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Apr 24, 2005 11:19 am

I don't know if your algorithm is correct, I'm no C++ guy.

The problem as I implemented it: with each "ADD" query add the number to your data structure. With the i-th "GET" query print the i-th smallest number in the data structure.

The problem comes from NEERC' 1996 regionals. You can use the tests at http://www.acm.inf.ethz.ch/ProblemSetAr ... NERC/1996/ as a last resort.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Apr 24, 2005 8:26 pm

Ah. It was a bug in my use of the iterator.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 5 (500-599)”