You have a list of jobs that need to be scheduled. For each job, you know when it should start and when it should end. You need to come up with an algorithm to schedule the maximum number of jobs possible."

Find The Maximum Sum in Triangle From Top to Bottom (Euler Problem) . Don't Forget to Check the Code for Triangle Which has 100s of Base :)

An Anonymous reader sent me the problem & ii posted it here
ohh but i forgot that Problem is already solved & posted few months back . so i am not giving to d same again excpet providing the link

Problem Discription

Given a triangle like the following
3
4 6
1 5 0 1.
How many nodes would you have, for 20 rows? 2. How to find the largest sum from the top of the triangle to the one of the nodes at the bottom. In other words, if you consider it as a tree, find the max sum of all paths from root to the leaf.

Thinking Process & Approach Here

This involves maths stuff rather then considering tree (it wont work check below link for detail ) or applying computer science & problem is already famous (Euler problem ) as we have to find the maximum sum in triangle we have given a big triangle which has many small triangle only thing u need to know a triangle has 3 vertexes so that you can approach :)

and a detailed description,explaination & solution you can find here

http://shashank7s.blogspot.com/2011/04/project-euler-problem-67-finding.html

let me know if i missed something or any other approach to solve it

one think that would recommands to geeks try out the recursive solution for the same problem :)

Given a positive integer n, find the minimum number of steps that takes n to 1 eg: 1.)For n = 1 , output: 0 2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 ) 3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

On a positive integer, you can perform any one of the following 3 steps. 1.) Subtract 1 from it. ( n = n - 1 )  , 2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  , 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). Using These Conditions Solve Above Question Efficiently ?

Approach / Idea: One can think of greedily choosing the step, which makes n as low as possible and conitnue the same, till it reaches  1. If you observe carefully, the greedy strategy doesn't work here. Eg: Given n = 10 , Greedy --> 10 /2 = 5  -1 = 4  /2 = 2  /2 = 1  ( 4 steps ). But the optimal way is --> 10  -1 = 9  /3 = 3  /3 = 1 ( 3 steps ). So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.

It all starts with recursion :).  F(n) =   1 + min{  F(n-1) ,  F(n/2)  ,  F(n/3)  }  if (n>1) , else 0  ( i.e., F(1) = 0 ) . Now that we have our recurrence equation, we can right way start coding the recursion. Wait.., does it have over-lapping subproblems ?  YES. Is the optimal solution to a given input depends on the optimal solution of its subproblems ? Yes... Bingo ! its DP :) So, we just store the solutions  to the subproblems we solve and use them later on, as in memoization.. or we start from bottom and move up till the given n, as in dp. As its the very first problem we are looking at here, lets see both the codes.

Memoization

[code]

int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )

int getMinSteps ( int n )

{

if ( n == 1 )  return 0;  // base case

if( memo[n] != -1 ) return memo[n];  // we have solved it already :)

int r = 1 + getMinSteps( n - 1 );  // '-1' step .  'r' will contain the optimal answer finally

if( n%2 == 0 )   r  =  min( r , 1 + getMinSteps( n / 2 ) ) ;  //  '/2' step

if( n%3 == 0 )   r  =  min( r , 1 + getMinSteps( n / 3 ) ) ;  //  '/3' step

memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.

return r;

}

[/code]

Bottom-Up DP

[code]

int getMinSteps ( int n )

{

int dp[n+1] , i;

dp[1] = 0;  // trivial case

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

{

dp[i] = 1 + dp[i-1];

if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );

if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );

}

return dp[n];

}

Source:http://www.codechef.com/wiki/tutorial-dynamic-programming#Identifying_the_State

Unable to Post The Discription of Problems since last 3 days ..M Not Feeling Good .does anyone know whats the probelm .please comment if you know ?

Unable to Post The Discription of Problems since last 3 days ..M Not Feeling Good .does anyone know whats the probelm .please comment if you know ?

Given n distinct elements, how many Young tableaus can you make?

Given n distinct elements, how many Young tableaus can you make?

You have a set of ants moving on an horizontal segment of length n. Each ant can randomly move either right or left. When an ant takes a direction, she stays in that direction until she either drops out of the segment or it bumps with another ant. In this case, the ant changes her direction. Can you formalize the system and describe what will happen after t iterations?

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.