reyad's blog

By reyad, history, 5 months ago, In English

To solve this problem first we need to do some observations:
let's denote
l_k = no. of elements less than k,
g_k = no. of elements greater than k,
e_k = no. of elements equal to k.

(1) let us first state, "when there is no solution for this problem":
if l_k >= e_k + g_k for all possible subarray where each subarray length is greater than 1, then its not possible to have a solution for this problem, cause k would never be able to be the median of the subarray.

(2) if we can't construct a solution for any of the subarrays of length w, then there would be no solution of any subarray of length w+1. And if there is a solution for w(where w > 1), then it is also possible to construct a solution for w+1 no matter what the consecutive elements are. [note: this is the most important observation]

(3) the elements can be represented as only two types a[i] < k and a[i] >= k. So, if we turn them into +(positive transition) and -(negative transition) operation then, there would be only two types of transitions. And we can easily represent them in diagrams like below:

//         _   _   _
// (i)   _| |_| |_| |_...
//
// or
//
// (ii)  _          
//        |_       _
//          |_   _| |_...
//            |_|
//
// or
//               _
//             _| |_
//           _|     |_...
//         _|
// (iii) _|
//
// etc...

The graph shows us one thing clearly, "when it is possible to make e_k + g_k > l_k":
e_k + g_k > l_k is possible if the graph contains any of the following segment for once:

//        _   _
// (i)   | |_| | : +, -, +
//
//           _
//         _|
// (ii)  _|     : +, +, any type of transitions
//
//
//            _
// (iii)    _|   : -, + , +
//       |_|
//

In summary it shows that if there are at least two positive transitions between three consecutive transitions, then it is possible to fill the array with k if there is at least one k present in the array.

(4) Let's denote positive transitions as +1 and negative transitions as 0, then in each subarray of size 3 if there is at least one subarray that confirms two positive transitions(considering k is present at least once in the array), we would be able to fill the array. Example of such subarray(for transitions) would be like: (1, 0, 1) or (1, 1, 0) or (0, 1, 1) or (1, 1, 1) etc...

Solution:

let flag = false, seenK = false;
let np = 0; // counts no. of positive transitions in subarray size of 3
for i = 0...n-1:
  seenK |= (a[i] == k) // check if we've been seen k at least once in the array
  np += ((a[i] >= k) ? 1 : 0);
  if i >= 3:
    np -= ((a[i-3] >= k) ? 1 : 0);
  if np >= 2:
    flag = true;
if seenK and (flag || (n == 1 && np == 1)/*check for exceptional case when n == 1*/):
  print "yes"
else:
  print "no"

The solution link is given here.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey thanks for making such a great editorial. Can you also mention how to prove the second point?(If there is a solution for length l, there is a solution for length l+1).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider the subarray {3, 1, 4, 4}. It has no immediate solution for length $$$2$$$, but does for length $$$3$$$. Once you make the changes for this, you can proceed to get valid subarrays of length $$$4, 5, 6, ...$$$ At least that's what I think he meant to say.

  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    let's say there's a solution for subarray of length l(l > 1).
    let's consider this subarray of length l as a[i...j](where, j-i+1 = l)
    now, if a[i...j] have a solution, then we can change all the elements of a[i..j] to k
    i.e. a[i] = a[i+1] = a[i+2] = .... = a[j] = k

    now, consider all the possible values for a[i-1] and a[j+1]
    there's four possibilities where a[i-1] and a[j+1] none of them are k(let's say i-1>=1 and j+1<=n, n means length of a):
    (i) a[i-1....j+1] = [k+x, k, k, ...., k+y] (where, x > 0 && y > 0)
    (ii) a[i-1....j+1] = [k-x, k, k, ...., k-y] (where, x > 0 && y > 0)
    (iii) a[i-1....j+1] = [k+x, k, k, ...., k-y] (where, x > 0 && y > 0)
    (iv) a[i-1....j+1] = [k-x, k, k, ...., k+y] (where, x > 0 && y > 0)

    I hope you get the scenario.

    Part-01: for a[i....j+1]
    Now, let's consider the subarray a[i....j+1], can you construct a solution? (remember l>1)
    let's try to find the median, which is (((j+1)-(i)+1) / 2) = (h / 2) th element [note: j-i+1 = l, and so, h = l + 1]
    for h == 3(a[i, j, j+1]), median would be 2nd element, which is k(whatever, a[j+1] holds, cause, after sort the possible sequence would be (k, k, k+x) or (k-x, k, k) and 2nd element would always be k)
    for h == 4(a[i, j-1, j, j+1]), median would be 2nd element, which is k(whatever a[j+1] holds)
    ...
    ...
    so on...
    so no matter what a[j+1] holds the median always would be some index which holds k

    Part-02: for a[i-1...j]
    You can just apply the rules as I have done in part-01 and prove it yourself.

    I hope this helps you.