1

My question is very general..and its not duplicate too..

when we declare something like this int mat[1000000][1000000];

it is sure it will give an error saying matrix size too large.

i have seen many problems on many competitive programming websites where we need to declare a 2d matrix with 10^6 rows, columns ,I know there is always some trick associated with it to reduce the matrix size.

so i just want to ask what are the possible ways or tricks we can use in such cases to minimize the size ..i mean which types of algorithms are generally required to solve it like DP or anyone else??

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
Shubham Gupta
  • 227
  • 2
  • 9
  • 1
    Sparse arrays. http://stackoverflow.com/questions/4306/what-is-the-best-way-to-create-a-sparse-array-in-c – Matthew Watson May 06 '14 at 10:15
  • 2
    Are you sure these problems ***have to be*** solved using arrays? – UmNyobe May 06 '14 at 10:21
  • 2
    On a "competitive programming website" the guys probably expect you to find a way to solve the problem _without_ using an array that would need four terabytes of memory. That's what makes it competitive :-) – gnasher729 May 06 '14 at 10:30

2 Answers2

3
  1. In DP, if current row is dependent only on previous row, you can use int mat[2][1000000];. After calculating current row, you can immediately discard previous row and switch current and previous.
  2. Sometimes, it is possible to use std::map instead of 2D array.
  3. I have encountered many question in programming contests and the solutions defers from case to case basis, so if you mention a specific case, I can possibly give you a better targeted solution.
Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
3

That depends very much on the specific task. There is no universal "trick" that will always work. You'll have to look for something in the particular problem that allows you to solve it in a different way.

That said, if I could really see no other way, I'd start thinking about how many elements of that matrix will really be non-zero (perhaps I can use a sparse array or a map (dictionary) instead). Or maybe I don't need to store all the elements it memory, but can instead re-calculate them every time I need them.

At any rate, a matrix that large (or any kind of fake representation of it) will NOT be useful. Not just because you don't have enough memory, but also because filling up such an array with data will take anywhere from several hours to many months. That should be your first concern - figuring out how to solve the task with less data and computations. When you figure out that, you'll also see what data structure is appropriate.

Vilx-
  • 104,512
  • 87
  • 279
  • 422