Codeforces Round #251 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	150

439A - Devu, the Singer and Churu, the Joker

For checking whether there is a way to conduct all the songs of the singer, you can conduct the event in the following way.

First singer will sing a song.
Then during 10 minutes rest of the singer, the joker will crack 2 jokes(each of 5 minutes)
Then singer will again sing a song, then joker, etc.
After the singer has completes all his songs, the joker will keep on cracking jokes of 5 minutes each.

Hence minimum duration of the even needed such that sing could sing all his songs will be t₁ + 10 + t₂ + 10 + ... +t_n = sum + (n - 1) * 10 where sum denote the total time of the songs of the singer.

So for checking feasibility of the solution, just check whether sum + (n - 1) * 10 ≤ duration or not?.

If it is feasible, then time remaining for joker will be the entire duration except the time when the singer is singing the song. Hence time available for the joker will be duration - sum. In that time joker will sing $\text{[math]}$ songs.

Solution codes

my solution

439B - Devu, the Dumb Guy

You can formulate the problem in following way. Given two arrays a and b. Find minimum cost of matching the elements of array a to b. For our problem the array a will be same as b. The array b will have content x, x — 1, , 1, 1. For a general version of this problem, we can use min cost max flow(min cost matching), but for this problem following simple greedy solution will work.

Sort the array a in increasing and b in decreasing order (or vice versa).
Now match i^th element of the array a with i^th element of array b.

Proof:

It can be easily proved by exchange argument.

Solution Codes

my solution

439C - Devu and Partitioning of the Array

Let us first try to find the condition required to make sure the existence of the partitions.

Notice the following points.

If the parity of sum does not match with parity of number of odd partitions (k - p) , then we can't create the required partitions. eg. a = [1;2], k = 2, p = 0, Then you can not create two partitions of odd size, because then sum of the elements of the partitions of the array will be even whereas the sum of elements of the array is odd.
If number of odd elements in a are less than k - p (number of required partitions with odd sum), then we can not do a valid partitioning.
If number of even elements are less than p, then we can not create even partitions simply by using even numbers, we have to use odd numbers too. Notice the simple fact that sum of two odd numbers is even. Hence we will try to include 2 odd elements in our partitions too. So if we can create oddsRemaining / 2 partitions in which every partition contains 2 odd elements, then we can do a valid partitioning otherwise we can't. Here oddsRemaining denotes the number of odd elements which are not used in any of the partitions made up to now.

Let oddElements denotes the number of odd elements in array a. Similarly evenElements denotes the number of even elements.

So the answer exists if

Number of possible odd partitions are ≥ k - p i.e. oddElements ≥ k - p.
Number of possible even partitions are ≥ p i.e. evenElements + (oddRemaining) / 2 ≥ p. where oddRemaining is oddElements - (k - p).

For generating the actual partitions, you can follow the same strategy used in detecting the existence of the partitions. We will first generate any valid p partitions (forget about the condition of using the entire array), then we can simply include the remaining elements of the array in the last partition and we are done.

Solution Codes

439D - Devu and his Brother

You can solve the problem in two ways.

By using ternary search

Let us define a function f. Function f(k) = cost needed to make array a elements ≥ k + cost needed to make array b elements ≤ k

Instead of proving it formally, try checking the property on many random test cases. You will realize that f is convex.

Claim: f is convex:

Proof:

It is fairly easy to prove. See the derivative of f.

