ROD CUTTING PROBLEM - Dynamic Programming

Hey I have come up with a wonderful algorithm for solving the rod cutting problem using dynamic programming. The rod cutting algorithm as per CLRS takes O(n^2) but but but there is a suspense, in CLRS Prof. Cormen embodies the solution to only one subproblem. So I brainstormed a bit and found that if you try to find to modify the solution for both the subproblem and optimise the code a bit then you can achieve O(nlogn) .

You'll not find O(nlogn) implementation of Rod Cutting Problem anywhere on the net. Go through the code, at first it's hard to completely understand it, but if you try a bit harder you'll know what I have done. The link to problem description is given below:

https://en.wikipedia.org/wiki/Cutting_stock_problem

Here is the implementation in C:

#include<stdio.h>

#include<stdlib.h>

#define maxi(a,b) ((a) > (b) ? a : b)

int main(){

    int i,j,n,q=0;

    printf("Enter the length of the array");

    scanf("%d",&n);

    int a[n+1],r[n+1];

    a[0]=0;

    a[1]=1;

    for(i=2;i<=n;i++)

        scanf("%d",&a[i]);

    for(i=0;i<=n;i++)

        r[i]=0;

    r[1]=1;

    

    for(i=2;i<=n;i++){

        q = a[i];

        for(j=1;j<=i/2;j++)

            q = maxi(q,(r[j]+r[i-j]));

        r[i]=q;

    }

    for(i=1;i<=n;i++)

        printf("%d ",r[i]);

    return 0;

                       

}

INPUT : Enter the length of the array

10

5 8 9 10 17 17 20 24 30

OUTPUT: 1 5 8 9 10 17 18 22 25 30

If you have any doubts feel free to ask in the comments section below.

                       

Maximum Perimeter Triangle

This is a simple but tricky greedy problem. I find the solution without complicating the things in O(n logn), I hope you'll like this! . Check out the link below for the problem Description.
https://www.hackerrank.com/challenges/maximum-perimeter-triangle/problem

Solution:

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

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
int cmpfunc (const void * a, const void * b)
{
   return (*(int*)b - *(int*)a);
}

int main() {

    int n,i,c=0;
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    qsort(a, n, sizeof(int), cmpfunc);

    for(i=0;i<n-2;i++){
        if(a[i]<(a[i+1]+a[i+2])){
            c=1;
            printf("%d %d %d",a[i+2],a[i+1],a[i]);
            break;
        }
    }
    if(c==0)
        printf("-1");    
    return 0;
}

Luck Balance

Just a trivial greedy problem. Check out the link for the problem description :
https://www.hackerrank.com/challenges/luck-balance


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int main() {
    int a[100]={0};
    int N,K,c=0,i=0,l,t,c1,c2,sum=0;
    scanf("%d %d",&N,&K);

    while(i!=N){
        scanf("%d %d",&l,&t);
        if(t==0)
            sum+=l;
        else if(t==1){
            a[i]=l;
            c+=1;
        }
      i++;
    }

    qsort(a, 100, sizeof(int), cmpfunc);

    c1=100-c;
    c2=c-K;
    for(i=c1;i<100;i++){
        if(i<c1+c2)
        sum=sum-a[i];
       
    else if(i>=c1+c2)
        sum=sum+a[i];
    }
    printf("%d",sum);
    return 0;
}

The Coin Change Problem

https://www.hackerrank.com/challenges/coin-change

Checkout my solution to this hard Dynamic Programming from Hackerrank:

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

#include <limits.h>

#include <stdbool.h>

int comp (const void * elem1, const void * elem2)

{

    int f = *((int*)elem1);

    int s = *((int*)elem2);

    if (f > s) return  1;

    if (f < s) return -1;

    return 0;

}

int main(){

    int n,m,i,j;

    scanf("%ld %ld", &n,&m);

    long int a[m],b[n+1];

     b[0]=1;

     for(i=1;i<(n+1);i++){

        b[i]=0;

     }

    for(i=0;i<m;i++)

        scanf("%ld",&a[i]);

    qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), comp);

    for(i=0;i<m;i++){

        for(j=a[i];j<n+1;j++)

            b[j]+=b[j-a[i]];

    }

    printf("%ld",b[n]);

    return 0;

}