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
- 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 CodeChef: Practical coding for everyone
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 : Codechef JUNE Challenge 2019 | Lent Money | LENTMO - YouTube to understand my approach.