1 day ago

admin 1.9k

Hyderabad

Question 1: Array Nullification

Problem Statement:

You are given two arrays, change and arr, of lengths n and m, respectively. In each operation, you can perform one of the following:

1. You can decrement any element of arr by 1.

2. If change[i] > 0 and arr[change[i]] = 0, you can change that element to NULL.

Assume 1-based indexing and find the minimum number of operations required to change all elements of the array to NULL, or report -1 if not possible.

Example:

n = 4, m = 2

change = [0, 1, 0, 2]

arr = [1, 1]

Operations sequence:

1. Decrement arr[1]: [0, 1]

2. Change arr[1] to NULL since change[2] = 1 and arr[1] = 0: [NULL, 1]

3. Decrement arr[2]: [NULL, 0]

   (... sequence continues to nullify the remaining elements)

Question 2: Minimum Complexity Level

Problem Statement:

Alex is attending a software engineering conference in which various lectures are presented. The subject matter of each lecture has a certain complexity. Alex has planned the order of lectures they would like to attend, but now they need to schedule these into several days.

Their goal is to attend at least one lecture every day and to plan the lectures in a way that minimizes the overall complexity of the conference. (Each day's complexity is defined as the complexity of the most complex lecture attended that day.)

Given the complexity levels of the lectures, as well as how many days the conference is being held, what is the overall minimum complexity that can be achieved with optimal planning?

Example:

For example, let's say there are n = 5 lectures, where complexity = [1, 5, 3, 2, 4], and the length of the conference is days = 2.

(Note that complexity denotes both the complexity of each lecture as well as the order in which they need to be attended...)

1 day ago

admin 1.9k

Hyderabad

Solution-1 (Array Nullification )

Topics Involved / Prerequisites

• Binary Search on Answer
• Greedy Algorithms
• Array Processing

Overview

• To find the minimum number of days to nullify all elements, we can binary search the optimal day, as any day after a valid solution is also valid.
• To verify if a specific number of days is sufficient, we act greedily by taking each exam (nullification) on its latest possible occurrence within that timeframe.
• We iterate through the days, accumulating available "decrement" operations and expending them when we are forced to nullify an element on its last available day.

Approach

1. Binary Search the Answer

The minimum possible days is 1 and the maximum is n. If we cannot satisfy the array in ndays, the answer is 1. We binary search a target day mid.

2. Validating the Target Day (Greedy Check)

For a guessed day mid, we first scan the change array from day 1 to mid and record the last occurrence of every required element 1 to m. If any element does not appear in this window, mid is immediately invalid.

Then, we simulate the process from day 1 to mid:

• If the current day is NOT the recorded last occurrence of its respective element, we use this day as a free "decrement" operation (incrementing a study_days counter).
• If the current day IS the last occurrence of an element E, we must nullify it today. This requires arr[E] accumulated decrement operations. If study_days < arr[E], we fail. Otherwise, we subtract arr[E] from study_days and proceed.

C++ Implementation -: 

#include <iostream>
#include <vector>

using namespace std;

// Helper function to check if all elements can be nullified in 'mid' days
bool check(int mid, const vector<int>& change, const vector<int>& arr, int n, int m) {
    vector<int> last_occ(m + 1, 0);
    
    // Find the latest possible day to process each element within the 'mid' window
    for (int i = 0; i < mid; i++) {
        if (change[i] > 0) {
            last_occ[change[i]] = i + 1; // 1-based day tracking
        }
    }
    
    // If any element doesn't appear at all in the window, it's impossible
    for (int i = 1; i <= m; i++) {
        if (last_occ[i] == 0) {
            return false;
        }
    }
    
    int study_days = 0;
    for (int i = 0; i < mid; i++) {
        int element = change[i];
        
        // If today is the absolute last day to nullify this element
        if (element > 0 && last_occ[element] == i + 1) {
            // Check if we have enough accumulated decrements
            if (study_days < arr[element - 1]) {
                return false;
            }
            study_days -= arr[element - 1]; // Consume the decrements
        } else {
            // Otherwise, we use today to build up our decrement operations
            study_days++;
        }
    }
    
    return true;
}

int minOperationsToNullify(const vector<int>& change, const vector<int>& arr, int n, int m) {
    int low = 1, high = n, ans = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid, change, arr, n, m)) {
            ans = mid;       // Valid, try to find a smaller day
            high = mid - 1;
        } else {
            low = mid + 1;   // Invalid, we need more days
        }
    }
    
    return ans;
}

Time Complexity

• Time:O(N log N) - The binary search space is N. For each step, our validation check iterates through the array in O(N) time.
• Space:O(M)- We need an auxiliary array of size M+1 to store the last occurrence of each element during the validation step.

1 day ago

admin 1.9k

Hyderabad

Problem2 Solution

Minimum Complexity Level Solution

Topics Involved / Prerequisites

• Dynamic Programming (2D)
• Array Partitioning

Overview This problem requires splitting a contiguous array into exactly k subarrays (days) such that the sum of the maximums of each subarray is minimized. We can solve this using dynamic programming by defining a state that tracks how many lectures have been scheduled and how many days have been used. By iterating backwards through the remaining unscheduled lectures, we dynamically identify the maximum complexity of the current day and add it to the optimal history of previous days.

Approach

1. DP State Definition Let dp[i][j] be the minimum complexity to schedule the first i lectures across exactly j days. We initialize all states to infinity (1e9), except the base case dp[0][0] = 0 (0 lectures in 0 days costs 0).

2. State Transitions To calculate dp[i][j], we iterate through a split point k representing the number of lectures completed by the end of day j - 1. k ranges from j - 1 (since j-1 days require at least j-1 lectures) up to i - 1. The lectures scheduled exactly on day j will be from index k to i - 1. As we evaluate each k backwards, we maintain the maximum complexity in this block and update our DP:

C++ Implementation-:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9; // 10^9 to prevent integer overflow during addition

int minComplexity(const vector<int>& complexity, int n, int days) {
   
    if (n < days) return -1;
    
   
    vector<vector<int>> dp(n + 1, vector<int>(days + 1, INF));
    
    dp[0][0] = 0;
    
    // Fill DP table
    for (int j = 1; j <= days; j++) {
        for (int i = j; i <= n; i++) {
            int current_day_max = 0;
            
            // Try all valid split points k for the previous day's boundary
            for (int k = i - 1; k >= j - 1; k--) {
             
                current_day_max = max(current_day_max, complexity[k]);
         
                if (dp[k][j - 1] != INF) {
                    dp[i][j] = min(dp[i][j], dp[k][j - 1] + current_day_max);
                }
            }
        }
    }
    
    return dp[n][days];
}

Time Complexity

• Time: O(N^2 * D) - Where N is the number of lectures and D is the number of days. For each of the N*D states, we scan back up to N elements to find the optimal split.

Space: O(N * D) - To store the 2D DP matrix. (Can be optimized to O(N) if only storing the previous day's row, but 2D is standard and safer for tracking).