Question 1

Click here to Practice

1.1 1.2

Question 2

Click here to Practice

2.1 2.2

ADD COMMENT • link

Entering edit mode

Solution for Simply Equal

Analysis

In the problem it is mentioned that in one operation we can select any non empty subsequence of the array and decrease all the elements in this subsequence by 1. Our goal is to find the minimum number of such operation such that the all the elements of the array become equal.

Let us say that MAX is the maximum value in the array and MIN is the minimum value in the array. We want that all the elements become equal to MIN, since we can't increase MIN (only decrease operations are allowed). Also, we don't want to go below MIN since that will only take more operations. Now, every operation can be carried out by selecting all elements of the array which are greater than MIN, and decreasing all of them by 1. Due to this some will become equal to MIN (those which were MIN+1 before the operation was carried out), and values of others will decrease. We keep on doing this till all of the elements become equal to MIN.

We notice here that the total number of operations it will take is MAX-MIN, since at every operation we decrease the elements by 1, and MAX is the maximum element in the array so it will take MAX-MIN operations to decrease it to MIN. After MAX-MIN operations, all elements will be equal to MIN. Hence, the minimum number of operations will be MAX-MIN.

Implementation

ll maxi = 0;
ll mini = LLONG_MAX;
for(ll i=0;i &lt; n;i++)
{
    maxi = max(maxi, a[i]);
    mini = min(mini, a[i]);
}
ll ans = maxi-mini;

ADD COMMENT • link 2.1 years ago Yash Sahijwani 940

Entering edit mode

Question 2

Analysis/Approach

Even though the final code for this problem is very short, it is not very intuitive to find the answer. In the solution below, we'll focus on finding all subsequences (including empty ones), and subtract the empty subsequence at the end.
Let's try for a dynamic programming solution. In order to not repeat work, our goal is to phrase the current problem in terms of the answer to previous problems. A typical idea will be to try to count the number of states dp[k] (distinct subsequences) that use letters S[0], S[1], ..., S[k].
Naively, for say, S = "1,2,3,18", we have dp[k] = dp[k-1] * 2. This is because for dp[2] which counts ("", "1", "2", "3", "1,2", "1,3", "2,3", "1,2,3"), dp[3] counts all of those, plus all of those with the x ending, like ("x", "1,x", "2,x", "3,x", "2,3,x", "1,2,x", "2,3,x", "1,2,3,x"). Here's a visualization for this array.
However, for something like S = "1,2,1,2", let's play around with it. We have:
- dp[0] = 2, as it counts ("", "1")
- dp[1] = 4, as it counts ("", "1", "2", "1,2");
  - dp[2] = 7 as it counts ("", "1", "2", "1,1", "1,2", "2,1", "1,2,1");
- dp[3] = 12, as it counts ("", "1", "2", "1,1", "1,2", "2,1", "2,2", "1,1,2", "1,2,1", "1,2,2", "2,1,2", "1,2,1,2").
We have that dp[3] countsdp[2], plus ("2", "1,1", "1,2", "2,1", "1,2,1") with"2"added to it.
Notice that("", "1")are missing from this list, as they get double counted. In general, the sequences that resulted from putting"2" the last time (ie."2", "1,2"`) will get double counted. Here's a visualization for an array with repeated letters.
This insight leads to the recurrence:
- dp[k] = 2 * dp[k-1] - dp[last[S[k]] - 1]
The number of distinct subsequences ending at S[k], is twice the distinct subsequences counted by dp[k-1] (all of them, plus all of them with S[k] appended), minus the amount we double counted, which is dp[last[S[k]] - 1].
Complexity Analysis
- Time Complexity: O(N), where N is the length of the Array.
- Space Complexity: O(N).

Code : `

    vector&lt;int&gt; dp(N+1);
    dp[0] = 1;
    vector&lt;int&gt; last(1e6, -1);

    for(int i = 0; i &lt; N; i++){
        int x = s[i];
        dp[i+1] = dp[i] * 2 % MOD;
        if(last[x] &gt;= 0) // if this is the first occurence of element
            dp[i+1] -= dp[last[x]];
        dp[i+1] %= MOD;
        last[x] = i;
    }
    dp[N]--;
    if(dp[N] &lt; 0) dp[N] += MOD;
    return dp[N];`

ADD COMMENT • link 2.1 years ago Akshay Sharma 990

Entering edit mode