i said dis bcuz....according to me akshata's algo has linear time while urs, i guess has square tym complexity..correct me if m wrong
On Tue, Mar 22, 2011 at 12:09 AM, ayush bhutani <[email protected]>wrote: > @sanchit nested loops does not mean TLE > I have just traversed the whole process's time array once for each elapse > time calculations ie O(n) and O(n^2) in total. I am not able to figure out > a faster method or a DP approach. Suggestions awaited > > On Mon, Mar 21, 2011 at 11:20 PM, sanchit mittal <[email protected]>wrote: > >> with so many nested loops u r obvcly goin to get tle.... >> >> >> On Mon, Mar 21, 2011 at 11:07 PM, ayush bhutani >> <[email protected]>wrote: >> >>> I have got a better algo >>> But I am also getting TLE >>> #include<stdio.h> >>> int main(){ >>> int n,i,j; >>> long t[50000]; >>> long elapse[50000]; >>> scanf("%d",&n); >>> for(i=0;i<n;i++){ >>> scanf("%ld",&t[i]); >>> elapse[i]=0; >>> } >>> for(i=0;i<n;i++){ >>> >>> for(j=0;j<n;j++){ >>> if(j!=i){ >>> if(t[j]<t[i]){ >>> elapse[i] +=t[j]; >>> } >>> else{ >>> if(j<i){ >>> elapse[i]+=t[i]; >>> } >>> else{ >>> elapse[i] +=(t[i]-1); >>> } >>> } >>> } >>> else{ >>> elapse[i] +=t[i]; >>> } >>> } >>> } >>> for(i=0;i<n;i++){ >>> printf("%ld\n",elapse[i]); >>> } >>> >>> return 0; >>> } >>> >>> >>> On 3/21/11, Akshata Sharma <[email protected]> wrote: >>> > Which data structure to use for getting it accepted?? This algorithm >>> > gives tle. Using scanf, printf is also resulting in tle. >>> > >>> > On Mar 21, 7:06 pm, radha krishnan <[email protected]> >>> > wrote: >>> >> U have to use Some Advanced Data Structures for this problem >>> >> :P >>> >> >>> >> >>> >> >>> >> On Mon, Mar 21, 2011 at 3:02 PM, saurabh singh <[email protected]> >>> >> wrote: >>> >> > using scanf and printf and still tle,I am not pretty sure how malloc >>> or >>> >> > new >>> >> > arrays can speed up execution? >>> >> >>> >> > On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal < >>> [email protected]> >>> >> > wrote: >>> >> >>> >> >> use scanf n printf instead of cin n cout, >>> >> >> malloc array of structures after reading value of n if working in c >>> >> >> else >>> >> >> use new in cpp >>> >> >> rest i guess...is ok >>> >> >> On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal >>> >> >> <[email protected]> >>> >> >> wrote: >>> >> >>> >> >>> I worked on this problem but cud not get a more efficient algo >>> than >>> >> >>> yours. >>> >> >>> Plz get back 2 me if u find a better algo. >>> >> >>> >> >>> On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma >>> >> >>> <[email protected]> wrote: >>> >> >>> >> >>>> I tried to solve this problem >>> >> >>>>https://www.spoj.pl/problems/RRSCHED/ >>> >> >>> >> >>>> I am getting TLE!! How can I improve my code?? >>> >> >>> >> >>>> #include<iostream> >>> >> >>>> #include<stdio.h> >>> >> >>> >> >>>> using namespace std; >>> >> >>> >> >>>> struct process >>> >> >>>> { >>> >> >>>> long time; >>> >> >>>> int finished; >>> >> >>>> long elapsed_time; >>> >> >>>> }; >>> >> >>> >> >>>> int main() >>> >> >>>> { >>> >> >>>> long n,sum=0; >>> >> >>>> cin>>n; >>> >> >>>> struct process prss[50000]; >>> >> >>>> for(long i=0;i<n;i++) >>> >> >>>> { >>> >> >>>> scanf("%ld",&prss[i].time); >>> >> >>>> prss[i].finished=0; >>> >> >>>> sum+=prss[i].time; >>> >> >>>> } >>> >> >>>> long index=0; >>> >> >>>> for(long k=1;k<=sum;k++) >>> >> >>>> { >>> >> >>>> while(prss[index].finished==1) >>> >> >>>> index++; >>> >> >>> >> >>>> prss[index].time--; >>> >> >>> >> >>>> if(prss[index].time==0) >>> >> >>>> { >>> >> >>>> prss[index].finished=1; >>> >> >>>> prss[index].elapsed_time=k; >>> >> >>>> } >>> >> >>> >> >>>> index++; >>> >> >>>> if(index==n) >>> >> >>>> index=0; >>> >> >>>> } >>> >> >>> >> >>>> for(long i=0;i<n;i++) >>> >> >>>> printf("%ld\n",prss[i].elapsed_time); >>> >> >>>> return 0; >>> >> >>>> } >>> >> >>> >> >>>> -- >>> >> >>>> You received this message because you are subscribed to the >>> Google >>> >> >>>> Groups "Algorithm Geeks" group. >>> >> >>>> To post to this group, send email to [email protected]. >>> >> >>>> To unsubscribe from this group, send email to >>> >> >>>> [email protected]. >>> >> >>>> For more options, visit this group at >>> >> >>>>http://groups.google.com/group/algogeeks?hl=en. >>> >> >>> >> >>> -- >>> >> >>> You received this message because you are subscribed to the Google >>> >> >>> Groups >>> >> >>> "Algorithm Geeks" group. >>> >> >>> To post to this group, send email to [email protected]. >>> >> >>> To unsubscribe from this group, send email to >>> >> >>> [email protected]. >>> >> >>> For more options, visit this group at >>> >> >>>http://groups.google.com/group/algogeeks?hl=en. >>> >> >>> >> >> -- >>> >> >> Sanchit Mittal >>> >> >> Second Year Undergraduate >>> >> >> Computer Engineering >>> >> >> Delhi College of Engineering >>> >> >> ph- +919582414494 >>> >> >>> >> >> -- >>> >> >> You received this message because you are subscribed to the Google >>> >> >> Groups >>> >> >> "Algorithm Geeks" group. >>> >> >> To post to this group, send email to [email protected]. >>> >> >> To unsubscribe from this group, send email to >>> >> >> [email protected]. >>> >> >> For more options, visit this group at >>> >> >>http://groups.google.com/group/algogeeks?hl=en. >>> >> >>> >> > -- >>> >> > Saurabh Singh >>> >> > B.Tech (Computer Science) >>> >> > MNNIT ALLAHABAD >>> >> >>> >> > -- >>> >> > You received this message because you are subscribed to the Google >>> >> > Groups >>> >> > "Algorithm Geeks" group. >>> >> > To post to this group, send email to [email protected]. >>> >> > To unsubscribe from this group, send email to >>> >> > [email protected]. >>> >> > For more options, visit this group at >>> >> >http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]. >>> > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> Sanchit Mittal >> Second Year Undergraduate >> Computer Engineering >> Delhi College of Engineering >> ph- +919582414494 >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Sanchit Mittal Second Year Undergraduate Computer Engineering Delhi College of Engineering ph- +919582414494 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
