Question: Edgeverve, Recently Asked Questions in IIT-BHU, November, 2022
0
Entering edit mode

# Question 3

3
Entering edit mode

Question 1

`Solution:`

• Let the maximum absolute difference occur between Element \$i\$ and \$i+1\$, then, the maximum difference be `Diff = A[i]-A[i+1]`
• So insert a number between `i` and `i+1`, which is equal to `A[i]+diff/2`. The cost reduces by a value of `(diff^2 - (diff/2)^2 - ((diff+1)/2)^2)`
• Also note that adding a number at the front or last just increases the difference and does not decrease it.

`Pseudocode:`

``````long long getMinCost(vector&lt;int&gt; arr)
{
long long cost = 0;
long long diff = 0;
for (long long i = 0; i &lt; arr.size() - 1; i++)
{
diff = max(diff, abs(arr[i] - arr[i + 1]));
cost += (arr[i] - arr[i + 1]) * (arr[i] - arr[i + 1]);
}
return (cost - diff * diff + (diff / 2) * (diff / 2) + ((diff + 1) / 2) * ((diff + 1) / 2));
}
``````

`Complexity:`

• `O(N)`
2
Entering edit mode

Question 2

`Solution`

• Precompute the prime or composite for every number until `10^4` (maximum value of A[i]) using prime sieve
• Find the number of prime and composite in the given array
• If no of prime = no of composite
• Then output `0`
• Ordering is of the form `PCPC......CP`
• Else
• `x = (min(no of prime, no of composite)`
• `ans = total sum - (sum of maximum x primes + sum of maximum x non-primes + (x+1)^th maximum of maximum element type(prime/composite)`
• let then maximum type(prime/composite) be denoted by `M`, minimum type by `m`
• Order is of the form `MmM.......MmM`.

`Pseudocode:`

``````int minPenalty(vector&lt;int&gt; arr)
{
vector&lt;bool&gt; is_prime(10001, true);
is_prime[0] = is_prime[1] = false;

for (int i = 2; i &lt;= 10000; i++)
if (is_prime[i] &amp;&amp; (long long)i * i &lt;= 10000)
for (int j = i * i; j &lt;= 10000; j += i)
is_prime[j] = false;
int count = 0;
vector&lt;int&gt; primes;
vector&lt;int&gt; nonprime;
for (int i = 0; i &lt; arr.size(); i++)
{
if (is_prime[arr[i]])
{
count++;
primes.push_back(arr[i]);
}
else
nonprime.push_back(arr[i]);
}

sort(primes.begin(), primes.end());
sort(nonprime.begin(), nonprime.end());
int ans = 0;

if (2 * count == arr.size())
return 0;
else
{
int x = min(count, (int)arr.size() - count);
for (int i = 0; i &lt; primes.size() - x; i++)
ans += primes[i];
for (int i = 0; i &lt; nonprime.size() - x; i++)
ans += nonprime[i];
if (2 * count &lt; arr.size())
ans -= nonprime[nonprime.size() - x - 1];
else
ans -= primes[primes.size() - x - 1];
}
return ans;
}
``````

`Complexity:`

• `O(NloglogN)`,where `N=10^4`
2
Entering edit mode

Question 3

`Solution:`

• To get the maximum number of positive prefix sums, the arrays should be sorted in descending order
• Sort the arr in descending order and count the number of positive prefix sums

`PseudoCode:`

``````long long  maxPosPrefixes(vector&lt;long long &gt; arr)
{
sort(arr.rbegin(), arr.rend());
long long prefixsum = 0;
long long  ans = 0;
for (long long  i = 0; i &lt; arr.size(); i++)
{
prefixsum += arr[i];
if (prefixsum &gt; 0)
ans++;
else
break;
}
return ans;
}
``````

`Complexity:`

-`O(NLOGN)`