PROBLEM LINK:Setter: Aleksa Plavsic DIFFICULTY:Easy PREREQUISITES:Median of a range, Greedy, Bruteforce or Casebased analysis, Constructive Algorithms PROBLEM:Given Number of elements $N$, Sum of elements $S$, a position $K$, minimum value $m$ and maximum value $M$, Construct an array $A$ which proves the median algorithm mentioned in problem wrong, following these constraints, or tell if it is impossible to make. SUPER QUICK EXPLANATION
EXPLANATIONWe will make few observations first, then solution would automatically develop. (Note that wrong algo means algorithm given in problem statement. 0based indexing has been used throughout the editorial. Also, unless i mention the constraints, I am giving ideas ignoring min, max or sum constraint, so as to convey the idea first. These will be surely taken care of. :) )
On line 3 in wrong algorithm, algorithm sorts the array, and then deletes elements. This means that no matter what permutation of array we select, all permutations will give same results. for choosing lexicographically smallest array, it is ideal strategy to choose perumtation sorted in nondecreasing order only.
Suppose there is no maximum constraint. Since we prefer sorted array only, we will try to add balance value after making first n1 values, to last element as this would give lexicographically smallest array. Now, if there is maximum constraint, we follow the same strategy, we first increase he last element till it can be increased without violating maximum constraint, then secondlast element, then thirdlast and soon.
For odd value of $N$, correct median is $A[N/2]$. Wrong median algorithm can only select can be $A[N/21]$, $A[N/2]$ or $A[N/2+1]$ , depending upon the position of values deleted. For even value of $N$, correct median is mean of $A[N/2  1]$ and $A[N/2]$. Incorrect algorithm will choose either out of $A[N/21]$, $A[N/2]$ or $A[N/2+1]$ as median. For both cases, we can see that varying these elements even by 1 will cause Wrong median algorithm to give Wrong answer. So, we just need a position $x$ such that $A[i] = min \forall 0 \leq i < x$ and $A[i] = 1+min \forall x \leq i < N$ so that it gives Wrong answer. We also know that value lies around the middle element. So, we can check a few positions of middle each side (checking two values around middle both sides and middle position would do the trick.)4 So, what does our final solution looks like?? We make a function taking input pos x, which generates an array following min, max and sum constraint, and $A[x] \neq A[x1]$ or tells if it is impossible to to do. Then make a check function which tells us if this array is a counter case for wrong algorithm or not. Choose the lexicographically smallest array out of valid arrays. But ACs in Cook off problems aren't that easy, that too without an edge case. The edge case is not in problem, but in our solution. the function building the array might return an array with $A[x] == A[x1]$ if we are not careful handling the sum constraint. we will never increase elementts before x position if if makes $A[x] == A[x1]$. Impossible Cases: I don't think you'll need me for this, but if you do, here they are. :) Complexity: Editorialist's note In this particular problem, we were able to make valid function in same time complexity as that of building an array. But more commonly there will be constructive problems, especially challenge problems, where valid function have very high time complexity. In those cases, we have to rely only on casebased analysis or some probabilistic checker. But that is a different story, much away from this editorial. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 19 Aug '18, 22:30

"we just need a position x such that A[i]=min∀0≤i<x and A[i]=1+min∀x≤i<N so that it gives Wrong answer." can anyone explain this please ? thanks. answered 23 Aug '18, 15:33

Copied the setter's solution, how unfortunate that it gives Wrong Answer!! https://www.codechef.com/viewsolution/22087477 @taran_1407 @admin answered 26 Dec '18, 01:28

Nice editorial. one silly thing : "We make a function taking input pos" here you mention 'pos' but in notation u have used 'x', please fix it.
Thanks again for this :)
Corrected. Glad you liked it. :)