View previous topic :: View next topic |
Author |
Message |
| Novembre
| Joined: 24 Apr 2006 | Posts: 2 | : | | Items |
|
Posted: Mon Apr 24, 2006 1:59 pm Post subject: Need help with this question!! |
|
|
Suppose you are given a two dimensional matrix. For example, 256 by 10000 where 256 is the number of rows and the 10000 is the number of columns. This matrix has the following properties:
1- Each entry is either 0 or 1 only.
2- Each columns must has exactly one 1.
Re-write the structure of the above matrix in a way that minimizes the space as much as you can.
For example:
If you store the 0 as int then the integer will take 4 bytes. If you store it as short integer then it will be 2 bytes. Therefore, you might think of other possible ways. If I were you, I will study the adjacency lists and the sparse matrix. I will try to get rid from the 0s and use the fact that each column has exactly one 1. You are allowed to use anything or any data structure you would like to use. For example, converting the above matrix into one dimensional solution is correct, but you need to check the required storage. Think of the 1s as bits not bytes. Note that total memory size must be as minimum as much as you can. |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Mon Apr 24, 2006 2:22 pm Post subject: |
|
|
Create a one dimensional array of 10,000 unsigned bytes.
Now populate it with ( row_number - 1 ) [0..255] where the 1-bit is set in each column.
Total size = 10,000 bytes = 80,000 bits
(Yeah, I know, someone else will have a smaller solution!) |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Mon Apr 24, 2006 3:36 pm Post subject: |
|
|
daj95376 wrote: | Total size = 10,000 bytes = 80,000 bits
(Yeah, I know, someone else will have a smaller solution!) |
I don't think so. Indeed, if the process includes "solving the grid", another bit per column would be req'd to keep track of columns with/without a 1s placement. |
|
Back to top |
|
|
| Novembre
| Joined: 24 Apr 2006 | Posts: 2 | : | | Items |
|
Posted: Mon Apr 24, 2006 7:08 pm Post subject: |
|
|
I thought i can just store a vector of indexes of rows for which the column corresponding to this item index has a "1"... after all, there's just one pero column... ex.: index i of the vector has a j on it if item j,i in the matrix is a "1".
can this do?? |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Mon Apr 24, 2006 7:35 pm Post subject: |
|
|
Novembre wrote: | I thought i can just store a vector of indexes of rows for which the column corresponding to this item index has a "1" ... can this do?? |
Sounds reasonable to me. How many bits does that take? |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Mon Apr 24, 2006 9:55 pm Post subject: |
|
|
rkral wrote: | daj95376 wrote: | Total size = 10,000 bytes = 80,000 bits
(Yeah, I know, someone else will have a smaller solution!) |
I don't think so. Indeed, if the process includes "solving the grid", another bit per column would be req'd to keep track of columns with/without a 1s placement. |
Please re-read his original request. There was no mention of solving the grid and he specifically stated that every column had exactly one occurrence of a 1. I answered his question within the given parameters! |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Tue Apr 25, 2006 1:10 am Post subject: |
|
|
daj95376 wrote: | Please re-read his original request. There was no mention of solving the grid and he specifically stated that every column had exactly one occurrence of a 1. I answered his question within the given parameters! |
People often don't state the exact scenario, so please re-read my statement and note I said "if" as in "if the process includes solving the grid." |
|
Back to top |
|
|
|