Given a sequence a1, a2, … a_n, we want to find a subsequence of length b (x1, x2, … x_b) such that |x1-x2|+…|x_b-1 – x_b| is maximized. Give an algorithm linear in n to find the maximum value of |x1-x2|+…|x_b-1 – x_b|. The only algorithm I can think of is quadratic in n. You would ..
The code below outputs number of all possible permutation in list of strings within a constant length solving with recursion. Assume list_1 = ["A"] and list_2 = ["BB"] an length is 5 then: All possible combinations are: A A A A A A A A BB A A BB A A BB A A BB ..
My task is different from another questions dedicated to "primitive calculator" problem. You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2(for time b), multiply x by 3(for time c), or add 1 to x(for time a). Your goal is given a positive ..
Lets assume that we have a parking lot with fixed dimension, and there is a large variety of cars, busses, motorcycles and various other vehicles that need to be parked on it for long term. In the long term, we do not care where the individual vehicles are, and if they are accessible or not, ..
I have a rough solution to an optimization problem using dynamic programming. The aim is to get the shortest time to achieve the most satisfaction, with each item having individual time values, and a general optimal time for all the satisfactions. def pp(list1, values, time_values, optimal_time, memo): list4 =  for i, j in zip(values, ..
I was solving this problem Kill the dragon with below code. R, C, K, D = map(int, input().split()) Dragon_position = list() distance = 0 store = dict() for g in range(D): x, y = input().split() x = int(x) y = int(y) Dragon_position.append([x, y]) ans = 9999999 from itertools import combinations comb = combinations(Dragon_position, K) list_comb ..
Question about a school assignment. The problem to solve : In a game of chess with only pawns, for a given configuration i.e. the dimensions of the chessboard and the pawns positions, calculate in how many turns will the current player (white) will win or loose if each player play optimally. I’m using a dictionary ..
I’m solving a question on CodeChef which is basically subset sum problem. When a mobster approaches you in a dark alley, he asks you for a specific amount of money. You are obliged to show him all the money that you have, but you only need to pay up if he can find a subset ..
I’m practicing the concepts of Dynamic Programming (recursion is not my strong suit). I was wondering how my piece of code may be improved so that I can avoid a stack overflow. Anything helps, thanks! def coinFlipping(n): """ For n amount of change, return the minimal amount of currency in coins. Top-Down Approach (Memoization): Memo ..
Knapsack 1 has a weight limit of W kilos, and no volume limit Knapsack 2 has a volume limit of V, and no weight limit You have n items, 1, 2, . . . , n. Item i has weight wi ∈ N, volume vi ∈ N,and benefit bi You can leave items behind Find ..