$\text{[math]}$ = — (# of elements of b > k) + (# of elements of a < k)

The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.

So, $\text{[math]}$

By using the fact that optimal values are attainable at the array values:

All the extremum points will lie in the elements from the any of the arrays because f is convex and $\text{[math]}$ at the event points (or the points of array a and b).

For learning more about ternary search, you can see following topcoder discussion

Another smart solution

Please see following comment of goovie and proof is given in the reply by himank

Solutions Code

439E - Devu and Birthday Celebration

There are two possible solutions.

dp solution

Let P(n, f) be total number of ways of partitioning n into f segments such that each a_i is positive. With some manipulations of the generating function, you can find that this is equal to $\text{[math]}$ .

So $\text{[math]}$

Let F(n, f, g) denotes partitions of n into f parts such that gcd of all the a_i's is g.

Note that F(n, f, 1) = P(n, f) — sum of F(n, f, g) over all possible gcd g's. So g will be a divisor of n.

In other words, $\text{[math]}$

As $\text{[math]}$ .

$\text{[math]}$

You can implement this solution by a simple dp.

You can pre-calculate factorials which will help you to calculate $\text{[math]}$ .

Complexity of this solution will be nlogn over all the test cases.

Please note that this solution might get time limit exceeded in Java. Please read the comment.

Mathematical solution

Note that F(n, f, 1) = P(n, f) — sum of F(n, f, g) over all possible gcd g's (g > 1 such that g is a divisor of n.

In other words, $\text{[math]}$

As F(n, f, g) = $\text{[math]}$ .

$\text{[math]}$

Now you have to use Möbius inversion formula.

Theorem:

If f and g are two arithmetic functions satisfying

$\text{[math]}$

then $\text{[math]}$

So In our case: g(n) is P(n, f) and f(n) is F(n, f, 1).

For proving complexity: Use the fact that total number of divisors of a number from 1 to n is $\text{[math]}$

Please also see xorfire comment for understanding the relation between mobius function and the solution using inclusion exclusion principle.

Solution Codes

Comments (94)

Show archived | Write comment?

devilcoderr

11 years ago, # |

← Rev. 3 →

got the solution:)

→ Reply

lfarrives

11 years ago, # ^ |

if your solution wasnt hacked during the duration of the contest then it wouldn't have passed the system tests! only way to prevent a solution from getting hacked is to make a perfect solution with no flaws!

bli0042

This is not true; a lot of people just don't bother to hack so a lot of people, for example, who didn't handle integer overflow ended up failing test 12 on B.

vicky2135

clearing of pretest doesn't mean that your solution is correct. pretest is few test cases which checks your solution. if someone else will see your solution and found it wrong it can hack your solution.

sumanth232

that means... your solution for that problem fails on a test case which the hacker used to test your problem. Your problem gave a wrong answer, so the points you have been awarded are withdrawn (which would anyway become zero in the final system test, if your solution had not been hacked).

Infact this is a good thing. You can resubmit your code by doing necessary corrections , if your problem is hacked. You can submit any number of times in the 2 hour duration unless you locked your solution.

hope this helps....

pscs27

Hi, how did you find derivative and double derivative there?

PraveenDhinwa

It is just found by intuition that "The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.", so double derivative will be >= 0.

thunderking

← Rev. 2 →

I was just going through different submissions of problem C, and came across this solution 6802980 which shows wrong answer for test case 44, but the output seems correct. Could you kindly tell how is that answer wrong?

Got it. Didnt see the number of elements :)

shubh09

The output is supposed to be a partition of the given numbers. The output of the given submission contains only 7 numbers, while the original array contained 9.

It would be great if you could add links to solutions which solve the problem using the ideas described in the editorial.

nice idea, I will do it in just an hour :)

HandIeNeeded

I used a random algorithm to solve the problem D. CLICK

alexpizarroj

Great round setup and nice tutorial. Keep up the good work.

xorfire

It looks like the editorial for E is intended to scare away people :D

First of all, we don't need generating functions to derive that simple formula for P(n, f). It is well known. We don't need to use a tank to kill a mosquito. :P

And the second thing is that we can use simple inclusion exclusion to derive the mathematical solution rather than use mobius inversion (although it is true that both are the same, since when we are using inclusion exclusion, we are basically reproducing the proof of Mobius' Inversion formula). Just saying it would have been better if you had explained that way.

Nevertheless, nice contest and editorial, hope to see more from you in the future :)

Yes, you are right, I will add your comment in the editorial too.

Guliash

But that formula allows us making a_i = 0. What is the proof that $\text{[math]}$ ?

If you need number of solutions to a₁ + a₂ + ... + a_f = n where a_i ≥ 1. It is the same as the number of solutions to b₁ + b₂ + ... + b_f = n - f where b_i ≥ 0 simply by substituting b_i = a_i - 1. Now use the formula given in the link and you end up with the result that you want.

R.A.X

how P(n, f) is equal to it should be equal to according to the link .Please explain.

Read what is given, understand it and then look at my explanation above instead of just looking at the formula and complaining that they don't match.

