Re: [algogeeks] Re: NEED ALGO IN TIME 0.00
@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 duman...@gmail.com 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 rizwanhu...@gmail.com 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 wladimir...@gmail.com 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 duman...@gmail.com 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 duman...@gmail.com 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 duman...@gmail.com 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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To
[algogeeks] Re: NEED ALGO IN TIME 0.00
@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 rizwanhu...@gmail.com 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 wladimir...@gmail.com 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 duman...@gmail.com 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 duman...@gmail.com 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 duman...@gmail.com 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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from
[algogeeks] Re: NEED ALGO IN TIME 0.00
I found the problem statement on the web page link to be a bit weak. Nothing in the problem statement says that you must do anything other than read in two lines of integers and multiply them in pairs and sum the results ( ie. Dot Product ). People seem to think that you should sort the data first ( an assumption that is NOT in the problem statement ). Does that mean that you get the problem wrong if you don't sort the data first? Also... it looks as if you have to write the code in one of the listed languages. Is that true? You then submit your text code and it is compiled somewhere else? What compiler(s) is/are used and with what settings? This can affect both speed and memory (by large amounts). Also... exactly what does 1.6M for memory mean? For the moment, let's assume that you ARE supposed to sort the data first. Then... at best, all this test really does is check to see if you can read and sort data quickly. Multiplying pairs of numbers is trivial and I doubt many individuals are writing much code to speed up this simple Dot Product calculation. So... unless you write your own integer sorting algorithm that you are very proud of, what's the point of this test (other than it might be worthwhile as a homework assignment to new coders). Have I missed something? Dan :-) On Jun 24, 9:53 am, prathimzn prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: NEED ALGO IN TIME 0.00
@Dan: see, that is not the point. We are just looking for a better solution not just an algorithm which fetches us 0.00 time given the SPOJ conditions. Actually we are not worried about the compiler stuff because its all relative. Some other person on this SPOJ platform has submitted the code which runs in 0.00 sec so we want to think of the optimizations he might have employed which made his code to run faster. Another plus point is- the difference in the time might be covered by exploiting the SPOJ platform but in the meanwhile, we get to think, we might get a new approach to the problem or may be an inprovement in the algorithm being deployed. Thats the whole point. Its just relative. Someone has used some optimizations and got a better time so we are looking for it. People do write their functions to multiply, take modulus etc We skip the printf scanf calls instead switch to fread etc just to achieve the speedup. The purpose is not just to solve the problem but to solve it efficiently. Say we are just sorting an array, the way we do it, the memory we use etc. it all matters and SPOJ helps to measure the same relatively. The problem given might be trivial but the competition among thousands of coders trying to achieve the best time for the same builds the spirit and helps to explore new techniques, new algorithms. It all comes with an urge to make our code run faster. Regarding the 1.6M, I don't really kno what it means but if one is interested, you can look for it on the forums etc and you'll have your answer. Some addicted user must be knowing this stuff actually. At the end, its all about the competition after you discover the logic to solve the problem. When you don't have the urge to improve upon it, you won't discover something new, something efficient. These are my views. I am not an addicted SPOJ user. I might be mistaken but this is what i feel. Doom On Jun 26, 11:59 pm, Dan dant...@aol.com wrote: I found the problem statement on the web page link to be a bit weak. Nothing in the problem statement says that you must do anything other than read in two lines of integers and multiply them in pairs and sum the results ( ie. Dot Product ). People seem to think that you should sort the data first ( an assumption that is NOT in the problem statement ). Does that mean that you get the problem wrong if you don't sort the data first? Also... it looks as if you have to write the code in one of the listed languages. Is that true? You then submit your text code and it is compiled somewhere else? What compiler(s) is/are used and with what settings? This can affect both speed and memory (by large amounts). Also... exactly what does 1.6M for memory mean? For the moment, let's assume that you ARE supposed to sort the data first. Then... at best, all this test really does is check to see if you can read and sort data quickly. Multiplying pairs of numbers is trivial and I doubt many individuals are writing much code to speed up this simple Dot Product calculation. So... unless you write your own integer sorting algorithm that you are very proud of, what's the point of this test (other than it might be worthwhile as a homework assignment to new coders). Have I missed something? Dan :-) On Jun 24, 9:53 am, prathimzn prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - WITH REGARDS, PRAMENDRA RATHI * ** *B.TECH 2ND YEAR* *COMPUTER SCIENCE AND ENGINEERING* *NIT ALLAHABAD*- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: NEED ALGO IN TIME 0.00
You are correct, this question is by no means testing anything non trivial/hard. It is one of the problems that the beginners in competitive programming solve. As for the discussion regarding this problem in current thread, some enthusiastic guy had got this AC in 0.08 at SPOJ, and everyone was trying to see how to implement the program efficiently to get it down to 0.00 Seconds. Thanks, Rizwan. On Mon, Jun 27, 2011 at 12:29 AM, Dan dant...@aol.com wrote: I found the problem statement on the web page link to be a bit weak. Nothing in the problem statement says that you must do anything other than read in two lines of integers and multiply them in pairs and sum the results ( ie. Dot Product ). People seem to think that you should sort the data first ( an assumption that is NOT in the problem statement ). Does that mean that you get the problem wrong if you don't sort the data first? Also... it looks as if you have to write the code in one of the listed languages. Is that true? You then submit your text code and it is compiled somewhere else? What compiler(s) is/are used and with what settings? This can affect both speed and memory (by large amounts). Also... exactly what does 1.6M for memory mean? For the moment, let's assume that you ARE supposed to sort the data first. Then... at best, all this test really does is check to see if you can read and sort data quickly. Multiplying pairs of numbers is trivial and I doubt many individuals are writing much code to speed up this simple Dot Product calculation. So... unless you write your own integer sorting algorithm that you are very proud of, what's the point of this test (other than it might be worthwhile as a homework assignment to new coders). Have I missed something? Dan :-) On Jun 24, 9:53 am, prathimzn prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: NEED ALGO IN TIME 0.00
I am able to get this accepted with 0.00 Seconds http://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 wladimir...@gmail.com 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 duman...@gmail.com 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 duman...@gmail.com wrote: Ok, it seems like bucket sort is the best way to do it. I got 0.06 and to go further we need to 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 duman...@gmail.com 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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. --
[algogeeks] Re: NEED ALGO IN TIME 0.00
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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: NEED ALGO IN TIME 0.00
Ok, it seems like bucket sort is the best way to do it. I got 0.06 and to go further we need to 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 duman...@gmail.com 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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: NEED ALGO IN TIME 0.00
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 duman...@gmail.com wrote: Ok, it seems like bucket sort is the best way to do it. I got 0.06 and to go further we need to 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 duman...@gmail.com 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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: NEED ALGO IN TIME 0.00
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 duman...@gmail.com 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 duman...@gmail.com wrote: Ok, it seems like bucket sort is the best way to do it. I got 0.06 and to go further we need to 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 duman...@gmail.com 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 prathi...@gmail.com 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 prathi...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 prathi...@gmail.com 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 best algo to solve this problem in 0.00 i.e. best algo * - - - - - 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.