Hackfu - editorial

editorial
, , , , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Aleksa Plavsic
Tester: Hussain
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Median of a range, Greedy, Brute-force or Case-based 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

  •   Just observe that Final array would be sorted. Also, It would be of form $min \dots min$ $min+1 \dots min+1$ upto certain range and then last elements to satisfy sum constraint.

  •   Since median is independent of values left to median, we keep them as low as possible unless forced th increase them due to sum constraint.

  •   Either go for case based analysis or try a few positions around the middle of array and select lexiographically.

EXPLANATION

We will make few observations first, then solution would automatically develop.
(Note that wrong algo means algorithm given in problem statement. 0-based 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. :slight_smile: )

  • The final array, if exists, will always be sorted

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 non-decreasing order only.

  • Sum constraints can be handled greedily

Suppose there is no maximum constraint. Since we prefer sorted array only, we will try to add balance value after making first n-1 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 second-last element, then third-last and so-on.

  • Median after deletion of e elements depend only upon middle 5 elemenets of array before Deletion

For odd value of N, correct median is A[N/2]. Wrong median algorithm can only select can be A[N/2-1], 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/2-1], 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[x-1] 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[x-1] if we are not careful handling the sum constraint. we will never increase elementts before x position if if makes A[x] == A[x-1].

Impossible Cases: I don’t think you’ll need me for this, but if you do, here they are. :slight_smile:

Click to view
  • In case min == max, while array consisting of same element sand thus, impossible to hack the wrong solution.
  • If min*N > S or max*N < S.
  • Actually, we can find out stricter upper and lower bound. But that is left as an exercise for reader.

You asking for hint?? Here you go, It will cause A[x] == A[x-1] or cause the array to be unsorted.

Complexity:
Time complexity of above solution is O(N).

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 case-based 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
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like
2

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 :slight_smile:

2 Likes
3

Corrected. Glad you liked it. :slight_smile:

1 Like
4

“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.

5

Copied the setter’s solution, how unfortunate that it gives Wrong Answer!!
https://www.codechef.com/viewsolution/22087477
@taran_1407
@admin