In the link you mentioned, can you please explain how the balls are matched from the k-1 extra urn to the original n urns??

roll_no_1

6 years ago, # ^ |

The link given in the above comment is not working. So here is the updated link.

himank

← Rev. 5 →

This is my approach to Problem D.
sort array a in increasing order and array b in decreasing order. Now find a index i such that a[i]>=b[i]. Now all elements from 0 to (i-1) in both a and b can be converted to some value X such that b[i]<=X<=a[i].So
ans = (b[0]+...b[i-1]) -X*(i-1) + X*(i-1) -(a[0]+ ...a[i-1]) = (b[0]+...b[i-1])-(a[0]+ ...a[i-1]).

NOTE: if no index is found till end of any one array then i= min(m,n);
6811074

triveni

See this solution(same approach) : solution.

Alladdin

Good idea! I had got something same in my solution, i also sorted arrays in the same way, but i didn't think about such formula and calculated everything step by step... I just understood, that we want to change the smallest amount of numbers as we can. So, every step we have got some already chosen elements in arrays and we think, that they are equal. So, we should choose the array and change chosen elements in it. We can easily see, that we can, for example, increase the elements in first array only to min(b[0], next number in a). If we increase them to b[0], we can stop, if we increase them to next element of a, we should add this next number to chosen elements in a. And, of course, at first, we have got only one element chosen in every array. My solution:6808595

hossain.ruetcse

thank you. himank for your smart solution. I was surprised by seeing this solution.

hereicomewf

10 years ago, # ^ |

What is 2 pointers approach to problem D?

Kaban-5

I don't understand, why E solution has $\text{[math]}$ complexity. Can you explain this a bit clearer? (I know, that there are $\text{[math]}$ pairs of divisors from 1 to n, but I don't understand why it makes this true). Will be very grateful for help.

I am just attaching the solutions in a while, it will be clear then :)

I still don't get it, why the complexity is O(nlogn)?

http://mirror.codeforces.com/contest/439/submission/6814322

In the solution above we run through all the divisors of n. But the number of divisors, as I know, isn't O(logn).

Could you please explain this moment?

moji

after four days... still waiting... :{

Breaker-iwnL-

4 years ago, # ^ |

after 7 years still waiting

thequacker

4 months ago, # ^ |

after 10 years still waiting

techwiz911

9 years ago, # ^ |

The maximum number of prime divisors n can have is 6(as 2*3*5*7*11*13*17>10^5).

Assuming we use the Mathematical solution, following will be the complexity,

Let us pre-calculate prime factors of all numbers from 1....(10^5) using the Sieve of Erastosthenes(each number has a vector containing the primes that divide it). Complexity = O((nlogn)(loglogn))

Also we pre-calculate factorials and modular inverses uptil 10^5. Complexity= O(nlogn)

Then, for every query, we apply the principle of inclusion-exclusion for upto 6 primes. Complexity = O(t*2^6)

All other things like input etc. can be done in less than or equal to O(n).

So, total complexity = O(nlogn) + O(t*2^6) + O((nlogn)(loglogn)) = O(nlogn)

Do point out if I am wrong somewhere. :)

goovie

+15

I have extremly fast and easy solution to D, however I can't find the proof. Here it is:

Sort a increasingly, and b decreasingly. Now, we add to result values (b[i]-a[i]) from left to right while a[i] < b[i].

Here is link to my submission:

http://mirror.codeforces.com/contest/439/submission/6809214

+17

I used the same approach and here is the proof.
sort array a in increasing order and array b in decreasing order, now our target is to equate the first element of both the arrays. In order to achieve this a[0] can be incremented maximum up to a[1] and b[0] can be decremented up to b[1] (because if we increment a[0] to a value more than a[1] then a[1] also need to be incremented to that value). If this change in a[0] and b[0] results in a[0]>=b[0] then we are done else do the same thing for next elements until a[i]>=b[i]. so once we find such index i then all elements in a and b below i can be converted to a[i] and b[i] respectively. but instead we can convert elements to some value X such that b[i]<=X<=a[i].
so ans = (b[0]+...b[i-1]) -X*(i-1) + X*(i-1) -(a[0]+ ...a[i-1]) = (b[0]+...b[i-1])-(a[0]+ ...a[i-1]).

