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 : https://www.codechef.com/viewsolution/26788339

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?