@Dumanshu: Your idea is definitely a good improvement, however the SPOJ Runtimes are not reliable.. The code which was getting 0.00 AC with 512 KB Buffer now runs in 0.02 Seconds.. And I tried submitting the code with enhancement u suggested it runs in 0.01 even with 8KB Buffer.
http://ideone.com/kO8BW On Tue, Jun 28, 2011 at 1:09 AM, Dumanshu <[email protected]> wrote: > @Rizwan: > don't u think for the counting sort part, if u use 11 int array as it > is without copying values in the main array, it would run faster? And > later on, get the sum from the two 11 int arrays like I did. Although > m using a single buffer so m getting 0.01. ->http://ideone.com/lsK8n > So, by using a buffer of 512, u might b able to get a time of 0.0. > What do u think? > > On Jun 27, 2:05 am, rizwan hudda <[email protected]> wrote: >> I am able to get this accepted with 0.00 Secondshttp://ideone.com/Eg2wZ >> But, I am using 512 KB Buffer. Not sure how I do get 0.00 with a >> smaller buffer size say 8KB >> >> >> >> >> >> On Sun, Jun 26, 2011 at 7:54 AM, Wladimir Tavares <[email protected]> >> wrote: >> > sometimes using global static variables may be better to use dynamic >> > variables on the stack! >> >> > Sometimes! >> >> > Wladimir Araujo Tavares >> > Federal University of Ceará >> >> > On Sat, Jun 25, 2011 at 7:32 PM, Dumanshu <[email protected]> wrote: >> >> >> finally got it in 0.01 sec using all the optimizations i am aware of >> >> including what Wladimir had suggested. >> >> Now wat to do for 0.00??? >> >> heres my code- >> >>http://ideone.com/lsK8n >> >> >> please suggest if any further optimizations possible. >> >> >> On Jun 26, 2:21 am, Dumanshu <[email protected]> wrote: >> >> > Ok, it seems like bucket sort is the best way to do it. I got 0.06 >> >> > and to go further weneedto use char buffer like the one Wladimir >> >> > suggested. >> >> > But still i have a doubt that would it be possible to reduce 0.06 to >> >> > 0.00 using that buffer? >> >> >> > I don't think there can be any possible improvement in logic. >> >> > wat do u think? >> >> >> > On Jun 26, 12:25 am, Dumanshu <[email protected]> wrote: >> >> >> > > see i got 0.07 sec as the time after using counting sort.. because the >> >> > > hotness scale is 0-10 so i used an array of 11 ints to count the no. >> >> > > of occurrences. But i m nt able to further reduce this. >> >> > > ny suggestions? >> >> >> > > theres a comment on the problem: >> >> > > On an interesting side note: the maximising principle underlying this >> >> > > problem generalises to almost-everywhere finite functions on sigma- >> >> > > finite measure spaces by a theorem of Hardy and Littlewood, see >> >> > > Theorem II.2.2 in C. Bennett, R. Sharpley, "Interpolation of >> >> > > Operators" >> >> > > ny use??? >> >> >> > > On Jun 25, 3:08 pm, prathimzn <[email protected]> wrote: >> >> >> > > > somebody answer how to reduce time.... >> >> > > > *- - - - - >> >> > > > WITH REGARDS, >> >> >> > > > * >> >> > > > * >> >> > > > PRAMENDRA RATHI >> >> > > > * >> >> > > > ** >> >> >> > > > *B.TECH 2ND YEAR* >> >> > > > *COMPUTER SCIENCE AND ENGINEERING* >> >> > > > *NIT ALLAHABAD* >> >> >> > > > On Sat, Jun 25, 2011 at 12:27 AM, prathimzn <[email protected]> >> >> > > > wrote: >> >> > > > > sorry my time is 0.2 and i use simple int array and sort function >> >> > > > > of >> >> > > > > <algorithm>... >> >> >> > > > > *- - - - - >> >> > > > > WITH REGARDS, >> >> >> > > > > * >> >> > > > > * >> >> > > > > PRAMENDRA RATHI >> >> > > > > * >> >> > > > > ** >> >> >> > > > > *B.TECH 2ND YEAR* >> >> > > > > *COMPUTER SCIENCE AND ENGINEERING* >> >> > > > > *NIT ALLAHABAD* >> >> >> > > > > On Sat, Jun 25, 2011 at 12:04 AM, sunny agrawal >> >> > > > > <[email protected]>wrote: >> >> >> > > > >> i am not sure about this >> >> > > > >> but when i solved this problem using simple scanf, printf and >> >> > > > >> sort >> >> > > > >> function of algorithm library, my time was 0.08 so might be >> >> > > > >> reading the >> >> > > > >> values in character buffer and then parsing then in ints may help >> >> >> > > > >> how did you implemented ? >> >> > > > >> did you implemented your own sort funtion ? >> >> > > > >> which input/output methods you used ? >> >> >> > > > >> On Fri, Jun 24, 2011 at 11:23 PM, prathimzn <[email protected]> >> >> > > > >> wrote: >> >> >> > > > >>>http://www.spoj.pl/problems/FASHION/ >> >> >> > > > >>> i summit this question and my time is 0.02 as i used sorting and >> >> > > > >>> then >> >> > > > >>> multiply corresponding index value and sum them to get ans. >> >> >> > > > >>> but best time is 0.00 and 1.6M in C. >> >> > > > >>> can anyone tell me what is the bestalgoto solve this problem >> >> > > > >>> in 0.00 >> >> > > > >>> i.e. bestalgo >> >> >> > > > >>> * >> >> >> > > > >>> - - - - - >> >> > > > >>> WITH REGARDS, >> >> > > > >>> PRAMENDRA RATHI >> >> > > > >>> * >> >> > > > >>> ** >> >> > > > >>> *B.TECH 2ND YEAR* >> >> > > > >>> *COMPUTER SCIENCE AND ENGINEERING* >> >> > > > >>> *NIT 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. >> >> >> > > > >> -- >> >> > > > >> Sunny Aggrawal >> >> > > > >> B-Tech IV year,CSI >> >> > > > >> Indian Institute Of Technology,Roorkee >> >> >> > > > >> -- >> >> > > > >> 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. >> >> -- >> Thanks and regards >> Rizwan A Huddahttp://sites.google.com/site/rizwanhudda2- Hide quoted text - >> >> - Show quoted text - > > -- > 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. > > -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda2 -- 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.
