PROBLEM LINK:
Author: Mahmoud Badawy
Tester: Mohammed Ehab
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Greedy, Sorting
PROBLEM:
Given two arrays A and B and a number k you have to replace exactly k elements from A with their XOR value with B find the maximum sum you can get
QUICK EXPLANATION:
Sort the elements by their A[i]^B[i]-A[i] and chose the best K
EXPLANATION:
If you used a magic spell on the i-th element it will increase the sum by A[i]^B[i]-A[i] so you can find the best K elements which will increase your sum and use the magic spells on them
Complexity : O(n*log(n))
Score: 100 points
ALTERNATIVE SOLUTION:
You can use dynamic programming where dp[i][j]=maximum sum in the first i elements if you used j magic spells on them and the answer will be in dp[n][k]
Complexity : O(n*k)
Score: 50 points
AUTHOR’S SOLUTIONS:
greedy solution can be found here (100 point).
DP solution can be found here (50 point).