Why tle in this question (COINS)

https://www.codechef.com/viewsolution/29922165

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?

Link?

1 Like

https://www.codechef.com/viewsolution/29010526

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 ints 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 :slight_smile: 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 ints until we eof; e.g.

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

Thanks I got it right :grinning:

2 Likes

Probably :slight_smile:

We’d really need to get some hard numbers on all of them.

2 Likes