Problem D:

You have an array arr containing N integers, which are all initially 0. You need to perform N actions, and in the action you do the following:

  • Choose the subarray with maximum length having all zeroes, if multiple choose one which starts earlier
  • Let it be if length is odd, set otherwise,

Hint 1

  • You just need to implement the algorithm as stated, but need to think how to get the interval on which we need to perform the action easily!

  • As we will process an interval, we put a value in the middle of it, and the left and right intervals will have all zeroes. Next time, we need an interval with larger length, and if length is same, with smaller start index. Can you think of some data structure that can query this quickly for you?

Hint 2
  • What about a priority queue (pq)?
  • Push the interval as {length, {start, end}} pair. Initially, pq will have {n, {0, n - 1}} as the first element.
  • Now, while pq is not empty, pop the element at the front (that should be one with max length and if multiple, with smallest start) so you need to define a custom comparator.
  • Once you pop this interval, update the value at middle, and push the left and right intervals. There are some minute implementation details you need to take care of.
  • Also, note that the maximum no. of intervals in pq will not be more than N, think about it!

Time Complexity

Implementation Details
  • Read priority_queue docs to know more about custom comparators.
  • In short, you can define a struct or class and overrride the () operator inside it.
  • This comparator works different from the custom comparators of sort function, you return exactly the opposite value of what is required.
  • Do check for validity of an interval before pushing to the priority queue. (start must be <= end)

Code

 
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
#define endl '\n'

const int MAXN = 2e5 + 10;
int arr[MAXN];

using mykey = pair<int, pair<int, int>>;
struct mycompare{
    bool operator()(const mykey& k1, const mykey& k2) {
        int l1 = k1.first; // length of first 
        int l2 = k2.first; // length of second
        if (l1 != l2) {
            return l1 < l2; // return 1 if l1 is not larger
        }
        int i1 = k1.second.first; // start index of first
        int i2 = k2.second.first; // start index of second;
        return i1 > i2; // reutrn 1 if i1 is not smaller
    }
};
priority_queue<mykey, vector<mykey>, mycompare> pq;

void solve() {
    int n;
    cin >> n;

    int k = 1; // value to be updated in array, action number

    // push the starting interval (0, n - 1)
    pq.push({n, {0, n - 1}});
    int len, mid, right, left;
    while (!pq.empty()) {
        mykey fr = pq.top(); // max length interval to be chosen
        pq.pop();
        len = fr.first; // length
        left = fr.second.first; // left index
        right = fr.second.second; // right index
        if (left == right) {
            arr[left] = k++; // update the value
            continue;
        }
        // find mid
        if (len & 1) {
            mid = (left + right)/2;
        } else {
            mid = (left + right - 1)/2;
        }
        arr[mid] = k++;
        if (mid + 1 <= right) { // {start, end} should be valid
            pq.push({right - mid, {mid + 1, right}});
        }
        if (left <= mid - 1) {
            pq.push({mid - left, {left, mid - 1}});
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    FAST_IO;

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    
    return 0;
}

Problem C:

Hint 1

Hint 2

Time Complexity

Code

Problem B:

Hint 1

Hint 2

Time Complexity

Code

Problem A:

Hint 1

Hint 2

Time Complexity

Code