[Solved] Tree Heights with Java, C++, Python

Tree Heights: There are N trees in Jon’s backyard and height of tree i is h[i]. Jon doesn’t like the appearance of it and is planning to increase and decrease the height of trees such that the new heights are in strictly increasing order. Every day he can pick one tree and increase or decrease the height by 1 unit. Heights can be 0 or even negative (it’s a magical world).

Jon has guests coming after X days, hence he wants to know if it is possible to make heights strictly increasing in no more than X days?

Input format:

First line contains one integer N<=2000 number of trees, X<=5000 number of days Jon has.
Second line contains N space separated integers where ith integer is h[i]

Output Format:

YES or NO, if it is possible to make tree heights in strictly ascending order in no more than X days, if YES, also print the number of days it will take.

Sample Input 1:

5 13
5 4 3 2 1

Sample Output 1:

YES 12

Explanation:

For the first sample the final array will look like 1 2 3 4 5
Hence the number of days required will be 12.

Sample Input 2:

7 10
7 1 4 10 5 8 12

Sample Output 2:

NO

Solution

// java
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.util.stream.Collectors;

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(solve(nums, X));
    }

    private static String solve(int[] nums, int X) {
        int N = nums.length;
        int minn = Arrays.stream(nums).min().getAsInt();
        for (int i = 0; i < nums.length; i++) {
            nums[i] -= minn;
        }
        int maxn = Arrays.stream(nums).max().getAsInt() + 1;

        int[][] dp = new int[N][maxn];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            // sauravhathi
        }

        for (int j = 0; j < maxn; j++) {
            dp[0][j] = Math.abs(nums[0] - j);
        }

        for (int i = 1; i < nums.length; i++) {
            int min_so_far = Arrays.stream(dp[i - 1]).limit(i).min().getAsInt();
            for (int j = i; j < maxn; j++) {
                dp[i][j] = Math.abs(nums[i] - j) + min_so_far;
                min_so_far = Math.min(min_so_far, dp[i - 1][j]);
            }
        }
        return Arrays.stream(dp[N - 1]).min().getAsInt() <= X ? "YES " + Arrays.stream(dp[N - 1]).min().getAsInt() : "NO";
    }
}

// c++ 
#include <bits/stdc++.h>
using namespace std;

string solve(vector<int> nums, int X) {
    int N = nums.size();
    int minn = *min_element(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        nums[i] -= minn;
    }
    int maxn = *max_element(nums.begin(), nums.end()) + 1;

    vector<vector<int>> dp(N, vector<int>(maxn, INT_MAX));
    for (int j = 0; j < maxn; j++) {
        dp[0][j] = abs(nums[0] - j);
        // sauravhathi
    }

    for (int i = 1; i < nums.size(); i++) {
        int min_so_far = *min_element(dp[i - 1].begin(), dp[i - 1].begin() + i);
        for (int j = i; j < maxn; j++) {
            dp[i][j] = abs(nums[i] - j) + min_so_far;
            min_so_far = min(min_so_far, dp[i - 1][j]);
        }
    }
    return *min_element(dp[N - 1].begin(), dp[N - 1].end()) <= X ? "YES " + to_string(*min_element(dp[N - 1].begin(), dp[N - 1].end())) : "NO";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, X;
    cin >> N >> X;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    cout << solve(nums, X) << endl;
    return 0;
}

# python
def solve(nums, X):
    N = len(nums)
    minn = min(nums)
    for i in range(len(nums)):
        nums[i] -= minn
    maxn = max(nums) + 1 

    dp = [[float('inf')]*(maxn) for _ in range(N)]

    for j in range(maxn):
        dp[0][j] = abs(nums[0]-j)
        # sauravhathi
    
    for i in range(1, len(nums)):
        min_so_far = min(dp[i-1][:i])
        for j in range(i, maxn):
            dp[i][j] = abs(nums[i]-j) + min_so_far
            min_so_far = min(min_so_far, dp[i-1][j])
    return "YES " + str(min(dp[-1])) if min(dp[-1]) <= X else "NO"
    

N, X = map(int, input().split())
nums = list(map(int, input().split()))
print(solve(nums, X))

Happy Learning – If you require any further information, feel free to contact me.