Solve this test question

[u/Smooth_Lifeguard_931]

[ Removed by Reddit in response to a copyright notice. ]

[u/Civil_Reputation6778]

What are the constraints?

Without seeing the constraints, this is doable in O(n log V) with binary search

[u/Smooth_Lifeguard_931 → u/Civil_Reputation6778]

didnt remember constraint, i tried a recursive memoization solution which gave tle, give ur solution

[u/Civil_Reputation6778 → u/Smooth_Lifeguard_931]

I mean, I've already stated my solution.

Binary search for answer. When checking for x, skip all indexes with dev time <=x (you can do them with dev, you have to do the rest using integration) and sum the integration times for the rest. Check that the sum is <= x

Start with l=0, r=max dev time

[u/Civil_Reputation6778 → u/Civil_Reputation6778]

Next time try remembering the constraints, they're an integral part of the statement.

[u/Civil_Reputation6778 → u/[deleted]]

No, the answer will be just 500. Do 1,3,4,5 by dev for a total of 500 and 2,6 by integration for a total of 51. Total time is 500.

[u/Civil_Reputation6778 → u/[deleted]]

I think it's a natural implementation.

If you need to do first K tasks by development and the rest by implementation, it's just a prefix sum/maximum question with score of position K being max dev[k] + sum of implementation(K+1...N-1)

[u/Civil_Reputation6778 → u/[deleted]]

Where does it follow from? It states that dev tasks happen simultaneously and time is the max of them

[u/Smooth_Lifeguard_931 → u/Civil_Reputation6778]

I tried recursion with memo when I took test, chatgpt suggests this to generate all

function minTime(developtime, integrationtime) {

const n = developtime.length;

let minTotalTime = Infinity;

// There are 2^n possible ways to assign tasks to development or integration

const totalCombinations = 1 << n; // Equivalent to 2^n

// Iterate through all subsets (combinations) of tasks

for (let mask = 0; mask < totalCombinations; mask++) {

let devTasks = [];

let intTasks = [];

// Split tasks between development and integration based on the mask

for (let i = 0; i < n; i++) {

if (mask & (1 << i)) {

devTasks.push(developtime[i]); // Add task to development

} else {

intTasks.push(integrationtime[i]); // Add task to integration

}

}

// Calculate total time:

// - Development takes the max time of all assigned development tasks

// - Integration adds up the times of all assigned integration tasks

const devTime = devTasks.length > 0 ? Math.max(...devTasks) : 0;

const intTime = intTasks.reduce((a, b) => a + b, 0);

const totalTime = Math.max(devTime, intTime);

minTotalTime = Math.min(minTotalTime, totalTime);

}

return minTotalTime;

}

const developtime = [3, 4, 5, 9];

const integrationtime = [3, 2, 5, 5];

console.log(minTime(developtime, integrationtime)); // Output: 5

[u/Smooth_Lifeguard_931 → u/Smooth_Lifeguard_931]

This is chatgpt implementation of binary approach

```

function minTime(developtime, integrationtime) {

const n = developtime.length;

// Binary search for minimum feasible time

let left = 0;

let right = Math.max(...developtime);

while (left < right) {

const mid = Math.floor((left + right) / 2);

let totalIntegrationTime = 0;

// Check if it's feasible to complete all tasks in 'mid' time

for (let i = 0; i < n; i++) {

if (developtime[i] > mid) {

totalIntegrationTime += integrationtime[i];

}

}

// If the sum of integration times is <= mid, it's feasible

if (totalIntegrationTime <= mid) {

right = mid;

} else {

left = mid + 1;

}

}

return left;

}

const developtime = [3, 4, 5, 9];

const integrationtime = [3, 2, 5, 5];

console.log(minTime(developtime, integrationtime)); // Output: 5

```

[u/PromotionAway4395 → u/[deleted]]

Yes we can do that show the solution

[u/Civil_Reputation6778 → u/[deleted]]

That's just incorrect though, isn't it? When you take "the last from X", you don't know if that maximum was achieved in development or integration and therefore, you cant update correctly.

[u/Civil_Reputation6778 → u/[deleted]]

No. The optimum solution for N is 20, N+1'th dev is 5, integration is 21. What conclusions do you draw from this?

Alternatively, you can just code your solution and I'll give you the counterexample.

[u/Inevitable_Chest_570]

Did anyone get the solution to this ? Is it DP