9 weeks ago

John 910

Hyderabad

Question 1

Odd Subset

Question 2

Range Sum Query 2.0

21 months ago

Yash Sahijwani 940

Solution to Range Sum Query 2.0

Analysis

In the question it is mentioned that we have an array of length R-L+1 consisting of consecutive numbers from L to R, i.e. the array is of the form L, L+1, L+2, ..., R-1, R and we are also given Q queries, X and Y in which we need to answer whether there exists a subsequence of this array such that the sum of this subsequence lies between X and Y.

We can approach this problem by first seeing what happens if we fix the length of the subsequence we are taking. Let us say the length of the subsequence we are taking is a. Then, the minimum value we can get from a subsequence of length a will be the sum of the first a terms (since the array is in strictly increasing order). So the minimum value will be L + (L+1) + (L+2) + ... + (L + a - 1). Now the maximum value we can get from a subsequence of length a will be the sum of the last a terms (since the array is in strictly increasing order). So the maximum value will be R + (R-1) + .. + (R-a+1). Now if we look carefully we can see that by taking a subsequence of length a we can always form all possible values between the maximum and the minimum.

Say you have taken the first a elements, then to increase this sum by 1, we just increase the last element i.e. L+a-1 to L+a. To increase the overall sum, we keep on increasing this last term till it becomes R. Then to further increase the sum, we increase the 2nd last element i.e. L+a-2 to L+a-1, and we keep doing so till the values become R + (R-1) + .. + (R-a+1). So we can form all values between the maximum and minimum for each length.

So for some length a, we can think of the possible sums that can be made as an interval [min, max]. These min, max values can be calculated in O(1) for each length. Now this [min, max] should overlap with the interval [X, Y], So if the min value is greater than Y, then taking any subsequence equal to or greater than that length will not work, since its minimum value will be greater than Y. So if this happens, we look at lengths lesser than the current length.

Now if the min value is less than Y, then for the intervals to overlap, the max value should be greater than or equal to X. If it is less than X, it means that taking such a length, or length lesser than that will result in a maximum value lesser than X which will not work. So we look at lengths greater than that.

So we can use Binary Search over the possible lengths of the subsequence, and in case at any point the intervals overlap, we break and output the answer as 1, otherwise we keep iterating till the end of Binary Search and output the answer as 0. Since Binary Search takes logn time, the time complexity will be O(logn).

Implementation

ll q,l,r;
cin > > q > > l > > r;
while(q--)
{
    ll x,y;
    cin > > x > > y;
    ll left = l;
    ll right = r;
    bool possible = false;
    while(left < = right)
    {
        ll mid = (left+right)/2;
        ll sum = (mid*(mid+1))/2 - (l*(l-1))/2;
        if(sum < = y)
        {
            ll length = mid-l+1;
            ll lower = r-length;
            ll max_sum = (r*(r+1))/2 - (lower*(lower+1))/2;
            if(max_sum > = x)
            {
                possible = true;
                break;
            }
            else
                left = mid+1;
        }
        else if(sum > y)
            right = mid-1;
    }
    if(possible)
        cout < < 1 < < '\n';
    else
        cout < < 0 < < '\n';
}

8 months ago

Akshay Sharma 990

Chandigarh

Question 1

Overview

We have to choose the maximum subset whose sum is odd.

Intution/Solution

• The first observation we can conclude that the sum of two odd numbers is even while the sum of two even numbers is even and thesum of one odd and any number of even is also odd`.
• From the above observation, we can say that if the number of even integers does not matter we are going to choose all even numbers if we have at least one odd number.
• Basically, the answers that are possible for this question are -1, length of array, and length of array-1.
• -1 will be the answer if there is no odd number is the given array means we can't for an odd sum with even numbers ever.
• Answer will be equal to length_of_array if the number of the odd elements present in the array is equal to the odd in such case we are able to choose the whole set as a subset.
• Answer will be the lenght_of_array-1 when the number of the odd element present in the array is even in that case we simply remove one element from the array that is odd.
  • Time Complexity: O(N)

Pseudo Code

  int odd = 0;
for (int i = 0; i < n; i++)
{
    cin >> a[i];
    if (a[i] % 2)
    {
        odd++;
    }
}
if (odd % 2 != 0)
{
    cout << n << "\n";
}
else if (odd == 0)
{
    cout << -1 << "\n";
}
else
{
    cout << n - 1 << "\n";
}