reyad's blog

By reyad, history, 2 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.

Read more »

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

By reyad, history, 2 months ago, In English,

The problem requires us to find gcd({lcm({a_i, a_j}) | i < j}).

Now, for each a_i we can take a_j(where i < j) to make a pair.
So the pairs would be like: (a_i, a_i+1), (a_i, a_i+2), (a_i, a_i+3), ..., (a_i, a_i+k) // let's assume, i+k = n
and we've to find lcm of those pairs
and then gcd of those lcms. [note: we've to do this for each of a_i]

Now, let's try write the formula using gcd and lcm and in a more readable format:

gcd(lcm(u, v_1), lcm(u, v_2), lcm(u, v_3), ..., lcm(u, v_k))....(formula-01) [note: u replaces a_i, v_x replaces a_i+x]

let's say, the result of the formula-01 is d i.e. d | {lcm(u, v_x) | 1 <= x <= k}

let's write, d = (p_1 ^ r_1) * (p_2 ^ r_2) * .... * (p_h ^ r_h)

According to definition
(i) for lcm: we take the max power of prime divisors between the two elements
(ii) for gcd: we take the min power of prime divisors between the two elements

let's assume, d = du * dv (so, du and dv both must be found in each and every lcm pairs)
now, say, du contains the primes those are contributed from u(note: u is common in each pair)
dv contains the primes those are not contributed from u, so dv must be found as a divisor in each of v_x(where 1 <= x <= k) or we may say dv | {v_x | 1 <= x <= k)}.

So, it can be said that,
gcd(lcm(u, v_1), lcm(u, v_2), lcm(u, v_3), .., lcm(u, v_k)) = lcm(u, gcd(v_1, v_2, v_3, ..., v_k))...(formula-02)

by using formula(02) we can easily find lcm of each pairs of that contains a_i, and then take gcd of those lcms:

Solution:

let, g[0....n-1] where g[i] denotes gcd(a[i], a[i+1], ..., a[n-1])
let, ans = 0
for i = 0...n-1:
  ans = gcd(ans, lcm(a[i], g[i+1]))
print ans

The solution link is given here.

Read more »

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

By reyad, history, 5 months ago, In English,

A O(V * N) solution is also possible for Array Shrinking.

The idea of this solution is building segments of value V+1 from V. Let's have a sequence i...j of value V and j+1...h is another sequence of value V, then value of sequence i...h would be V+1.

Let's consider e[v][i] = j, then we can do as follows:

j = e[v][i]
h = e[v][j+1]
if j != -1 and h != -1:
    e[v+1][i] = h

This process can be used to find all the possible shrinking sequences. Then the start and end index of the sequences can be used to find the possible minimum length.

Here's the Solution.

Read more »

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