In my opinion, this is a 2D DP problem. dp(i, j) represents the minimum sum required to reach last index from index i and minimum jump allowed of size j. Let's say you are at index i in the array. Then you can either go to index i-j+1 or index i+j. So, int recur(int values[], int i, int j){ // base case. Here n is size of values array if(i==n-1) return 0; if(dp[i][j] != -1){ /* here -1 is taken as to mark never calculated state of dp. If the values [] array also contains negative values then you need to change it to something appropriate. */ return dp[i][j]; } int a = INT_MAX; int b = a; if(i>0 && (i-j+1)>=0) a = values [i-j + 1] + recur(values, i-j+1, j); if(i+j < n) b = values [i+j] + recur(values, i+j, j+1); return dp[i] [j] = min(a, b); } Time and space complexity O(n * n).

In my opinion, this is a 2D DP problem. dp(i, j) represents the minimum sum required to reach last index from index i and minimum jump allowed of size j. Let's say you are at index i in the array. Then you can either go to index i-j+1 or index i+j. So, int recur(int values[], int i, int j){ // base case. Here n is size of values array if(i==n-1) return 0; if(dp[i][j] != -1){ /* here -1 is taken as to mark never calculated state of dp. If the values [] array also contains negative values then you need to change it to something appropriate. / return dp[i][j]; } int a = INT_MAX; int b = a; if(i>0 && (i-j+1)>=0) a = values [i-j + 1] + recur(values, i-j+1, j); if(i+j < n) b = values [i+j] + recur(values, i+j, j+1); return dp[i] [j] = min(a, b); } Time and space complexity O(n n).

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

