Here is my first and second solution for this problem.
The only difference in these two solution is, former have an array ifact[3000000] (which i didn’t use) and later don’t.
First code has nothing to do with this ifact[] array, i just merely declared it, so to reduce memory i removed ifact[] from second one. But my first solution got accepted and second got runtime error
please tell me what is wrong with second code, i have no idea 
result of grep ifact first.c
ull ifact[3000000];
//ifact[0] = 1;
//ifact[i] = mod(ifact[i-1]*ppow(i,m-2));
Below is result of diff command on these two file :-
8,9d7
ull fact[3000005];
ull ifact[3000000];
11a10
ull fact[3000005];
59d57
//ifact[0] = 1;
63d60
//ifact[i] = mod(ifact[i-1]*ppow(i,m-2));
can somebody explain this ‘memory’ thing one should keep in mind while solving these kind of problems. I mean, can anybody just give a clear picture of where to declare large arrays? Also, when you submit a solution on codechef and get accepted, It shows some number under Memory consumed.
What does this number actually account for …?
I actually don’t know clearly on what basis the number under memory consumed shows but to declare large arrays either declare it globally or you can use malloc to declare arrays. These allocate memory on heaps instead of stack and allows larger size of array declaration.Generally you can declare in the order of 10^8 using malloc or defining it globally
@dawnavd >> This is an example of Undefined Behavior. It is possible that there is some out of bound access to the seg[] array, when the unused array ifact[] is there, then seg[] array overwrites the contents in the ifact[] array, and hence the original array while computation is not affected and the answer is correct. But when you remove the ifact[] array, then seg[] array overwrites to its own indices or then it again experiences out of bound access, and hence throws a Runtime Error.
My Conclusion: Some function might be the suspect from my intuitions, and the test data is possibly trying the out of bound access, which translates to an RE when the unused array is deleted.
Either the setter/tester of the problem can confirm it, or some C++ genius like @anton_lunyov himself.
@sumanth232 >> Anywhere you wish, as far as you know that you’ll not be having any out of bound access.
EDIT: It was not the fact[] array which was going out of bound, but it was seg[] array, as pointed correctly by @cyberax. Hence updated my answer.
1 Like
@bugkiller but how on earth fact[] is overwriting the content of ifact[] 
When there is an Undefined Behavior, then you can’t really be sure about how your program will behave, and the program behaves ill. You were lucky that your program worked, I would say. In the cases like this, out of bound accesses, anything is possible and it might or might not be explainable for me, as I am not a pro.
i have a test case here that makes your second code generate a segfault. i’ll investigate, and come back to explain.
ull fact[3000005];
ull ifact[120981];
is fine,
ull fact[3000005];
ull ifact[120980];
segfaults. it’s kinda strange…
valgrind tells me there is something wrong too in make_tree.
EDIT: i think i found something.
please add an assert(x >= 0 && x < 20000); in the conditional block in make_tree.
in my opinion, you’re doing an heap overflow. removing the ifact array reveals the fact you’re trying to access memory out of the seg array bounds. with the ifact array declared, you’re providing your program an extended area to store values. without it, it simply crashes.
just increase the size of the seg array, let’s say 500000, and it does not crash anymore.
4 Likes