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

×

please tell me the fault in this solution. I'm getting SIGABRT error.

asked 11 Jul '17, 16:48

daksh_3108's gravatar image

1★daksh_3108
1
accept rate: 0%


You are using too much memory.

In the question, N can be upto 10^9. So, an array of N (64-bit) integers would take 64 * N bits, which is equal to 7.45 Gb (almost). This is a lot of memory for a single program.

One thing to notice is that in the above question, we don't need all the indices. So, a better way will be to use a map.

You can see my solution for reference.

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

link

answered 11 Jul '17, 17:12

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

edited 11 Jul '17, 17:19

If you WANT to solve it using array, then its possible. You just need to make an observation that lesser value of N are more frequently used.

Meaning, assuming we have stored all ans for N upto 10^9, you may not use N=10^8 a lot, but you will be using N=2,10,100 etc. much more. Why? Because smaller values will come in handy when you get a LARGER number, which breaks down to use the N.

Just make some cases and a recursion tree, and see which values of N are getting repeated alot. Once you come to agree that smaller Ns are more important than larger N, then its simple.

Declare an array of size 10^7, and store the result if N<=10^7. You can afford multiple same recursions for values between 10^7-10^9, if you are able to answer smaller numbers in O(1) time via memonisation.

Also, in this process of division, greater the number, faster it decreases and lesser the recursion calls it takes. Smaller numbers take more time/calls .

For example, if we constantly divide by 2,

100/2=50 . Difference of 50. 10/2=5. Difference of only 5. 10 times slow than above example.

link

answered 11 Jul '17, 19:30

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12065
accept rate: 18%

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,165
×345
×65
×64

question asked: 11 Jul '17, 16:48

question was seen: 299 times

last updated: 11 Jul '17, 19:30