last day (111 days later) » 

11:48 AM
-1
Q: Counting sort, problem giving error, iterative,

V_headI am having a c++ implementation of the counting sort algorithm. I try to send it to our university's online judge, and it gives time limit error. The input output is as follows; Input: The first line contains a natural n – the quantity of elements in an array n (1 ≤ n ≤ 10000000), then n elem...

 
Post the error the online judge is giving.
 
It doesn't give it. It says only run time error 30. That means for input 30, this happens.
 
Well, in that case I'll test your code but it's bed time in my timezone so it's going to be tomorrow. Can you wait?
 
First, use constexpr instead of #define. Second, please try to avoid using namespace std; because it is considered bad practice. See Why is “using namespace std;” considered bad practice? Third, never redirect stdin and stdout without a good reason. Fourth, use a proper container like std::vector instead of raw new. Fifth, use standard algorithms instead of the hand written loops. And that's not the end ...
 
@L.F. First, isn't that a standard algorithm?!, I ve used define, namespace, stdin, stdout for all previous tasks, they require such practice.
@JavierSilvaOrtíz, yeah, isn't that the standard counting sort algorithm?
 
11:48 AM
No, you aren’t using a single standard algorithm in the code. You didn’t even include the <algorithm> header. As for “they require such practice”, that’s just like a math prof requires you to set 1 + 1 = 3. I know way too many teachers are teaching bad C++ practice around the world, but that’s not an excuse.
 
@L.F. You are right, but I ll use for my code. For the online judge I ll do this.
 
Sorry, then I can't help you learn C++.
 
@L.F. I see. You see they even ask us to visual studio 2015 :( Don't take it on me.
 
OK, then please first resolve the basic problems (#define, using namespace std;, etc.)
 
When your "for" loop is just a one-liner of 1 statement, you don't need to enclose that line in {}. Also, your problem looked like it came from codeChef :).
 
11:48 AM
No, it didn t. But why it should give a run time error?
 
@KevinNg One doesn't need - but it's good practice, and there are many coding guidelines (e. g. MISRA, both for C and C++) mandating placing braces. That avoids trouble if e. g. a seeming function actually is a macro containing more than one expression or avoids bugs by simply forgetting to place braces if the body is extended later.
@V_head About the re-directing of std:cin/std::cout: std::ifstream in("input.txt"); if(in) { std::ofstream out("output.txt"); if(out) { /* now use in/out instead of std::cin/std::cout */ } } (or similar) would actually be the way to go. Automatic test tool pretty sure won't inspect the generated machine code, so it wouln't ever recognise. At best, prof might spot in code review, but if she/he complains, send her/him to here to let us discuss...
Is the input array required by the task? For the algorithm itself, you don't need it: for (i = 0; i < n; i++) { int m; in >> m; ++count[m]; } (I'm using the std::ifstream proposed above) would read in the counts in one single loop run. Similarly, you can drop the output array and just write to file directly; You can do it much simpler if you use a double loop (proposing a range-based for loop here): for(auto m : count) { while(m--) { out >> m >> ' '; } } (if task requires the output array: int pos = 0; for(...) { while(...) { out[pos++] = m; } }).
 
Can someone help, I am blocked to ask other questions. Could you rate this question as good. Thanks. @Aconcagua, the program gives time error when I changed what you suggested.
 
@V_head Have been inattendent anyway (sorry), of couse, we don't want to output the counts, but the values, so we need a separate counter: for(int m = 0; m < RANGE; ++m) { for(int k = count[m]; k; --k) { std::cout << m << ' '; } }
 
@Aconcagua I ve updated the code. I think I am implementing the right counting sort algorithm. Now it gives time limit error. Is there an optimized counting sort algorithm?
 
Try dropping those unnecessary arrays. Allocating them might be what costs you too much time.
Why are you adding the counts of the predecessors to current values? That's totally irrelevant.
 
11:48 AM
@Aconcagua, what do you mean? How can I do it? I find them all necessary, no?
 
What did you intend with count[i] += count[i - 1]; inside the loop??? Next loop looks very confusing as well...
The complete algorithm only consists of: for (int i = 0; i < n; i++) { int m; in >> m; ++count[m]; } for(int m = 0; m < RANGE; ++m) { for(int k = count[m]; k; --k) { out << m << ' '; } } – especially: no arrays a or out needed.
 
Hi, Yeah, here is the code, cpp.sh/5ppyt
This is about binary search, I feel its the right algorithm.
 
Why did you switch to long long? The ranges requested fit into 32-bit integers, if you feel int might have less than 32 bits, long would be fine already. Or: use int32_t (exactly 32 bit) or int_fast32_t (fastest type having at least 32 bit) from <cstdint> header.
Wait a second, this is a totally new problem???
 
Oh, I didn't do long long first, it failed, I though maybe there is some big numbers, then it failed so it fails in both cases.
Yes, it is I just felt instead of asking it on stackoverflow, if you can help since you re available.
 
12:07 PM
Hm, OK... We can assume input is sorted, can we?
 
Yes
 
And problem now is which?
 
It is that it fails the first test case, which is not shown. So I have to speculate, it tried every input it works
If you can spot something?
 
Any hints about what fails?
 
No, input goes like this, n, n numbers, k number to be found.
 
12:16 PM
Input is clear... But: std::cout << m + 1; – so you are supposed to output 1-based index? Pretty unusual...
 
Yes
Yeah, but they require such.
 
And still -1 is required for elements not found?
 
yes
 
Point is, algorithm looks fine. What I could imagine, though, is a problem with duplicates. Are you possibly required to find first or last occurence?
 
right, it seems to be the first one
But I can't know, the algorithm spots the first one. I think i ll be a bit silly to ask for the second one.
 
12:24 PM
The algorithm spots any element. Imagine you have an array with all elements the same. It would find the one in the middle then.
The simplest fix would be just counting back from the element found until predecessor is unequal. But actually, that would break O(log(n)), imagine the all equal elements array again, you'd iterate over n/2 elements.
 
yeah, I get it. That's why I think that is not required since they specify it is done in O(log(n))
 
Actually, you only need a minor fix:
while (l <= r)
{
    long long int m = l + (r - l) / 2;
    if (a[m] < k)
    {
        l = m + 1;
    }
    else
    {
        r = m - 1;
    }
}
This way, you don't care for k having been found already, you just go on until r got smaller than l.
Now at the very end, there are two options:
1. you found the very first occurence of k, located at a[l]
2. you didn't find the element at all
So one additional check gives you the solution:
a[l] == k ? l + 1 : -1
 
12:42 PM
Thanks, I ll try and reply to you
 
 
2 hours later…
2:22 PM
Hi, they had some problem with the task, they updated, now, it works! Thanks
 
You're welcome...
 
Thank you, is it possible I get your email or something. I am studying software engineering in Russia, and sometimes get stuck or not find good stackoverflow help. I come from a country where it is normal for us to ask someone for such things even if we don't know each other, it's Morocco :) If it's not possible, I understand, Thanks again :)
 
3:14 PM
Sorry, for privacy reasons, I don't give out e-mail addresses easily. But you can invite me to chat any time you have a problem...
 
3:33 PM
Absolutely, It's like you game your email :) Thank you so much
 
3:54 PM
Since I still don't have 20 reputation, I can't create a chat. So, I'll poke here so you can create a chat room until I get 20 reputation, is that Ok?
 
 
6 hours later…
9:49 PM
Sure, that's fine...
 

  last day (111 days later) »