samadeep's blog

An Interesting Dyanmic Programming + Binary Search Problem

By samadeep, history, 12 months ago, In English

An array arr of n integers is to be divided into different groups such that each element belongs to exactly one group and the size of each group is at least m.

The cost of the division is defined as the maximum value of the difference between the maximum and minimum elements of a particular group. For example, if an array [1, 2, 3, 4, 5] is divided into two groups [1, 3], [2, 4, 5], the cost is max(3 — 1, 5 — 2) = 3

Given arr and an integer m, find the minimum possible cost of dividing the array into groups of size greater than or equal to m. Example : Suppose n = 5, arr = [5, 11, 13, 4, 12], and m = 2. It is optimal to divide the array into two groups [5, 4] and [11, 13, 12] with the cost max(5 — 4, 13 — 11) = 2.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me where are we using dp here?. Why binary search isn't sufficient?

Like we can sort the array and do binary search on answer based on if difference X is possible or not

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you have such a approach it would be great if you could share

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why would a greedy approach not work in this case? I can sort the elements in non-decreasing order and greedily take elements in windows of size m or greater in case of extra elements. I think max(window)-min(window) can be maintained to be the lowermost in that case.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just assume it is $$$1 \le n,m \le 10^6$$$. There are bunch of easy $$$O(nlogn)$$$ solutions like this problem. It is almost the same, asking to divide array into subarrays with limitation on the size but cost of subarray is only max insted of max-min.

    I also know one meme problem, with $$$n \le 2.5 * 10^6$$$ and $$$tl =200ms$$$ to force the $$$O(n)$$$ solution.

    I think the $$$O(nlogn)$$$ can be a good challenging problem for people in range of mid~high expert (for reference I solved the first problem in 2.5 hours inside an onsite contest when my rating was swinging between 1890 ~ 1949, my friend who was IM on cf at that point of time solved it in 20mins), but $$$O(n)$$$ is much harder and require good ds skills.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Can you please tell the approach to solve in nlogn

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the downvote ???

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding the downvote i have no idea about !!!

i Know i am not a highly rated coder but in the past few months i have really loved CP and would like any person who like to associate or advice in this journey of mine

Thanks

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    don't mind those boring people who kept downvoting.

    I think if a person downvote some topics which are not meaningless, he is noob

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      True... sometimes i find no reason for it .. i hope the cf community becomes more accepting

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the order in which we divide affect the outcome? For instance, when dividing into three parts, are we referring to std::max(1,2,3), or is it a case of first dividing into two parts and then dividing one of those parts into two again?

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oh, I guess I got it. It's meaningless to have order. So I think it's always better to take combinations in non-decreasing order.

    I'm not sure the code below is right or not. you can test it with your input like:

    5 2

    5 11 13 4 12

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

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> vec(n);
    for (int &num : vec)
    {
        cin >> num;
    }
    std::sort(vec.begin(), vec.end());
    std::vector<int> dp(n+1, 0);
    for (int i = m; i <= n; i++)
    {
        dp[i] = vec[i - 1] - vec[0];
        for (int j = m; j <= i - m; j++)
        {
            dp[i] = std::min(std::max(dp[j], vec[i - 1] - vec[j]), dp[i]);
        }
    }
    cout << dp[n] << endl;
}

int main()
{
    // freopen("input.txt", "r", stdin);
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      7 2
1 2 3 2000 2001 2003 2004

      I tested this with this input and the answer is 2 I think it works Great !!!

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just some obvious open-close interval trick. You can learn more at "Non-trivial DP tricks and Tecniques" blog on codeforces.

→ Reply