501 - Black Box
Moderator: Board moderators
501 - Black Box
bacause I `m afraid my program will get Time Exceed!
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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:)
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
Re: for 501 : Is there any efficient algorism to be used ?
1) Two HeapsAnderson wrote:bacause I `m afraid my program will get Time Exceed!
2) Red-Black Tree
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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][/c][/cpp]
I have posted my code here,
because i have tried in many ways to get ac but
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
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]
"Everything should be made simple, but not always simpler"
-
- Experienced poster
- Posts: 154
- Joined: Sat Apr 17, 2004 9:34 am
- Location: EEE, BUET
501 - Black Box : What should be the data structure ?
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:](./images/smilies/icon_rolleyes.gif)
![:roll:](./images/smilies/icon_rolleyes.gif)
You should never take more than you give in the circle of life.
-
- Experienced poster
- Posts: 154
- Joined: Sat Apr 17, 2004 9:34 am
- Location: EEE, BUET
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
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...
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.
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.