Lent Money - debug

Code
I tried various test cases, all of them work fine, please take a loot at my code (python) and help me debug it. I have indented code properly and tried to explain as mush as I can through comments, if something is not clear comment it down I’ll explain it. Thank You

Some clue for you.
There are three cases you need to take care of

  1. If k == n and you know what to do

The other two case are tricky.
In those cases whatever k may be you will be able to pick up elements in a pair. How?

Ans - Take a element you want to pick and k - 1 other random elements. In next turn take the 2nd term of your pair and all the other k - 1 which was taken previously. So now you only changed the value of two bags although k was very big.

Check out my code here https://www.codechef.com/viewsolution/24560777

1 Like

I can tell the test case in which your code is failing.
1
6
0 0 0 0 0 0
4
1

arr = list of Ai
Let list_A = List of elements which increase(x^arr[i]>0) on performing xor operation

Let list_B = List of elements which decrease(x^arr[i]<=0) on performing xor operation

Precisely let both the list contain |arr[i] - x^arr[i]|

Consider the following cases(Only for n!=K):

if(k%2==1) //if k is odd-
It is always possible to increase all the elements in list_A.
Why? Try it

if(k%2==0) //if k is even-
Only even number of elements can be increased in each operation. So
if(least_element in list_A - least_element in list_B > 0) then it is advantageous to include both and make it even.
else
leave out the least_element in list_A.

Other special cases:
n==k:
perform the operation only if it is advantageous(sum(list_A)>sum(list_B))

size(list_A) == 0:
No operation is performed

Hope it helps!!

You can also watch this video : https://www.youtube.com/watch?v=yMuaIjKlTfg to understand my approach.

1 Like