vinitkp

very nice explanation!!!

yash.15296

Yes. Fast and easy. that's why yours is mentioned in the editorial.

But, I think that condition should be while(a[i]<b[i]) instead of until.

yes, you are right.

PeterNaut

In problem E, do you need to use Fermat's little theorem?

v4_adi

In problem B i used unsigned long long for answer as answer was expected to overflow integer range but n and x is said to be within limit 10^5 then why I got wrong answer in test 12 on using them as int.

I submitted sol. in MvS 2010. Here http://msdn.microsoft.com/en-IN/library/s3f49ktz.aspx range given for integer is –2,147,483,648 to 2,147,483,647.

ItsLastDay

The problem is when you use int operands, the result of the operation (in your case it is "*") is also computed as int. Then, when it is evaluated, it is assigned to your long long variable, but the overflow already occured.

nicolas.pe.92

It seems that using the standard Arrays.sort in Java will give TLE in problem B... Of course, radix sorting could also be used. However, one would expect this sort to be enough, given the constraint on the array size. Also, it seems kind of unfair because the C++ sort seems to have no problem.

DieAnderen

Why don't you write your own sorting algorithm that guarantees logarithmic time.

JuanMata

or just use Collections.sort(), which uses merge-sort, therefore runs in $\text{[math]}$ .

marat.snowbear

You have big integers in Java, don't forget that it is unfair too :-)

OmaeWaMouShenDeiru

My code for problem C keeps giving WA !!

Any help please :/

mathlover

learn more while reading the editorial than taking part in the contest! Thanks for such perfect proofs~!

orchidmajumder

PraveenDhinwa,Can we say that the greedy approach of the second problem is actually an outcome of the rearrangement inequality??

I didn't understand you, The greedy approach can be proved by exchange argument(ie we will always get greater answer if we do the sorting as given in the problem statement), Try on any 2 elements arrays and generalize it.

Lewin

Yes, this is exactly what the rearrangement inequality states (http://en.wikipedia.org/wiki/Rearrangement_inequality)

← Rev. 4 →

Lewin,Thank you :) .. PraveenDhinwa,that's what I was trying to say that this exchange argument thing is basically same as rearrangement inequality(proof of which is also based on similar logic).nothing else.

And thanks for providing an awesome problem set like you have always done in the past :)

Yes, you are right, both the things are same.

I am glad that you liked the contest :)

code_overlord

439B - Деву-дурачок

Why does this solution (6815744) give TLE while this does not (6815855)?

plz refer to following comment

Why does this solution (6815744) give TLE while this does not (6815855?

Because in Java : default types like int arrays are sorted in N^2 time, while user-defined type eg Integer arrays are sorted in nlog(n) time.

callmekevin

the ternary search solution for problem D, the author made "it"(the variable name in the code) from 0 to 100 ,why it max value is 100, but not 200 or 50? i think the max value for it is the cubic root of 10^9. can you help me ?

it should be $\text{[math]}$ = 51.0 Try running your program for 49, 50, 51, 52 and check on which iteration it gets accepted :)

NomenEstOmen

Hi, praveen123. I had the same solution in problem 2 as yours, but in C, not C++. And it was wrong in 8. I used long long int for result. Isn't it enough? And what data type I must use for such problems in C? Thank you. P.S. I'm a newbie, so my question can be stupid :)

Here is the thing.

int a; int b;

long res = a * b;

if a is around 10^5 and b is also around 10^5. a * b will be overflowed and wont be 10^10.

Try running this and you will get the reason :)

sory.. get it :)

rudra101

One of the best tutorials, I have read on CodeForces. Thanks for the contest and the editorial !

CUDA

My worng answer information is: wrong output format Unexpected end of file — int32 expected Could anyone tell me what does this mean?

This means that you did not output anything when a 32-bit integer (normal integer) was expected. Eg : Correct answer : 2 2 Your answer : 2

Thanks!

Nash171

It is possible to solve this problem B using PHP? I got "Time limit exceeded on test 30". Still, Nobody solve it using PHP. :(

RodionGork

With bcadd I think you have no hope on success. It is quite slow.

Try instead summarize using general numbers. They wrap to double in PHP so if answer fit into 10^15 you will succeed.

UPD: No, does not work — too big numbers. However you can try splitting integer in two 32-bit parts :)

