A supercomputer has several processors to deploy for execution. They are arranged sequentially in a row from 1 to n. The efficiency of each processor depends upon the order of deployment of its adjacent processors. For the ith processor, the efficiency of the th processor is no adjacent[in], one adjacent[i], or both adjacent[i] when neither, one, or both adjacent processors is deployed before processor i. Note: The 1st and nth processors can only have one adjacent. Find the maximum possible sum of efficiencies amongst all possible orders of deployment.↵
↵
Example↵
↵
There are n = 4 processors.↵
↵
no_adjacent = [1, 2, 3, 4]↵
↵
one_adjacent = [4, 4, 2, 1]↵
↵
both_adjacent = [0, 1, 1, 0]↵
↵
Consider the following orders of deployment (1- based indexing):↵
↵
The deployment sequence is (1→3→4→2).↵
↵
Then, the sum of efficiencies = no_adjacent[1] +↵
↵
no_adjacent[3] + one_adjacent[4] + both_adjacent[2]=1+3+1+1=6.↵
↵
Let the deployment sequence be (4→2→1→3),↵
↵
no adjacent[4] + no adjacent[2] + one adjacent[1] + both_adjacent[3]=4+2+4+1=11.↵
↵
Let the deployment sequence be (4-3-2-1),↵
↵
no_adjacent[4] + one_adjacent[3] + one_adjacent[2] + one_adjacent[1] = 4+2+4+4=14.↵
↵
.↵
↵
Similarly, other deployment orders can be performed.↵
↵
Amongst all possible deployments, the maximum possible sum of efficiencies is 14.↵
↵
**Constraints **↵
↵
2 ≤ n ≤ 10^5↵
↵
1 ≤ no_adjacent[i], one_adjacent[i],↵
↵
both adjacent[i] ≤ 10^9↵
↵
↵
↵
I was trying to solve this question Can anyone help me? (published)
↵
Example↵
↵
There are n = 4 processors.↵
↵
no_adjacent = [1, 2, 3, 4]↵
↵
one_adjacent = [4, 4, 2, 1]↵
↵
both_adjacent = [0, 1, 1, 0]↵
↵
Consider the following orders of deployment (1- based indexing):↵
↵
The deployment sequence is (1→3→4→2).↵
↵
Then, the sum of efficiencies = no_adjacent[1] +↵
↵
no_adjacent[3] + one_adjacent[4] + both_adjacent[2]=1+3+1+1=6.↵
↵
Let the deployment sequence be (4→2→1→3),↵
↵
no adjacent[4] + no adjacent[2] + one adjacent[1] + both_adjacent[3]=4+2+4+1=11.↵
↵
Let the deployment sequence be (4-3-2-1),↵
↵
no_adjacent[4] + one_adjacent[3] + one_adjacent[2] + one_adjacent[1] = 4+2+4+4=14.↵
↵
.↵
↵
Similarly, other deployment orders can be performed.↵
↵
Amongst all possible deployments, the maximum possible sum of efficiencies is 14.↵
↵
**Constraints **↵
↵
2 ≤ n ≤ 10^5↵
↵
1 ≤ no_adjacent[i], one_adjacent[i],↵
↵
both adjacent[i] ≤ 10^9↵
↵
↵
↵
I was trying to solve this question Can anyone help me? (published)
