MAXORSUM - Editorial

PROBLEM LINK:

Practice
Contest

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).

1 Like
//