Pointers

[dargueta]

Ok, this means that your issue is in initializeArray() and you're writing four bytes past the end of your array. My guess is that this line:

for(j = 0; j <= k; j++)

Should be:

for(j = 0; j < k; j++)

Try that.

[fread]

Im kind of far from my pc right now...will try as soon as i get home...

[fread]

I dont think that is it. I tried it but same error. What i realise is that happens the first time i call the realloc function. Lets say i had set that long pointer to hold 40 long values. It is on the first call i make to adjust the array to size 41 it fails. It does not get pass that.

[dargueta]

Oooh, a challenge. I like these. Gimme a bit and I'll figure something else out that won't work.

[fread]

LOL. Like the enthusiasm. I spent a lot of time on this and still haven't figured it out.

[dargueta]

Wild guess...make atracker unsigned, along with anything else that doesn't absolutely have to be able to take a negative value.

[fread]

***SIGHHHH***** No luck still... I think i have to rethink my approach towards solving this problem. I made some other changes and tested on a windows box and it ran without the segmentation error but my row was incorrect from the exact column where i was getting the segment error on my linux box. The error lies in realloc.

This is the scenario

Let * equal 1 chunk of memory, say.

//allocate storage for 3 rows of pointers
//unsigned long **Array;

Array = malloc( (x_size + 2) * sizeof(long *));

//then allocate storage for an array of long values
for (i = 0; i < (x_size + 2); i++)
    {
        Array[i] = malloc( (y_size + 1) * sizeof(long));
    }

//No i am going to assume it all looks something like this in memory

Array[1]**************************
Array[2]**************************
Array[3]**************************

//What i want to do is increase the lenght of any particular array at any point in time
//it could then probably look like this 

Array[1]**************************
Array[2]**************************************************
Array[3]**************************************************************

/*but now I'm wondering if realloc cannot create the required space for a particular row
what happens then. I think in a 1D Array it would move the entire chunk into new 
location if it could not create the entire space in from that initial memory 
position. So Im wondering now if the long pointers are bounded within that start 
position since it is an array of pointers. Lets say Array[2] could not realloc further
 from that point....what would happen..Bare in mind this program crashes before 
realloc returns and the pointer going into realloc in never null(i think). 
*/

This assignment is long over due. So ill get back to it some other time. I wont suggest you waste any more time on it. Thanks for the help...

[fread]

The problem is the same as before. This time i will describe the entire thing. I managed to get pass the realloc problem. For some reason now the program only works for the first two test input. after that the result is wrong. The result is the amount of entries in the last row. Here is the problem:

Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created. 

For example, consider stamps whose values are limited to 1 cent and 3 cents and suppose that you can use at most 5 stamps. It's easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren't much harder: 
6 = 2*3 
7 = 2*3+1 
8 = 2*3+2*1 
9 = 3*3 
10 = 3*3+1 
11 = 3*3+2*1 
12 = 4*3 
13 = 4*3+1. 
However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13. 

The first line of the input file has K, the total number of stamps that can be used, followed by N, the number of stamp values. The second and subsequent lines list all the N stamp values, 15 per line. Your job is to compute and print M, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set. 

You may assume that 1 <= N <= 500 and 1 <= K <= 500. No stamp value will exceed 10,000. Long integers (signed 32-bit) will be adequate for all solutions.
 
------------------------------------ 
20 1 
1 
 
Ans: 20 
------------------------------------- 
40 3 
1 2 5 
 
Ans: 197 
-------------------  ------------------ 
6 10 
1 2 9 31 255 480 4 15 63 127 
 
Ans: 720 
------------------------------------- 
334 14 
1 2 4 15 9 31 63 2100 3500 127 255 511 1000 1999 
 
Ans: 1151938

This is my attemp thus far:

//using the coin problem approach to solve this problem

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 500
#define true 1
#define false -1;


long getMinimum(long t1, long t2)
{    
    if (t1 > t2)         
        return t2;    
    return t1;
}

void initializeArray(unsigned long **a,long xsize, long ysize)
{    //xsize = the amount of different numbers; each in its own row
    //ysize = the number limit. Used for now. we will dynamically allocate the rest
    // set row 1 to the column value
    //set the first row and first column to 0
    //set everthing else to -1(null)
    
    printf("In initialise--->xsize: %ld, ysize: %ld\n",xsize,ysize);
    long i,j;
    long count = 0;
    for(i = 0; i <= xsize; i++){
        for(j = 0; j <= ysize; j++)
        {                            
                if (i == 1 && j != 0) //if row 1 set to j                                    
                    a[i][j] = j;                    
                else    
                if (i == 0 || j == 0)  //if row 0 or col 0 set to 0                
                    a[i][j] = 0;
                else                
                    a[i][j] = -1;                
        }    
    }
}


void mergeSort(int A[],int lo,int hi){
  void merge(int [],int ,int, int);
  if (lo < hi){
     long mid = (lo + hi) / 2;  //get the midpoint subscript
     mergeSort(A,lo,mid);      //sort first half
     mergeSort(A,mid+1,hi);    //sort second half
     merge(A,lo,mid,hi);      //merge sorted halves
     }
}
void merge(int A[],int lo,int mid,int hi)
{
  //A[lo..mid] and A[mid+1..hi] are sorted;
  //merge the pieces so that A[lo..hi] are sorted;
    static long T[MaxSize];
    long i = lo;
    long j = mid + 1;
    long k = lo;
  
    while (i <=mid || j <= hi)
    {
        if (i > mid) T[k++] = A[j++];     //A[lo..mid] completely processed
        else if (j > hi) T[k++] = A[i++]; //A[mid+1..hi] completely processed
        else if (A[i] < A[j]) T[k++] = A[i++]; //neither part completed
        else T[k++] = A[j++];
    }
    for(j = lo; j <=hi; j++) A[j] = T[j]; //copy merge elements back to A  
}


