Tiling Spoj 2530 and related

Time to Tile some Dominoes

http://www.spoj.com/problems/M3TILE/

http://www.spoj.com/problems/GNY07H/ (M4TILE)

http://www.spoj.com/problems/M5TILE/ (M5TILE)

(M3TILE) : https://gist.github.com/swapcoder/6738962
(M4TILE) : https://gist.github.com/swapcoder/6738982

i will explain the (M4TILE) and posted (M4TILE) and (M3TILE) codes , last one i will post later

problem can be broken up into 3 subproblems

Sub problems
Check code for related recurrence relations

HR Red John is back

https://www.hackerrank.com/contests/101july13/challenges/red-john-is-back

Easy solution with the little dp and prime with very mild constraints

POJ 2663 Tri Tiling

Solution

DP practice problems

Chest of Drawer Practice DP

Chest of Drawers - Problem D of ACM World Finals Warmup

2008

You are given a chest of drawers with N drawers, which

can be locked.

You want to have exactly S secured drawers.

But not all locked drawers are secure.

A locked drawer is secure:

If it’s either the top drawer.

If the drawer directly above it is locked aswell.

Constraints:

0 <= N <= 65

0 <= S <= 65

You have to count how many ways you can locked N

drawers to give you S secure drawers.

I will publish answe later


Try this POJ 2663
 

836 Largest Submatrix

The 2D range sum DP problem recurrence relation same as 836
only change is we have to consider submatrix wih max 1's and (not maxsum)
have a look at condition on line no 106

10360 Rat Attack

This is easy backtracking problem which can be solved in O(n*d^2) complexity.
But this could also solved in 1025^2 using dp using range sum.
take input and make entries in dp[1025][1025];
Preproccess the 1025x1025 array using :
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];
then, use recurrence relation to find max
        dp[i+d][j+d]-dp[i+d][j-d-1]-dp[i-d-1][j+d]+dp[i-d-1][j-d-1]; for all (i,j) between d+1 to 1025-d

990 Diving for Gold

This is same as Knapsack 0/1 (maximize profit with using time < given amount of time) This problem can be considered as little bit harder because reconstruction of solution is also required here for that purpose we are going to have 2-D(number of element as rows and time as column) boolean array which tells us that whether we have taken element with current row ndex.

10306 e-Coins

This is Dynamic Programming problem.
It is coin change problem , form table with dp.
and find i,j such that i*i+j*j=s*s using brute force
and among all i,j find minimum coins using table values