Tag Archives: Dynamic programming

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 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 »

Spoj DANGER solution

Spoj DANGER solution. Spoj In Danger Solution. Category: Dynamic Programming, Pattern, AdHoc This question is the direct implementation of the Josephus Problem. But, the time limit is such that even the Dynamic Programming solution of Josephus Problem gives Time Limit Exceeded Error. Spoj DANGER solution code: So, we study that Josephus Problem with K=2 has the… Read More »

Spoj WTK solution

Spoj WTK solution. Spoj Why this kolaveri di Solution. Category: Dynamic Programming This question is a variation of the Josephus Problem. We need to add the value of ‘N’ in every iteration of the Dynamic Programming solution of the Josephus Problem. Here, the number of people who are skipped increases in every iteration. Spoj WTK solution code:… Read More »

Spoj ANARC08H solution

Spoj ANARC08H solution. Spoj Musical Chairs Solution. Category : Dynamic Programming This question is the Direct application of the Josephus Problem. We use the Dynamic programming Solution of the Josephus Problem. Spoj ANARC08H solution code: Here is the working code: #include <bits/stdc++.h> using namespace std; int main() { int n,d; scanf(“%d%d”,&n,&d); while(n && d) { /*The following… Read More »

Spoj KNAPSACK solution

Spoj KNAPSACK solution. Spoj The Knapsack Problem solution. Category: Dynamic Programming This question is the direct application of the 0-1 Knapsack Problem. Refer to the link to understand how to solve this question. Spoj KNAPSACK solution code: Here is the working code: #include <bits/stdc++.h> using namespace std; int Knapsack01(int W, int wt[],int v[] ,int n) {… Read More »