Codeforces Round #641 (Div. 2) problem D(Orac and Medians): Visualization and approach to the solution

Revision en2, by reyad, 2020-05-28 16:28:15

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 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. (3) the elements can be represented as only two types v < k and v >= 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) _|
//
// or
//
//
// etc...other styles


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 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 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 one subarray that confirms two positive transitions, we would be able to fill the array. Example would 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 += ((b[i] >= k) ? 1 : 0);
if i >= 3:
np -= ((b[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. #### History

Revisions Rev. Lang. By When Δ Comment
en7 reyad 2020-05-28 22:01:17 21
en6 reyad 2020-05-28 21:57:19 126
en5 reyad 2020-05-28 16:46:43 12 (published)
en4 reyad 2020-05-28 16:41:51 85
en3 reyad 2020-05-28 16:35:02 55
en2 reyad 2020-05-28 16:28:15 215
en1 reyad 2020-05-28 16:18:40 2924 Initial revision (saved to drafts)