C++-এ অ্যারে স্ট্রিক্টলি ইনক্রিজিং বানানো (Make Array Strictly Increasing)

দুটি অ্যারে arr1 এবং arr2 দেওয়া আছে। arr1-কে স্ট্রিক্টলি ইনক্রিজিং বানাতে হলে ন্যূনতম কতবার অপারেশন দরকার সেটা বের করতে হবে। একবার অপারেশনে arr1[i] = arr2[j] অ্যাসাইন করা যায়। অসম্ভব হলে -১ রিটার্ন করুন।

উদাহরণ

ইনপুট: arr1 = [1,5,3,7,8], arr2 = [1,3,2,5]

আউটপুট: 1

ব্যাখ্যা: ৫ কে ২ দিয়ে রিপ্লেস করলে [1,2,3,7,8] হয়ে যায়।

সমাধানের ধাপসমূহ

arr2 সর্ট করুন।
DP + বাইনারি সার্চ ব্যবহার করুন।
dp[i][j] = সূচক i থেকে শুরু করে, শেষ ব্যবহার করা arr2 এর ইনডেক্স j, এবং পূর্বের মান prev দিয়ে ন্যূনতম অপারেশন।
দুই অপশন: বর্তমান arr1[i] রাখুন (যদি prev < arr1[i]), অথবা arr2 থেকে সবচোটে বড় ভ্যালু নিন।
মেমোইজেশন ব্যবহার করে অপ্টিমাইজ করুন।

প্রোগ্রাম উদাহরণ

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

class Solution {
public:
    int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, 
              vector<vector<int>>& dp) {
        if (i >= arr1.size()) return 0;
        
        j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
        if (dp[i][j] != -1) return dp[i][j];
        
        int ret = arr2.size() + 1;
        if (prev < arr1[i]) {
            ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
        }
        if (j < arr2.size()) {
            ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
        }
        return dp[i][j] = ret;
    }
    
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int n = arr1.size(), m = arr2.size();
        vector<vector<int>> dp(2005, vector<int>(2005, -1));
        int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
        return ret > m ? -1 : ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
    cout << (ob.makeArrayIncreasing(v, v1));
}

ইনপুট

{1,5,3,7,8}, {1,3,2,5}