Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Post a Comment

Morgan Stanley Campus Codeathon 2017

Q-1 Maximize Profit


Crypto Bank provides  crypto currencies, each of which has a fixed conversion rate with respect to dollar. The conversion rate w.r.t dollar is not subject to change over time. But as you may have imagined, the conversion rate between each pair of crypto currencies may change over time, due to economic and political factors.
Ron has  bitcoins with him. The conversion rate of a bitcoin w.r.t dollar is . You are given the conversion rates of every other crypto currency with respect to bitcoin. You are also given the conversion rate of these crypto currencies w.r.t dollar. You have to find the currency, that Ron can buy with  bitcoins, such that the total value in dollars is maximized.
Note that, Ron cannot buy crypto currency in fractions and Ron can own only one type of crypto currency at the end of the transaction.
Input Format
In the first line, you are given three integers - ,  and , where  is the number of currencies excluding bitcoin, is the amount of bitcoins Ron has and  is the conversion rate of bitcoin w.r.t dollar.
In the next line, you will be given  integers(), the  of which denotes the conversion rate of the  crypto currency w.r.t dollar.
In the third line, you will be given  integers (), the  of which denotes the number of units Ron can buy with one bitcoin,  Ron can buy  units of  crypto currency with  bitcoin.
Constraints
Output Format
In a single line, you have to output the maximum value in dollars that you can have. It is guaranteed that the answer will fit into a 32-bit integer.
Sample Input 0
5 10 3
2 3 4 1 5
1 3 2 4 5
Sample Output 0
250
Explanation 0
If you keep the bitcoins you have, then the value in dollars is 30. If you decide to buy the 1st currency, then you can have 10*1 = 10 units of that currency, and the value in dollars is 10*2 = 20. Similarly, the values in dollars of the 2nd, 3rd and 4th currency that you can buy are 90, 80, and 40 respectively. If you decide to buy the 5th currency, then you can have a total value in dollars of 250. This is greater than any other value and therefore the output is 250.
Sample Input 1
10 1 1000
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 3 2 1 1
Sample Output 1
1000
Explanation 1
The total value in dollars of the bitcoin is 1 * 1000 = 1000. This is greater than the value in dollars of any other currency which are 10, 18, 24, 28, 30, 30, 21, 16, 9 and 10 respectively. Therefore, the output is 1000.

Comments

Post a Comment

Popular posts from this blog

Array Transformation | biweekly-contest-12 | leetcode | Java Solution

Question Source Java Solution: class Solution {     public List<Integer> transformArray(int[] arr) {                  while(true) {             boolean isChanged = false;             int []copy = arr.clone();                          for(int i = 1; i < arr.length-1; i++) {                                 if(arr[i-1] > arr[i] && arr[i+1] > arr[i]) {                      copy[i]++;                     isChanged = true;                 }else if(arr[i-1] < arr[i] && arr[i+1] < arr[i]) {               ...
Read more

Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Read more

leetcode | Longest Substring Without Repeating Characters Solution

Source Problem: Given a string, find the length of the  longest substring  without repeating the characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. Solution: class Solution {     public int lengthOfLongestSubstring(String s) {                  Set<Character> subStr = new HashSet<>();         int maxLength = 0;         int j = 0;         for(int i = 0; i < s.length(); i++) {                          if(subStr.contains(s.charAt(i))){ ...
Read more