OJ Board

Posted: **Fri Apr 19, 2002 2:43 am**

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

Posted: **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.

Posted: **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:)

Posted: **Mon Apr 22, 2002 3:57 am**

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

Posted: **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.

Posted: **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

Posted: **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.

Posted: **Thu Apr 25, 2002 5:09 am**

STL has all these nice ADTs:)

Posted: **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

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]

Posted: **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?

Posted: **Mon Apr 11, 2005 10:11 pm**

I used AVL tree, and got .379 sec.

Posted: **Mon Apr 11, 2005 11:16 pm**

Thanks mf.

Posted: **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.

Posted: **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.

Posted: **Sun Apr 24, 2005 8:26 pm**

Ah. It was a bug in my use of the iterator.

OJ Board

501 - Black Box

501 - Black Box

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

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