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

×

Alternate way of storing data of array size 10^9

My program is giving runtime error when i exceed my array size beyond 10^7 , can anyone help me to solve this issue :)

asked 15 Nov '15, 11:40

chaman_amit's gravatar image

1★chaman_amit
871413
accept rate: 0%

edited 15 Nov '15, 11:40


Then you should find another algorithm for the problem. You may consider the following things:

  1. The array of size 10^9 takes 100 times more memory than 10^7 size array. Considering it an int array, this array alone will take memory of around 3800MB. Most problems do not allow this amount of memory.

  2. Even if you're able to declare an array of such great size, You won't be able to apply a linear time algorithm in many of the problems as it will probably exceed the time limit.

  3. To get a hint of the approach, you can look at other solutions' memory and execution time.

  4. If the required array in the problem requires such an array, but it would be sparsely filled, then you may consider hashing.

link

answered 15 Nov '15, 12:14

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

edited 15 Nov '15, 12:14

1

If it is a contest problem, remove the solution link as soon as possible!

As for the approach, you'll find much smarter solutions, once the contest ends. (:

(15 Nov '15, 12:48) xariniov96★

Got ur idea i ll try finding some other approach :)

(15 Nov '15, 12:59) chaman_amit1★
1

In your situation, point number 3 will surely help you out

(15 Nov '15, 13:08) xariniov96★

okk @ xariniov9

(15 Nov '15, 13:17) chaman_amit1★

i found others are also doing the same mistake and got 25 points but in next 4 minutes they got 100 points , how can they do this :p

(15 Nov '15, 13:20) chaman_amit1★

Got it complexity will be O(1)

(15 Nov '15, 13:21) chaman_amit1★
showing 5 of 6 show all

i think you are trying to solve EGRKAKE..you can do it with very simple trick...now recognize that TRICK by your self

link

answered 15 Nov '15, 13:12

shibli786's gravatar image

2★shibli786
723
accept rate: 7%

Declare array as global i.e. before int main().

link

answered 15 Nov '15, 12:56

dushsingh1995's gravatar image

4★dushsingh1995
98314
accept rate: 11%

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:

×3

question asked: 15 Nov '15, 11:40

question was seen: 518 times

last updated: 15 Nov '15, 13:59

Related questions