# Why tle in this question (COINS)

Youâ€™re recursively passing an array, make dp global instead.

array will be passed by value or reference?

This probably doesnâ€™t make much difference - a parameter that is a C-style array is in reality a pointer, and passing a pointer around doesnâ€™t slow things down much.

Of much more concern is that the OP is trying to create and initialise a dynamic array of length N, where N can be as high as 10^9. And to do so up to 10 times, too.

1 Like

so whats the solutionâ€¦
accepted solution have created array using new â€¦How will that make a difference?

1 Like

The difference is allocation on the stack vs allocation on the heap - the heap is usually larger. Iâ€™m surprised you got a TLE instead of a RE.

1 Like

but the max size of array allocated in heap is also in 10^7â€¦so how 10^9 problem will be solved

Is it?

I have absolutely no idea how the solution you linked manages to pass, to be honest - if the testcases are as strong as the constraints suggest, it should eat up about 8GB RAM per testcase. And since it doesnâ€™t de-allocate memory, it should in total use up about 80GB XD

Anyway, I suspect that the â€ś`dp`â€ť â€śarrayâ€ť will be quite sparse, so probably a `std::map` would be more efficient.

2 Likes

but the max size of array allocated in heap is also in 10^7? is this wrong ?

Depends on the type of the array and the largest contiguous block of RAM available. I donâ€™t know how much RAM Codechefâ€™s Online Judges provide to programs.

On my laptop, allocating an array of 10^8 `int`s on the heap is easily possible.

1 Like

so what the max size in stack? is that also depends on type of the array and the largest contiguous block of RAM available

Depends on Codechefâ€™s stack limits I donâ€™t know, but itâ€™s very probably less than the heap.

1 Like

every accepted sol have declared it with new but when i declare it globally it is giving sigsegv error.why

so this limits will be different in other sites like codeforces.

Iâ€™m sorry but even I need to ask a question. The question doesnâ€™t tell you how many test cases we have, so how do we know when to stop?

Keep reading `int`s until we eof; e.g.

``````int numCoins;
while (cin >> numCoins)
{
// ... compute largest dollars ...
}
``````
3 Likes

Thanks I got it right

2 Likes

Probably

Weâ€™d really need to get some hard numbers on all of them.

2 Likes