HACKER RANK: Play Game

Problem Link: https://www.hackerrank.com/challenges/play-game

Summary:
Given N number of elements in stack.

first line will contain a number N i.e. number of elements in the stack and next line will contain N numbers i.e. numbers etched on bricks from top to bottom.

You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

Print a single line containing your maximum score.

For Example:

Sample Input:

2

5

999 1 1 1 0

5

0 1 1 1 999

Sample Output:

1001

999

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming

Logic:

I took dp[2][n]

dp[0]->My Score

dp[1]->Minimum Score other player leaves for me as he also play optimally

When n = 1,2,3 then you took all elements in stack

dp[0][n-1]=a[n-1]

dp[0][n-2]=a[n-1]+a[n-2]

dp[0][n-3]=a[n-1]+a[n-2]+a[n-3]

so for i n-4 to 0:

    dp[1][i] = min(dp[0][i+1],min(dp[0][i+2],dp[0][i+3]))

    dp[0][i] = max(a[i]+dp[1][i+1],max(a[i]+a[i+1]+dp[1][i+2],a[i]+a[i+1]+a[i+2]+dp[1][i+3]))

ans = dp[0][0]

print ans

In this code dp[1][i] is minimum left by other player for you when he plays optimally i.e chooses maximum sum of elements for itself.

and dp[0][i] is maximum of taking one element, two element or three element plus minimum left by other player when he chooses maximum sum of elements for itself.

Time Complexity: O(n)

To View My Solution:

https://github.com/shivam04/hackerrank/blob/master/play-game.cpp

HACKER RANK: Red John is Back

Problem Link: https://www.hackerrank.com/challenges/red-john-is-back

Summary:
Given N find number of ways to to arrange 4X1 and 1X4 bricks in 4XN block. Say there are M ways so print P number of prime up to M(i.e. <=M).

For Example:

Sample Input:
4
1
3

Sample Output:
0
3

For N=1
There is only one way so P = 0 as there is no prime number less than M=1

For N=7
there is M=5 ways so answer P=3 as 2,3,5 is less than than and equal to 5.

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming

Logic:
What I have done is take number N as a block of weight N kg and try to adjust weight 1kg and 4kg weight in different ways.
So number of ways can be recursively computed as:
F(n) = F(n-1) + F(n-4)
if we place weight of 1kg then F(n-1) need to be computed.
if we place weight of 4kg then F(n-4) need to be computed.

Then taken sum of all computes M = F(n)

Now using Sieve Of Eratosthenes(http://www.geeksforgeeks.org/sieve-of-eratosthenes/) we compute P number of prime numbers up to M.

To View My Solution:
https://github.com/shivam04/hackerrank/blob/master/red-john-is-back.cpp