xlm 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!
sandygunner Brilliant!
rohil93 Thanks a ton buddy!
lk00100100 [deleted]onlysumon Great!! I want to add one more-
4. Scanner is slower than BufferedReaderJBeUy I am totally agreeing with you!
skur42 I tried StringBuilder for the first time and its very useful.
qihaoxa Appreciate to you, I doubted my algorithm was not fast enough when I got a fail on test#5, when I tried StringBuffer, it works! I used StringBuffer before, but I really don't know it can be faster so much, thanks again!
tmwilliamlin168 Yeah StringBuilder/StringBuffer allowed me ot pass test case #5
ishita_ghosh its not working for me. i dont understand
kksant StringBuilder and Single sysout did the trick for me
Thank you
avi_bpgc Thanks a lot buddy!!
nkenzhebekov StringBuilder instead System.out.println(str); helped a lot!
shubham_sawlani1 Thanks bro .Learnt using StringBuilder class with the help of this question.
pdixon555 StringBuilder, to the rescue! I never used it before but it made all of the difference for test case #5. Thanks for this.
Tanisha23 It worked for me..!!Thanks a ton :)
RAHUL_KUMAR21 Thanks Man Stringbuilder help to pass the 5th test case
hooni Thanks for your help. Managed to pass #5 after using stringbuilder.
What do you mean by "IO is slow" though. What exactly can we improve?
masonite Thanks for the tip. I have to say, the point of this exercise is not to optimize for string concat or io, so I think the exercise should be modified or at least documented to address this. Thank god for smart commenters!
dsinghiitp Yup, realized the same (coding in c#). However, using a 100 sized array of StringBuilders, not sure what else can be the alternative (nothing times-out now though).
davideoguche Thanks for this hints!!
marioquiroga2912 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; }
WeirdCoder @singhabhinandan see this code..try to learn how this works...this code is awesome . thanks @marioquiroga2912 for this brilliant piece of code.
marioquiroga2912 Thank you @WeirdCoder
vedantsg4 @marioquiroga2912 Just brilliant !! But you are not doing what it says to do. You are just appending the strings in the order they appear at their poisitions(which is a great idea though), here we have been told to implement counting sort. So I implemented it, but my 5th test case is failing(Seg fault), which i think is due to memory limits. i have used 3 arrays of size n(1<=n<=1000000), help please! Here's my submission link mySubmission
vedantsg4 @marioquiroga2912 Just one correction, since all x(keys) are between 1 to 100. You don't need to allocate string ar[] of size 'n', 101 is enough and hence the limit of last for loop would also change.
rocketmannot Thank you for great solution. I think string ar[n]; - array size of 100 is enough.
shashwat_dhanan1 brilliant
bachhal nic answer
anshul_4ggarwal You are truly an amazing guy !
jain_cj_chetan there is still segmentation fault in test 5
sadeghi_misha really brilliant
sadeghi_misha really birilliant
adk96r Superb ! Everyone who has commented here (including me) has been like :
sasebot legend
tiagocrb87 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.
zhenyiluo You are right!
littleninja There's a "catch 22": Testcase #5 aborted so I downloaded the testcase, but I can't test changes due to the max size constraint on the custom input.
abhiranjan Hi @littleninja, your error is caused to SIGABRT. Quoting this so:
_`abort()` sends the calling process the SIGABRT signal, this is how `abort()` basically works._ _`abort()` is usually called by library functions which detect an internal error or some seriously broken constraint. For example `malloc()` will call `abort()` if its interal structures are damaged by a heap overflow._
chauhan_himanshu welcome to shitty hackerrank
aparkerkes Also have an issue with #5. My algorythim runs in 1.1s with a string object, printing the string with Console.WriteLine on the string makes it take over 4 seconds. How do you get down to 0.89s when it takes over 3s just to print the string?
e_cazarez Build the string and use just one call to Console.WriteLine
allali_elkhalili thanks man, thats helped me :)
sortedletter Thanks, that helped me.
mariia_iurchenko I had the same issue. Thanks for the hint!
furkanakcay This is the point!
noormahdi Thanks. I was facing the same issue, but now by using StringBuilder i was able to clear the 5th test case :)
cheks54 Yes for me too StringBuilder did work wonders. effects of slow I/O was felt for 1M numbers
mihaiile 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
StringBuilderfor output) - Success 1.03s (using the
BufferedReadermethod 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
vickybiet Yes You are right,Thank you
RodneyShag Thank you. Your post was very helpful. I tried all 3 methods you said. Here were my runtimes for testcase #5:
1) > 4 seconds. Failed testcase #5
2) 2.28 seconds
3) 1.11 seconds for this final code
go_st_go Thanks for the great info mihaiile!
I have 2 questions regarding your comment:
What is the reason for this big performance difference between BufferedReader and Scanner?
How did you come up with the time? How did you measure it?
Thanks a lot!
rss_ricardo It's also possible to use BufferedReader keeping Scanner. Using this, it passes in all test cases and you need smaller changes:
Scanner in = new Scanner(new BufferedInputStream(System.in));
thedailynathan Thanks, a little ridiculous this question about sorting requires modifying the template code.
- Success 3.97s (using Scanner and doing
rarunkumar451 i didn't understand the question can anyone explain in simple words plz..
chinmayp Can I do better than this in C? It passes all testcases, the last one in 0.38s, but I would like to know if there's a better way of doing it. Any suggestions would be appreciated.
int main() { int n=0; scanf("%d",&n); int *arr = (int*)calloc(100,sizeof(int)); //For implementing counting sort int *input = (int*)calloc(n,sizeof(int)); //For storing the input integers char **strings = (char**)calloc(n,sizeof(char*)); //For storing the input strings for(int i=0;i<n;i++) strings[i]=(char*)calloc(10,sizeof(char)); int num=0; for(int i=0;i<n;i++) { scanf("%d",&num); input[i]=num; arr[num]++; scanf("%s",strings[i]); } for(int i=0;i<100;i++) { int j=0; while(arr[i]>0) { while(input[j]!=i) //Find the number in input list j++; if(j<n/2) printf("- "); else printf("%s ",strings[j]); //print corresponding string j++; //Increment j to find other instances further ahead in input arr[i]--; //Decrement count } } return 0; }
snikketysnake I got 0.28 seconds on testcase #5 with this implementation. This one creates linked lists for keeping the stable ordering. This way you don't have to search the original input array in order:
#include <stdio.h> #include <malloc.h> struct count_elem { int count; struct elem *first; struct elem *last; }; struct elem { int idx; char str[11]; struct elem *next; }; int main() { int ni, nc=100; struct elem *ai; struct count_elem *ac; int idx; int i; struct elem *elem; ac = calloc(nc, sizeof(struct count_elem)); scanf("%d", &ni); ai = calloc(ni, sizeof(struct elem)); for (i = 0; i < ni; i++) { scanf("%d %s", &idx, ai[i].str); ac[idx].count++; ai[i].idx = i; if (ac[idx].first == NULL) { ac[idx].first = &ai[i]; ac[idx].last = &ai[i]; } else { ac[idx].last->next = &ai[i]; ac[idx].last = &ai[i]; } } for (i = 0; i < nc; i++) { elem = ac[i].first; while (elem) { if (elem->idx < ni/2) printf("- "); else printf("%s ", elem->str); elem = elem->next; } } printf("\n"); return 0; }
helena_50010 Is this counting sort?
Zodiac99 I realy liked it...smart coding.
namankumar821310 can you plz explain what is wrong in my code, it is showing segmentation fault.
include
int main() { int n; scanf("%d",&n); int arr[n]; char ar[n][10]; int x[100]={0}; for(int i=0;i0) { while(arr[j]!=i) j++; if(j
insane84 This solution works better than the other solutions discussed here.
import java.util.Scanner;
public class Solution {
public static void main(String[] args) { Scanner scan=new Scanner(System.in); int size=Integer.parseInt(scan.nextLine()); StringBuffer[] st=new StringBuffer[100]; for(int i=0;i<100;i++) { st[i]=new StringBuffer(); } for(int i=0;i<size;i++) { String sts=scan.nextLine(); String[] str=sts.split("[\\s]+"); int k=Integer.parseInt(str[0]); String s; if(i<size/2) s="- "; else s=str[1]+" "; st[k]=st[k].append(s); } for(int i=0;i<100;i++) { System.out.print(st[i]); } }}
Mirrage quite a elegant solution
revengeCoder should've used "int size=scan.nextInt();" instead
adrita_borkakot1 If anyone is looking for a solution. this is it.
abehjat Simple to read Python solution
n = int(raw_input()) num_dict = {} maxNum = 0 for i in xrange(n): x = raw_input().strip().split() numX = int(x[0]) linX = x[1] if i < n/2: linX = "-" if numX > maxNum: maxNum = numX if numX in num_dict: num_dict[numX].append(linX) else: num_dict[numX] = [linX] output = [] for i in xrange(maxNum + 1): if i in num_dict: for line in num_dict[i]: output.append(line) print " ".join(map(str,output))
Woj_Swiderski ok, but by replacement linX = "-" you are losing original strings from input.
abehjat Ah! Good point. I could set up two list variables (one stores the original array, and the other contains the modified array)
jessachandler It's okay because "that's what the client wants" - I created a second list variable with "-" if i < n/2, but I don't think it was necessary because the original list is never used.
miten_solanki Great Solution
Argooni n = int(input()) ar = [] for i in range(n): if i < n//2: numX, striX = input().strip().split() ar.append((int(numX),'-')) else: numX,striX = input().strip().split() ar.append((int(numX),striX)) ar.sort(key=lambda tup: tup[0]) print(*[x[1] for x in ar])
yerbolat102 brilliant code
aleksei_maide arent you supposed to use counting sort in the "challange"?
chlamb16 def counting_sort(list): min = list[0][0] max = list[0][0] for i in range(1,len(list)): if list[i][0] < min: min = list[i][0] if list[i][0] > max: max = list[i][0] diff = max - min count = [0] * (diff+1) for i in range(len(list)): count[list[i][0] - min] += 1 for i in range(1,len(count)): count[i] += count[i-1] output = [[]] * len(list) for i in range(len(list)-1,-1,-1): output[count[list[i][0] - min]-1] = list[i] count[list[i][0] - min] -= 1 for i in range(len(list)): list[i] = output[i] n = int(input().strip()) list = [] for i in range(n): m = input().strip().split(' ') m[0] = int(m[0]) if i < n // 2: m[1] = "-" list.append(m) counting_sort(list) output = "" for i in range(n): output += list[i][1] + " " print(output)
AffineStructure This code is good. Although, you should not name objects the same as restricted keywords in python, such as 'list'
scandium good code . but y is it giving runtime error here
GeoMatt22 Nice solution!
A more concise (but perhaps less clear?) Python 3 translation might be:
from collections import defaultdict n, A = int(input()), defaultdict(list) for i in range(n): ind, str = input().split() A[int(ind)].append('-' if i < n/2 else str) print(*map(' '.join, A.values()))
Anubhav_singh Awesome code though. slight improvisation in output part.
n=int(input()) d={} maxnum=0 for i in range(n): num,str_=map(str,input().split()) num=int(num) if i<n/2: str_='-' if num>maxnum: maxnum=num if num in d: d[num].append(str_) else: d[num]=[str_] for i in range(maxnum+1): print(' '.join(d[i]),end=' ')
Sakshi_Parashar Hey, this is a cpp solution. Passes all the test cases.
int main() { int n; cin >> n; vector<int> arr(n), hash(100); vector<string> s(n); string out = ""; for ( int i = 0 ; i < n ; i++ ) { cin >> arr[i] >> s[i] ; for ( int j = arr[i] ; j < 100 ; j++ ) { hash[j]++; } } for ( int i = 0 ; i < 100 ; i++ ) { if ( hash[i] > 0 ) { for ( int j = 0 ; j < n ; j++ ) { if ( arr[j] == i){ if ( j < n/2 ) { out += "- "; } else { out += s[j] + " "; } } } } } cout << out; return 0; }
prachi_1312 [deleted]
jhabbott Swift: No spoilers of the solution here, I just give some tips on how to optimise reading the input in Swift.
Reading input and general string manipulation in Swift can be pretty slow if you use the standard/normal techniques. You may struggle with Test Case #4 and almost certainly will time out on #5.
So, for Test Case #5...
I tried various experiments and reading the input alone takes 0.48s with this code:
let size = Int(readLine()!)! for i in 0 ..< size { let line = readLine()! }
Adding in the standard "Foundation" way to process this into an
Intand aString, like this:let size = Int(readLine()!)! for i in 0 ..< size { let line = readLine()! let comps = line.components(separatedBy: " ") let x = Int(comps[0])! let str = comps[1] }
...with no other code times out (>2s at time of writing). So unfortunately just getting the input is too slow using this technique. Another way to process the
linestring into anIntandStringis this:let (x, str) = line.withCString { (cStr: UnsafePointer<Int8>) -> (Int, String) in let x = Int(atoi(cStr)) let pSpc = strchr(cStr, 0x20)! let str = String(validatingUTF8: pSpc + 1)! return (x, str) }
...and this now takes 1.09s.
This should be enough for you to solve the rest by yourself, but I will just point out that it took 1.41s to read the input plus the processing for the algorithm alone (no output) using the above code. My final solution took just 1.16s because I optimised away unnecessary code from the
withCStringclosure above as well. Without that optimisation you will be sailing pretty close to the 2s time-out.
witekbobrowski Very usefull info! Couldnt pass the challenge, but after taking your advice i have passed all tests! Thank dude.
Sort 340 Discussions, By:
Please Login in order to post a comment