Question: DE Shaw (DESIS Ascend) , Online Assessment Question (17th September 2023) | findMincost
0
Entering edit mode

0
Entering edit mode

Solution using DP

int split(vector<int> &v, int start, int end, int m, vector<vector<int>> &dp)

{

if ((end - start + 1) < m)

return INT_MIN;

if ((end - start + 1) < 2 * m)

return v[end] - v[start];

if (dp[start][end] != -1)

{

return dp[start][end];

}

int ans = INT_MAX;

for (int i = start + m - 1; i < end - m + 1; i++)

{

int l = split(v, start, i, m, dp);

int r = split(v, i + 1, end, m, dp);

if (l == INT_MIN || r == INT_MIN)

{

ans = max(ans, v[end] - v[start]);

}

else

{

ans = min(ans, max(l, r));

}

}

return dp[start][end] = ans;

}

int fun(vector<int> &nums, int m)

{

sort(nums.begin(), nums.end());

int n = nums.size();

vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));

if (n < 2 * m)

{

return nums[nums.size() - 1] - nums[0];

}

int ans = INT_MAX;

for (int i = m - 1; i < n - m; i++)

{

int l = split(nums, 0, i, m, dp);

int r = split(nums, i + 1, n - 1, m, dp);

ans = min(ans, max(l, r));

}

return ans;

}

int main()

{

// vector<int> a = {5, 11, 13, 4, 12};

vector<int> a ={93, 32, 88, 9, 58, 15};

cout <<fun(a, 3);

}