void initializeArray_1d(int A[], long lo, long hi, long value)
{
    int i;
    for ( i = 0; i < hi; i++)
        A[i] = value;
}

int main()
{
    FILE * pFile;
    unsigned long **a;     /* this is the array name */
    int *A_count;  //used to keep track of the amount on a given row
    long x_size, y_size, hold, value;
    int temp_array[MaxSize];    //used to hold stamp values
    int i, j ;
    pFile = fopen("INPUTC.txt","r");
    if(pFile == NULL)
        perror ("The following error occurred: ");
        
    fscanf(pFile,"%ld",&y_size);
    fscanf(pFile,"%ld",&x_size); 
    
    //make space for an array of size x_size to keep track of how many items on each row
    A_count = malloc( (x_size + 1) * sizeof(int));   
    
    //set 1 to x_size to y_size. This will increase as the array grows
    for(i = 0; i <= x_size; i++){
          if (i > 0 && i <= x_size) A_count[i] = y_size;
          else A_count[i] = 0;
          //printf("A_count[%d] = %d\n",i,A_count[i]);
          }
    
    printf("xsize: %ld, ysize: %ld\n",x_size,y_size);
    
    /*  allocate storage for an array of pointers*/
    a = malloc( (x_size + 1) * sizeof(long *));        
    
    /* for each pointer, allocate storage for an array of long values */
    for (i = 0; i < (x_size + 1); i++)
        a[i] = malloc( (y_size + 1) * sizeof(long));
    

    /* Initialise all arrays */
    initializeArray_1d(temp_array,0,MaxSize,32000);        
    initializeArray(a,x_size,y_size);
    
    //Load stamp values in temp_array 
    temp_array[0] = 0;
    for(i = 1; i <= x_size; i++)    
        fscanf(pFile,"%d",&temp_array[i]); 
        
    //sort temp_array
    mergeSort(temp_array,0,MaxSize -1 );  
    
   /* printf("printing the contents of temp_array\n");
    for(i = 0; i <= x_size; i++)
        printf("temparray[%d]: %d  \n",i,temp_array[i]);*/
        
    printf("\n");        
    
    for(i = 2; i <= x_size; i++)
    {
        /* For every row: calculate the amount of coins needed to make the jth(column) value.
         * When a value greater than j is found stop processing that row; this means that the item in just before
         * the jth one would represent the max unbroken list using only K amount of stamps.
         */
          hold = 0;
          j = 0;
          while (hold <= y_size)//iterate through each row until an invalid value is found
          {
                if (j > 0)  //put value into array from second pass onward                
                   a[i][j - 1] = hold;                   
                             
                if(j <= y_size) //we dont make a new entry
                {
                    if (j - temp_array[i] < 0) hold = a[i - 1][j];
                        else
                            hold = getMinimum ( a[i - 1][j] , a[i][j - temp_array[i]] + 1);                            
                }
                else
                if(j > y_size) //we make a new entry
                {
                    if (A_count[i - 1] >= j)  //considering the case where there exist a value directly above
                    {
                        //printf("toplow--> i: %d ->> %d vs %d; hold: %ld\n",i,A_count[i-1],j,hold);                  
                        if (j - temp_array[i] < 0) hold = a[i - 1][j];
                        else
                            hold = getMinimum ( a[i - 1][j] , a[i][j - temp_array[i]] + 1);
                            
                        a[i] = realloc(a[i], (j + 1) * sizeof(long));                        
                    }
                    else
                    {    
                        hold =  a[i][j - temp_array[i]] + 1;                     
                        a[i] = realloc(a[i], (j + 1) * sizeof(long));   
                    } 
                    if (hold <= y_size ) A_count[i] = A_count[i] + 1; 
                }                    
                j++;
          }         
    }

    for(i = 0; i <= x_size; i++)
    {
        for (j = 0; j <= A_count[i] ; j++)
            printf("%2ld ",a[i][j]);
        printf("\nrow %d above\n",i);
    }
    
    /* The answer would be the amount of values in the last row*/
    printf("sizeof A_count[%ld]: %d\n",x_size,A_count[x_size]);
    
    for (i = 0; i <= x_size; i++) 
        free(a[i]);    
    free(a);
    
    return 0;
}

Help needed

[dargueta]

How am I supposed to interpret the output? I tried 20 and 1 and it gives me this:

xsize: 1, ysize: 20
In initialise--->xsize: 1, ysize: 20

 0 
row 0 above
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 
row 1 above
sizeof A_count[1]: 20

[fread]

The only line that matters in the output is:
sizeof A_count[1]: 20

The rest is just debugging and tracking info i printed. You can comment out the rest.

In the explanation of the the problem above this is an example of the input and output:

SAMPLE INPUT (file INPUT.TXT):
5 2
1 3

SAMPLE OUTPUT (file OUTPUT.TXT):
13

where 5 is the amount of stamps you are allowed to use, 2 is the amount of different stamp values and 1 and 3 are the actual stamp values.

for example
40 3
1 6 10

would mean: use no more than 40 stamps, there are three different stamps and they are 1 6 10. Sorry about the confusion