You are not logged in. Please login at www.codechef.com to post your questions!

×

MLE in Codeforces Round 442-D

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 :)

asked 03 Nov '17, 00:22

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%


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.

link

answered 03 Nov '17, 21:16

therisingsun's gravatar image

4★therisingsun
3864
accept rate: 40%

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!

(04 Nov '17, 00:59) dishant_184★

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.

(04 Nov '17, 02:39) therisingsun4★

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

(04 Nov '17, 10:53) dishant_184★
(04 Nov '17, 10:57) dishant_184★

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

(04 Nov '17, 17:43) therisingsun4★
1

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 :)

(04 Nov '17, 22:48) dishant_184★

Glad that I could be of some help. :)

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

(05 Nov '17, 23:01) therisingsun4★

Thanks for the help again :)

(06 Nov '17, 00:05) dishant_184★
showing 5 of 8 show all

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

link

answered 03 Nov '17, 12:15

pandey_96's gravatar image

1★pandey_96
667
accept rate: 0%

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.

(03 Nov '17, 14:34) dishant_184★

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

link

answered 04 Nov '17, 00:57

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×688
×107

question asked: 03 Nov '17, 00:22

question was seen: 423 times

last updated: 06 Nov '17, 00:05