markmorcos

Could any body tell me why this greedy assumption would fail concerning problem D? http://mirror.codeforces.com/contest/439/submission/6821455

afrizal

Can someone tell me why this code got TLE?

Luqman

Every function solve is called, it run $\text{[math]}$ . Meanwhile it used recursively, so it will run again and again in $\text{[math]}$ .

Try iteration (non-recursive) style and got AC.

Boxer

Somebody have links for problems with mobius function ?

May be similar to problem E.

Thanks in advance.

real_father_of_goku

(E) part int modpow(int a, int b){ int ans = 1; while(b){ if(b & 1) ans = (ans * li(a)) % mod; a = (a * li(a)) % mod; b >>= 1; } return ans; } int rev(int v){ return modpow(v, mod — 2); } Why are we using (mod-2) ? thanks in advance

modpow(v, MOD — 2, MOD) is computing v^- 1 mod MOD, where MOD is prime.

inakolithsihsa

Why 1/v is equal to modpow(v, MOD — 2, MOD) ?

By Fermat's theorem a^p - 1 = 1 mod p.
Multiply both sides by a^- 1,
we get a^p - 2 = a^- 1 mod p

Why don't we divide by the factorial instead of calculating inverse and multiply ? int ans = (f[n] * 1LL / f[k]) % mod; ans = (ans * 1LL /f[n — k]) % mod;

Notice that answer must be mod by 1e9+7. Some factor may lost within this operation

islam-al-aarag

PraveenDhinwa I implemented the first solution Java and it does't get AC. I spent more than 1 hour optimizing it each time bumping me up by 5-10 test cases but now I TLE in case 53 and there is nothing else I can add.

P.S.: Similar C++ solution pass 6834876

Time limit is quite relaxed in the problem. So I think your time complexity is more than expected one. My C++ solution passes under .6 or .7 sec.

You are using two loops over factors, this might be the reason behind TLE, though I am not sure about that.

P.S. The code which you have attached is in Java, can you please the C++ one?

How can I loop less than twice??? I need to compute the dp for the factors themselves so I need to loop over their factors. I process them in order so the factors of the factors have their dp there already. Case 53 is just 98280 repeated 100k times. It's weird to have the max case that frequent. This http://mirror.codeforces.com/contest/439/submission/6814322 is the solution you refrences in the blog and it's just a recursive form of mine (which would be even slower on java). It passed in 2 sec so it's very hard for Java solutions to pass with this idea. I pushed the optimization as hard as I can. The only thing left is to cache the answers themselves (since I saw the case) but it doesn't feel right.

yes, you are right. You need to loop twice.

Regarding the time limit, it seems like your solution is quite close to time limit. Actually time limit was decided on the basis of mobius solution which will be faster than this. I am sorry but it looks like here you dont have any choice than shifting to mobius solution.

I see. I saw more comments (at least one) asking my same question. I think you should mention it in the editorial. Thanks for your quick responses :)

I have mentioned it in the editorial, thank you :)

Miras321

Ignore.

Well, as i can see from this solution, it's dp, Java and AC.

UPD. Submitted your solution with Java 8 — AC with 4 sec.

This is exactly what I mentioned in my comment. There is one more optimization which is to cache answers as they are (e.g. f(n,f)) which will only work in case you are repeating queries but this doesn't feel right and shouldn't be part of the solution. Long Key = (( Long ) N << 32 ) + F ; if ( cache . containsKey ( Key )) { return cache . Get ( Key ); }

What? Memoization shouldn't be a part of lazy dp? It's very common technique, must have as it is. (with your logic every code should pass, despite the effectiveness, lol) Secondly, your solution passed under Java 8. Try to use all compilers before blaming the authors about TL.

Can you please read the solution explained above?? The dp is not across cases, it's per case and this is what's explained in the tutorial. Yes the final solution pass on Java 8 but this is after spending nearly an hour of optimization (not doable in contest)

