The Full Counting Sort
The Full Counting Sort
+ 38 comments I did a simple, efficent and yet understandable solution in C++. I hope it's useful for you guys
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { long int n; cin >> n; string ar[n]; for(long int i = 0; i < n/2; i++){ int x; cin >> x; string s; cin >> s; ar[x] = ar[x] + "-" + " "; } for(long int i = n/2; i < n; i++){ int x; cin >> x; string s; cin >> s; ar[x] = ar[x] + s + " "; } for(int i = 0; i < n; i++) cout << ar[i]; return 0; }
+ 20 comments I learnt three big things from struggling with test #5 in Java: 1. StringBuilder, don't underestimate how important it is when working with Strings; 2. IO is slow, minimise where possible; and 3. Really think about the the aspects that contribute the most to overhead/performance and not try small things which take a lot of time and result in small/negilible gains.
Thank you for this challenge!
+ 1 comment i didn't understand the question can anyone explain in simple words plz..
+ 10 comments I was having problems with testcase #5. Then I realized that I was using Console.WriteLine inside the loop, and this is VERY slow, specially for 1M entries. So, I used a StringBuilder and printed everything in the end. I went from more than 3s to 0.89s. The problem is not always with your algorithm, but it may be with the way your are printing.
+ 5 comments For Java submissions, having
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
and then using something like
String[] tmp = in.readLine().split(" "); int x = Integer.parseInt(tmp[0]); String s = tmp[1];
instead of normal Scanner nextInt(), next() methods cuts processing time in half.
For testcase #5 my submission times were:
- Success 3.97s (using Scanner and doing
System.out.print(s + " ");
) - Success 2.21s (using Scanner and using
StringBuilder
for output) - Success 1.03s (using the
BufferedReader
method shown above)
Either way if the implementation really is good the test should pass independent of using Scanner and System.out.print for each of the items
- Success 3.97s (using Scanner and doing
Sort 642 Discussions, By:
Please Login in order to post a comment