Maximum possible score by player 1

Problem: Link

Suppose you are given an array with even number of integers. You and some other player take turns to pick numbers, either the leftmost element or the rightmost element. We have to find the maximum possible score (sum of numbers chosen) by player 1.
For example: if array is 5 8 4 2, then player 1 can choose either 5 or 2. Suppose he chooses 2, then player 2 can choose 5 or 4. Irrespective of what player 2 chooses, in next round player 1 will have chance to choose 8. Thus, maximum possible score by player 1, in this scenario, is (8+2)=10.

Solution:

#include <stdio.h>

#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)

/* Returns maximum possible score of player1 incase of player2 is dumb */
int maxscoredumb(int a[], int start, int end)
{
if(start > end)
return 0;

if(start == end - 1)
{
return max(a[start], a[end]);
}
else if(start == end)
{
return a[start];
}

/* if player1 chooses left */
int left = a[start];
{
int left1 = maxscoredumb(a, start + 2, end); //if player2 chooses start
int left2 = maxscoredumb(a, start + 1, end - 1); //if player2 chooses end

left += max(left1, left2); //assuming player2 is dumb, if player2 is smart, we have to take min
}

/* if player1 chooses right */
int right = a[end];
{
int right1 = maxscoredumb(a, start + 1, end - 1); //if player2 chooses start
int right2 = maxscoredumb(a, start, end - 2); //if player2 chooses end

right += max(right1, right2); //assuming player2 is dumb, if player2 is smart, we have to take min
}

return max(left, right);
}


/* Returns maximum possible score of player1 incase of player2 is smart */
int maxscoresmart(int a[], int start, int end)
{
if(start > end)
return 0;

if(start == end - 1)
{
return max(a[start], a[end]);
}
else if(start == end)
{
return a[start];
}

/* if player1 chooses left */
int left = a[start];
{
int left1 = maxscoresmart(a, start + 2, end); //if player2 chooses start
int left2 = maxscoresmart(a, start + 1, end - 1); //if player2 chooses end

left += min(left1, left2);
}

/* if player1 chooses right */
int right = a[end];
{
int right1 = maxscoresmart(a, start + 1, end - 1); //if player2 chooses start
int right2 = maxscoresmart(a, start, end - 2); //if player2 chooses end

right += min(right1, right2);
}

return max(left, right);
}
int main()
{
int n;

scanf("%d", &n);

int a[n];

int i;

for( i = 0; i < n; ++i)
scanf("%d", a + i);

printf("Player2 Dumb: %d\n", maxscoredumb(a, 0, n-1));
printf("Player2 Smart: %d\n", maxscoresmart(a, 0, n-1));
Advertisements

Given an array of length n, print all sub arrays of length r

#include <stdio.h>

/* Prints all the subarrays of length r */

/* @params: a, given array */
/* @params: n, a length */
/* @params: sub, sub array */
/* @params: r, sub length */
/* @params: i, current index of a */
/* @params: j, current index of sub */

void subarray(int a[], int n, int sub[], int r, int i, int j)
{
if(j == r) /* current index of sub r, print sub */
{
int k;

printf("( ");

for(k = 0; k < r; k++)
printf("%d ", sub[k]);

printf(")\n");
}
else
{
if(i < n)
{
sub[j] = a[i];

subarray(a, n, sub, r, i + 1, j + 1); /* Include current element */
subarray(a, n, sub, r, i + 1, j); /* Override the current element */
}
}

}

int main()
{
int n, r;

scanf("%d%d", &n, &r);

int a[n], sub[r];

int i;

for(i = 0 ; i < n; ++i)
scanf("%d", a + i);

subarray(a, n , sub, r, 0, 0);
}

To find max palindrome in a given ascii text file

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <ctype.h>

void usage(char *s)
{
printf("Usage: %s <inputfile>\n", s);
exit(1);
}

int ispalindrome(const char *s)
{
const char *p = s + strlen(s) - 1;

while(s <= p)
{
if(*s++ != *p--) return 0;
}

return 1;
}

int main(int argc, char* argv[])
{
if(argc != 2)
usage(argv[0]);

int fd = open(argv[1], O_RDONLY);

if(fd == -1)
{
perror(argv[1]);
exit(1);
}

/* Buffer to hold data read from file */
char buf[64 * 1024];

/*Buffer to hold current word */
char str[4096];

/*Buffer to hold current max palindrome */
char palindrome[4096] = {0};
int maxlen = 0;

/* Temporay variables */
char *p = str;
int n;

while( (n = read(fd, buf, 64 * 1024)) > 0) /* Read 64k at a time */
{
int i = 0;

while(i < n) /* Divide into words */
{
if(isalpha(buf[i])) /*if alpha, Copy to temp buf*/
{
*p++ = buf[i];
}
else /* end of the word */
{
if( ((p - str) > maxlen) && ispalindrome(p) ) /* Check whether it is max palindrome */
{
*p = 0;
maxlen = p - str;
strcpy(palindrome, str);
}
p = str;
}
++i;
}
}

printf("%s %d\n", palindrome, maxlen);
}

internal node count in a binary tree

#include <stdio.h>

typedef struct Node
{
int data;
struct Node *left, *right;

}Node;

typedef Node * Tree;

inline int isLeaf(Node *n)
{
return (n == NULL) || (n->left == NULL && n->right == NULL);
}

int internalNodeCount(Tree t)
{
if(isLeaf(t))
return 0;

return 1 + internalNodeCount(t->left) + internalNodeCount(t->right);

}

minimum depth of a binary tree

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node *left, *right;
} Node;

