Why tle in this question (COINS)

general
1

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

2

You’re recursively passing an array, make dp global instead.

3

array will be passed by value or reference?

4

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
5

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

6

Link?

1 Like
7

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

8

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
9

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

10

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
11

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

12

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
13

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

14

Depends on Codechef’s stack limits :slight_smile: I don’t know, but it’s very probably less than the heap.

1 Like
15

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

16

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

17

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?

18

Keep reading ints until we eof; e.g.

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

Thanks I got it right :grinning:

2 Likes
20

Probably :slight_smile:

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

2 Likes