You have been given an array A of size N and an integer K. This array consists of N integers ranging from 1 to 10^7. Each element in this array is said to have a Special Weight. The special weight of an element a[i] is a[i]%K. You now need to sort this array in Non-Increasing order of the weight of each element, i.e the element with the highest weight should appear first, then the element with the second highest weight and so on. In case two elements have the same weight, the one with the lower value should appear in the output first. Input Format: The first line consists of two space separated integers N and K. The next line consists of N space separated integers denoting the elements of array A. Output Format: Print N space separated integers denoting the elements of the array in the order in which they are required. Constraints: 1≤N≤10^5 1≤A[i]≤10^7 1≤K≤10^7 Note: You need to print the value of each element and not their weight. SAMPLE INPUT 5 21 2 3 4 5 SAMPLE OUTPUT 1 3 5 2 4…
15. Consider the problem of finding the first position in which an array b occurs as a subsequence of an array a. Write two nested loops: let result undefined for (let i = 0; i < a.length - b.length; i++) { for (let j = 0; j < b.length; j++) { if (a[i+j] = b[j]) . . . } } Complete with labeled break and continue statements.
In an array-based implementation of a List, why does the add operation take O(n) time in the average case? Select one: a. The time it takes to shift entries over to make room in the array depends on the number of entries in the List b. The time to copy the current entries into a newly allocated, larger array depends on the number of entries in the List c. The time to access the position in the array to add the new entry depends on the number of entries in the List d. The time to access the position in the array to add the new entry depends on the capacity of the array
Given two arrays a and b, where both arrays consisting of n positive integers. It is allowed to swap any element from array a with any element from b. Your task is to find the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k moves (swaps). Input • The first line of the test case contains two integers n and k (1Sns30;0sksn) - where n is the number of elements in a and b, while k is the maximum number of moves you can do. • The second line of the test case contains n integers a1,a2,... an • The third line of the test case contains n integers b1,b2,..,bn Output Print the answer – the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k swaps. Examples: Ex 1: Ex 2: Ex 3: Input 55 53 40 55665 1234 5 2243 12543 10 9 10 10 9 2423 Output: 27 39 11 • In the first test case of the example, you don't need to swap anything. • In the second test case of the example, you can swap a1=1 with bi=10, a3=3 with b3=10…
Given two arrays a and b, where both arrays consisting of n positive integers. It is allowed to swap any element from array a with any element from b. Your task is to find the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k moves (swaps). Input • The first line of the test case contains two integers n and k (1sns30;0sksn) - where n is the number of elements in a and b, while k is the maximum number of moves you can do. • The second line of the test case contains n integers a1,a2,... an • The third line of the test case contains n integers b1,b2,..,bn Output Print the answer – the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k swaps. Examples: Ex 1: Ex 2: Ex 3: Input 55 53 40 55665 12345 2243 12543 10 9 10 10 9 2423 Output: 27 39 11 • In the first test case of the example, you don't need to swap anything. • In the second test case of the example, you can swap a1=1 with b1=10, a3=3 with b3=10…
You are given an array J[1 : n] which includes the scores of n players in a game. You are additionally given an array P[1 : m] with the score of m new players. Design and analyze an algorithm that given both arrays J and P, can find the rank of each player P inside the array J, i.e., for each P[i], determines what would be the rank of P[i] in the array consisting of all elements of J plus P[i]. Your algorithm should run in O((n + m) ·log n) time.
You are given an integer array X[1, . . . , n]. You should move each element of X[1, . . . , n] into one of the two arrays A and B such that A and B are non-empty and average(A) = average(B). Return true if it is possible to achieve that and false otherwise. Note that for an array A, average(A) is the sum of all the elements of A over the length of A. Precisely define the subproblem.Provide the recurrence equation.Describe the algorithm in pseudocode to compute the optimal value.Describe the algorithm in pseudocode to print out an optimal solution.
Given two arrays a and b, where both arrays consisting of n positive integers. It is allowed to swap any element from array a with any element from b. Your task is to find the maximum possible sum you can obtain in the array a if you can do no more than (Le. at most) k moves (swaps). Input • The first line of the test case contains two integers n and k (1
Consider the following problem.Input: An array of sizen>3that consists ofanon-empty decreasing sequence ofnumbers followed byanon-empty increasing sequence of numbers.Output: The smallest number of array A.For example, givenA=<16, 10, 6, 3, 2, 4, 8, 12, 15, 20>, the output will be 2. Notethat for such an array, you can find the smallest number at indexkwith •A[i]>A[i+1] for all1<i<k •A[i]<A[i+1] for allk<i<nAssume index starts from 1.Designarecursive algorithm based on divide-and-conquer to find the smallestnumber of such an array. [Hint: The idea can be similar to binary search. (1) Write your algorithm in pseudocode. You will get no point if your algorithmis non-recursive. (2) Write a recurrence relation on the running time of your algorithm. Solve itto giveatight bound.
Select the for-loop which iterates through all even index values of an array.A. for(int idx = 0; idx < length; idx++)B. for(int idx = 0; idx < length; idx%2)C. for(int idx = 0; idx < length; idx+2)D. for(int idx = 0; idx < length; idx=idx+2)
Suppose we are given an array of numbers A[0], A[2], . . . , A[n - 1]. You may assume that n is a multiple of6. We wish to find a number x that simultaneously satisfies two properties: First, x should be in the middle two-thirds ofthe array (in other words, x = A[i] for some n/6 <= i < 5n/6). Second, after sorting the array, x should still be in the middletwo-thirds.2a) Prove that such an x exists. (Hint: how many values are not in the middle two-thirds of the original array? How manyare not in the middle two-thirds of the sorted array?)2b) Describe a linear time algorithm for finding such an x. (Note, if your solution calls one of the algorithms described inthe lectures, you should just refer to it by name, e.g. “quicksort”, rather than explaining how it works.)
You're given an array of N integers, and a number K. The maximum K-product of the array is the maximum product of any K length subsequence of the array. For example, the maximum 2-product of the array [-5, 3, 4, -6] is 30 because the product of the subsequence [-5, -6] is 30 and it is impossible to achieve larger subsequence product. What is the maximum K-product you can achieve? Using JAVA programming output the max K- product. Input: 1 42 5 -3 -4 6 Output: 30