Chef and Segments

general
, , , ,
1

This is the link to the question:

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.

2

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.

3

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

1 Like