501 - Black Box

[Anderson]

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

[Stefan Pochmann]

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]

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]

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

[C8H10N4O2]

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]

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

1) Two Heaps
2) Red-Black Tree

[Stefan Pochmann]

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]

STL has all these nice ADTs:)

[anupam]

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]

[Mohammad Mahmudur Rahman]

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?

[mf]

I used AVL tree, and got .379 sec.

[Mohammad Mahmudur Rahman]

Thanks mf.

[Abednego]

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.

[mf]

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.

[Abednego]

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