I understood the question, but can someone plz explain the solution? How to solve it?
Looks like there’s a decent write-up here:
Do you want solution or you want to understand question ?
Ya, I want solution explained in a very easy-to-understand manner.
BTW, my solution:
https://www.codechef.com/viewsolution/26885925
Okay so I will try my best to explain you.
Algorithm :
- Sort them and remove values less than k. And subtract other values by k (Also, Add values less than k to final “ans” and also add “k” for all other values (because we subtracted it) ).
- find (sum - max - 2nd_max) , ( max) , (2nd max)
3) Let’s start main algorithm,
a = (sum - max - 2nd_max)
b = 2nd max
c = max
if(a < b)
ans+=c - (b-a)
else if( a%2 != b%2) // if parity is not equal
ans+=c-1;
else
ans+=c;
How does this work ?
Case 1 :
if a (sum of all numbers except max and 2nd max) is less than b (2nd max)
then there is no choice but subtracting “all numbers except max and 2nd max” from “2nd max”. And then subtracting remaining value of “2nd max” from “max”.
Case 2:
Now if a (sum of all numbers except max and 2nd max) is greater than or equal to b (2nd max)
Then we keep subtracting 2 from a (given we have at least two elements in a, which will always be the case because they are “sorted” and “a is more than b”) till it becomes case 1 ( select any two except “max” and “2nd max” and decrease them by 1 each).
Let me know if its still unclear 
My implementation : CodeChef: Practical coding for everyone
It’s horribly written.
You mean his code of my code or my answer ?
I mean the question, I remember when I first read it, I wasn’t able to understand it until my roommate explained it to me, lol, I thought I suck at understanding, but turns out the author, apparently admin2 sucks at writing.
ohh XD
I disagree,
I found it good enough to understand though.
How can we subtract k from all those values greater than k, to ans, because that can happen only if there are even no of those values, otherwise how will we pair them up?
Sample Input:
**3**
**2 1**
**1 2**
2 1
2 2
3 1
2 3 2
Sample Output:
**3**
2
5
It is easy question.
Let’s do first output…
You have 3 test cases
Array of two integers and your k is and will be 1
You go to your array next line and you choose two a’s in this case a1 =1 and a2=2
Min(a1,a2)=1
So no decrement will happen here
And your maximum sum for what you get left in your array here in this case is 3.
Did you understand or you need the rest test cases explain.
what would be the answer for
5 5
4 4 6 6 9
There will be repetion put that in mind .
We choose a1and a2 random but here we will not chhose them again only this time let say a1=4and a2 =4 min(a1,a2) <k =5 so no decrement In this case and summation 29
Then do other choice for the a’s and that other case and other summation answer.
I believe you need to paires for getting the maximum summation ,paired for the a’s.
Like (a1=4,a2=6) (a1=6,a2=6) (a1=6,a2=9)
But the maximum summation (5,5) or (5,8) both min =5 so no more decremntal will happen here but we have two max sum 4 4 5 5 9
Or 4 4 5 6 8
Idont know if they do more decrement after the first decrement .
Seems like you misunderstood the statement.
if(j<a[n-2])
cout << ans+a[n-1]-(a[n-2]-j) << “\n”;
else if((j%2)!=(a[n-2]%2))
cout << ans+a[n-1]-1 << “\n”;
else
cout << ans+a[n-1] << “\n”;
I’m not getting this
4 4 6 6 9
ans = 4 +4+5+5+5
Make it
0 0 1 1 4
Now
0 0 0 0 4
ans+=4
Have you read my answer instead of code ?
I wrote everything there.
Click on
"How does this work ? "
Read my answer 2-3 times and you’ll get it.
Which portion of code takes care of case 2? And why that parity code?
And my code breaks at this test case:
10 5
3 3 3 4 5 7 8 9 43 76
Can you tell what is the answer for it, showing manually the pairs we will pick up?