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

×

Chef and Segments

This is the link to the question: http://www.codechef.com/problems/CHMOD

My final solution (WA shown) http://www.codechef.com/viewsolution/3447265

I implemented this. However, I kept getting Time limit crossed. So I went through the tutorial. I saw that I had followed more or less whatever they did, just that I didn't use the cumulative prime factorization scheme so we could get the prime factorization of a segment in O(1) time. So I tried implementing what they did. Now the problem occurring is:

  1. If I declare the cumulative array as: int A[N][25] Then there are no storage problems. However, say if the input was N=100,000 and all inputs were 64, then the cumulative frequencies for 2 would be (6*100,000)=600,000, which would not fit in an int array.

  2. If I declare it as: long int A[N][25], then such an array cannot be initialized as it takes too much space.

Anyways, I'm getting shown as WA. Have I identified the problem correctly? If yes, how to go about it then? If no, could you help me find the problem?

Any help would be greatly appreciated. Stuck for quite some time.

This question is marked "community wiki".

asked 20 Feb '14, 19:09

s1d_3's gravatar image

5★s1d_3
165413
accept rate: 20%

If N=600000, the second array should have around 57 MB, because long int is the same as int. That should fit into any general memlimit (unless you're COCI with stupid 32 MB limits), but it could theoretically overflow stack size. In that case, using vector<>s is better.

(20 Feb '14, 19:37) xellos07★
1

declare the array globally...let the array be on heap...if the size is too large...maybe this will help..:)

(20 Feb '14, 21:33) kunal3614★
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:

×1,070
×862
×477
×107
×23

question asked: 20 Feb '14, 19:09

question was seen: 1,483 times

last updated: 20 Feb '14, 21:33