Tag Archives: DP

Maximum sum with no adjacent elements

Maximum sum with no adjacent elements Maximum Sum with no adjacent elements Problem Statement: Given an array of positive numbers, find the maximum sum possible choosing numbers such that no two chosen numbers should be adjacent. Maximum Sum with no adjacent elements Problem Example: arr[ ] = {9, 1, 10, 100} Here maximum sum would be:… Read More »

Spoj HOTELS solution

Spoj HOTELS solution. Spoj Hotels Along the Croatian Coast Solution. Category: Dynamic Programming, DP This problem uses a technique called sliding window method or Kadane’s algorithm (Modified version is used). It is fairly easy to understand. Logic used: In this, you need a continuous set of hotels. To consider a set (window), we will use two pointers-… Read More »

Spoj PR003004 solution

Spoj PR003004 solution. Spoj Digit Sum solution. Category: Formula, Maths, DP In this question we need to find the sum of digits of all numbers between A and B. This can be done in the following way. Algorithm: Find Sum of digits from 1 to B. Find Sum of digits from 1 to (A-1). Subtract… Read More »

Spoj CPCRC1C solution

Spoj CPCRC1C solution. Spoj Sum of Digits solution. Category: Formula, Maths, DP In this question we need to find the sum of digits of all numbers between A and B. This can be done in the following way. Algorithm: Find Sum of digits from 1 to B. Find Sum of digits from 1 to (A-1). Subtract… Read More »

Spoj TWENDS solution

Spoj TWENDS solution. Spoj Two Ends Solution. Category: Dynamic Programming, DP(recursion + memoization) Before Solving this question, solve Spoj TRT. If you need to understand how to solve the problem, refer to Spoj TRT solution. In this question, the recursion/concept is same as TRT but we need to ignore/omit the larger element on the sides, as it… Read More »

Spoj TRT solution

Spoj TRT solution. Spoj Treats for the Cows Solution. Category: Dynamic Programming, DP(Recursion + memoization) In this question we need to maximise the amount we get by selling the treats. At first sight, this seems like a question that is solved using Greedy Strategy, but Greedy approach will produce a wrong answer. This question is similar… Read More »

Spoj ACODE solution

Spoj ACODE solution. Spoj Alphacode solution. Category: Dynamic Programming Solution goes like this: Initialize an Array of Size N with 0 and element 0 as 1 Loop through all the elements If it is a valid single digit number, Copy the previous element’s value to the current element (DP[i] = DP[i-1]) If it is a valid… Read More »

Spoj PAIRSUM solution

Spoj PAIRSUM solution.Spoj Sum of Pairwise Products solution. Category: Dynamic Programming In this question we need to print the value of auau + au+1au+1 + au+1au + au+2au+2 + au+2au+1 + au+2au + … + avav + avav-1 + … + avau What we do is : we use sum[i] to store sum of values of a0…ai. we use sumProd[i] to store… Read More »

Spoj DCEPC501 solution

Spoj DCEPC501 solution. Spoj Save Thy Toys solution. Category: Dynamic Programming Here, The array val[] stores the value of each of the items. The array dp[] stores the maximum money that Leonard can get by choosing toys from n−1 to i. Now, we use bottom-up DP and move through the array A from right to left… Read More »

Spoj POCRI solution

Spoj POCRI solution. Spoj Power Crisis solution. Category : Dynamic Programming,AdHoc This problem is direct implementation of Josephus Problem. The standard Dynamic Programming solution code for the Josephus Problem leads to Time Limited Exceeded error. So, we modify the code by removing the addition from the loop and adding a statement after the loop (in… Read More »