Problem1 :
Given a string S, find for all substrings of S the minimum cost of operations needed to make each of its substring a palindrome. In one operation you can,
1) Either rearrange the substring with cost 0 or, 2) Replace a character with cost 1
I came up with a O(26 * N * N) solution, but the constraints N <= 1e5. How to solve it?
Problem2:
Given an array weight[] and profit[] (similar to Knapsack Problem) you are also given the size of the knapsack W. you need to find a subset whose bitwise OR is <= W and the profits are maximum. Constraints : N <= 1e5, weight[i] <= 1e9, W <= 1e9, profit[] <= 1e9.
Thanks for the help in advance!!!
Problem 2:
Initially take all items with weight[i] <= W, because if weight[i] > W, that item can never be part of any valid subset.
Let x be the OR of all currently active weights, sum be the total profit, freq[b] be the number of active items having bit b set, and cost[b] be the total profit of active items having bit b set.
Now scan bits from MSB to LSB. Maintain carry = total profit already forced to be removed.
If x[b] = 1 and W[b] = 0, then all active items having bit b set must be removed, otherwise the OR will remain greater than W. While removing them, update freq, cost and x. Let the profit removed in this step be removed. If after this x <= W, update the answer with carry + removed and stop. Otherwise add removed to carry and continue.
If x[b] = 1 and W[b] = 1, we can choose to make this bit 0 by removing all active items having bit b set. Once this happens, the OR becomes strictly smaller than W at the first differing bit, so lower bits do not matter. Hence the candidate loss is carry + cost[b].
So for every matching 1,1 bit: mini = min(mini, carry + cost[b]);
For every forced 1,0 mismatch, remove all corresponding active items and update everything.
Finally: answer = sum — mini; If initially x <= W, then the answer is simply sum.
Complexity: O(30 * n).