typedef Node* Tree;

#define min(a, b)(a)<(b)?(a):(b)

int mindepth(Tree t)
{
    if(t == NULL || (t->left == NULL && t->right == NULL)) return 0;
    return min( 1 + mindepth(t->left), 1 +  mindepth(t->right) );
}

Given an array a[], create another array ar_low[] such that ar_low[i] = number of elements less than or equal to ar[i] in ar[i+1:n-1]

#include <stdio.h>
#include <map>

/* Map to hold an element and its count of number of elements <= */
/* Element is the key and Count of <= is the Value */
typedef std::map<int, int> Map;


/* Inserts the element into map */
/* Returns count of <= */
int insert(Map &m, int el)
{
/* Find the element >= el */
Map::iterator mit = m.lower_bound(el);

/* If el already exists, increment its Count of <= */
if(mit != m.end() && (mit->first == el ))
{
return ++mit->second;
}

Map::iterator mit1 = mit;

/* Increment the count of the greater elements by 1 */
for(; mit != m.end(); ++mit)
{
mit->second++;
}

/* Find prev element, set current element count as prev element count + 1 */
if(mit1 != m.begin())
{
--mit1;
return m[el] = mit1->second + 1;
}

return m[el] = 0;
}

void findCount(int a[], int a_low[], int n)
{
Map m;

/* Start from the end */
while(n--)
{
a_low[n] = insert(m, a[n]);
}
}

int main()
{
int n;

scanf("%d", &n);

int a[n], a_low[n];

int i;

for(i = 0; i < n; ++i)
scanf("%d", a + i);

findCount(a, a_low, n);

for(i = 0; i < n; ++i)
printf("%d ", a_low[i]);

printf("\n");

}

Checking whether given intervals are contiguous or not

Problem: Link

u will be given pairs.. u need to see whether they have any gaps..
ex1: max no:20
pairs: 11-15, 0-5, 18-20, 14-19, 6-13

u can think pairs are like intervals..the above has no gaps..
because 0-5,6-13,11-15,18-20 have all numbers from 0 (min) to 20(max)

ex2: 11-15, 0-5, 18-20, 14-16, 6-13

this have gap as the intervals miss a number from 0 to 20 i.e.,17


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


typedef struct
{
    int minimum, maximum;
}Interval;


/* Compares intervals based on minimum element */
int cmpInterval(const void *a, const void *b)
{
    return ((Interval *)a)->minimum - ((Interval *)b)->minimum;
}


int isIntervalsContiguous(Interval intervals[], int n)
{
        /* Sort the intervals */
        qsort(intervals, n, sizeof(Interval), cmpInterval);


        /* Check whether they are contiguous */
        int i;

        for(i = 1; i < n; i++)
        {
            if(intervals[i].minimum > intervals[i - 1].maximum + 1)
                return 0;
        }

        return 1;
}

int main()
{
    int n;

    scanf("%d", &n);

    Interval intervals[n];

    int i;

    for(i = 0; i < n; ++i)
        scanf("%d%d", &intervals[i].minimum, &intervals[i].maximum);

    printf("isContiguous: %d\n", isIntervalsContiguous(intervals, n));
}