He did EXACTLY what's been said in the tutorial, and did it effectively. Tutorial is only a model solution, it's not like, do this, and this, write this code here. It's your job to make EFFECTIVE code, not just copy paste what's been said, and, afterwards, complaining about wrong verdict. It's like you never solved the problems with multitests, cashing the cases to not calculate them again is like obvious, how can it not feel right?

harshhx17

5 years ago, # ^ |

The reason behind the complexity being nlogn is that the sum of factors over all numbers from 1 to n is nlogn. However, if you refuse to memorize the answers across different queries, it can very easily be made to cross nlogn by using a number which has high number of factors.(although memorization won't help if we change f in every case) Hence, it is advisable to memorize the answers across the queries!

vanche

Hi! In problem E second query , isn't it possible partition [5,2] not [5,3] ?

nikesh04

7 years ago, # |

Can we use binary_search for the problem 439D — Devu and his Brother? My solution is going wrong when I apply binarysearch. Can you help me find a mistake in it. Link to my solution: Your text to link here... Thanks in advance.

rupav

5 years ago, # |

In problem D:

Proof of why optimal values(pivot value) will always lie on array elements, a[i] or b[j]: (here Optimal value is x such that all a's >= x and all b's <= x)

Let a and b be sorted in increasing order. Let us pick a[i] and b[j], such that a[i] < b[j] and there is no element of either arrays in between them. Let cost[z] defines the answer, with z being the optimal value.

Claim: min(cost[a[i]], cost[b[j]]) <= cost[p] for any a[i] < p < b[j].

Let count of array 'a' elements before i be $$${n_1 - 1}$$$, and count of array 'b' elements after j be $$${n2 - 1}$$$. Let $$${cd_1}$$$ be cost of converting smaller these $$${n_1 - 1}$$$ elements to a[i] and $$${cd_2}$$$ be cost of converting these larger $$${n2 - 1}$$$ elements to b[i].

Pick $$${p}$$$ such that $$${a[i] < p < b[j]}$$$. And let $$${x = p - a[i]}$$$, $$${d = b[i] - a[i]}$$$,

$$${=> b[i] - p = d - x}$$$

So,

Converting all a[q] to a[i] s.t $$${q < i}$$$, all b[q] to b[j] s.t. $$${q > j}$$$, and then push all $$${n_2}$$$ elements towards a[i], we will get cost[a[i]] i.e.:

$$${c_1 = cost[a[i]] = cd_1 + cd_2 + n_2d}$$$

Similarly the other way around pushing all to b[j],

$$${c_2 = cost[b[j]] = cd_2 + cd_1 + n_1d}$$$

By pushing elements to p, we get cost[x] i.e.

$$${c_3 = cost[x] = cd_1 + cd_2 + n_1x + n_2(d-x)}$$$

To compare, since all have $$${cd_1 + cd_2}$$$ common, eliminating them, i.e.

$$${c_1 = n_2d}$$$

$$${c_2 = n_1d}$$$

$$${c_3 = (n_1 - n_2)x + n_2d}$$$

Case 1: $$${n_1 = n_2}$$$

Then, $$${c_1 = c_2 = c_3}$$$.

$$${\therefore min(c_1, c_2) = c_3}$$$

Case 2: $$${n_1 > n_2}$$$

$$${c_1 = n_2d < c_2 = n_1d}$$$

$$${c_3 = +zx + n_2d = +zx + c_2}$$$, where z is a positive value = $$${n_1 - n_2}$$$

$$${=> c_3 > c_2 > c_1}$$$

$$${\therefore min(c_1, c_2) = c_1 < c_3}$$$

Case 3: $$${n_1 < n_2}$$$

$$${c_1 = n_2d > c_2 = n1_d}$$$

$$${c_3 = -zx + n_2d}$$$, where z is a positive val = $$${n_2 - n_1}$$$

$$${\therefore c_2, c_3 < c_1}$$$

now taking,

$$${c_3 - c_2 = n_2d - n_1d - zx = (n_2 - n_1)d - zx = zd - zx}$$$

$$${=> c_3 - c_2 = z(d - x)}$$$, but $$${d > x}$$$,

$$${(\therefore c_3 > c_2 => min(c_1, c_2) = c_2 < c_3)}$$$

hence proved.

Therefore, the optimal value will always lie on array elements.

PraveenDhinwa's blog