MLE in Codeforces Round 442-D

help
, ,
1

Hii guys!
I was solving this problem and saw my solution gets MLE. I don’t understand why and when I looked at some other solutions, they had the same space complexity(unless I missed something). Here’s my solution : Link.
It would be great if anyone can help me figure out why am I getting an MLE.
Thanks in advance :slight_smile:

2

This error occurs due to large size of array or data structure and you try to allocate memory beyond the memory limit.

3

Yup I know that. But I don’t think my code allocates memory beyond the memory limit. I have seen AC codes with similar memory allocation.

4

Hey @dishant_18

The default memory taken by queue is 80 bytes. And you are adding pair in that queue, which can exceed the maximum allowed memory of the question ie 256MB. queue is a heavy data structure(memory wise), you might need to optimize your memory used.

You can have a look at this example for further explanation.

1 Like
5

Thanks for the reply @therisingsun :slight_smile:
Can you pls tell me why do (i) and (ii) solutions get AC? They too are doing the same I guess.

6

Hii…I don’t know how to use link in reply so I have posted an answer regarding your reply. It would be great if you can clarify it to me.
Thanks!

7

One basic difference that I see between the other two code and your code is that, you have declared the size of the array before taking the input values of n and m. On the other hand, the other two codes firstly take the input values and then declare the array of those size accordingly. You are declaring a[2000][2000] even if you might only be needing lesser number of entries. This can optimize your code memory wise.

8

I tried that!! It doesn’t work for me yet ;_;

9

Here’s the link : http://codeforces.com/contest/877/submission/32003439

10

Can you try this solution as well. https://ideone.com/vB3Iqu
Just added a new check to avoid adding certain entries in the queue.

11

Wow it did pass!!! Just had to change initialization from 1e5 to 1e7!
Can you tell me what prevented my solution from getting AC??
Btw here’s the link: http://codeforces.com/contest/877/submission/32059353 Thank you so much :slight_smile:

1 Like
12

Glad that I could be of some help. :slight_smile:

Just try dry running your code for this input. You will see that you were adding some of the numbers that were already added in the queue. The added check restricts them from adding already added number which should not be added.

3 3 4
…
…
…
1 1 3 3

13

Thanks for the help again :slight_smile: