CHEFCK - Editorial

PROBLEM LINK:

Practice
Contest

Author: Abhra Dasgupta
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Range Minimum Query, Sliding Range Minimum Query

PROBLEM:

Given an array A of size N, and an integer K, handle the queries of the form: find the minimum element of the subarray A[L, R], where length of the subarray lies between K and 2K.

QUICK EXPLANATION:

Any interval which has length between K and 2K, can be represented as a union of two K-length intervals. Hence, the minimum of any subarray of length n \in [K, 2K] can be computed by taking the minimum of two K length subarrays. Hence, the task reduces to precomputing the minimum of all K length subarrays, which can be done in linear time using sliding range minimum query method.
.

EXPLANATION:

We are given an array A, and we need to handle several queries, each of which asks the minimum of some subarray A. Also, we are given an integer K, and it is guaranteed that all the subarrays in the queries have length between K and 2K.

If we were not given the special constraint about the size of queried subarrays, then this problem would be a standard range minimum query problem, which can be solved using O (N \log N) preprocessing time and O (1) query time as described here. In fact, this approach will suffice to solve the smaller subtasks (and probably the large one as well, if well optimized). However, here we describe an approach, which uses this constraint, and requires O (N) preprocessing time, while still answering queries in O (1) time.

Reduction into Fixed-Length Subarray:

Any interval [x, y] of length between K and 2K can be written as a union of two K length interval.
[x, y] = [x, x + K] \cup [y - K, y].

Similarly, a subarray A[L, R], can be seen as the union of two (possibly overlapping) subarrays A[L, L + K - 1] and A[R - K + 1, R]. Since, the length of the original subarray is at least K, none of the two subarrays cover any element outside the original subarray. On the other hand, the length of the original subarray is no longer than 2K (i.e., R - L + 1 \leq 2K), hence the two subarrays must cover each element of the original subarray (i.e., (R - k + 1) \leq (L + K) ).

Based on this we can write
\min (A[L, R]) = \min (\min(A[L, L + K - 1]), \min(A[R - K + 1, R]))

In other words, we have reduced the problem of computing the minimum of A[L, R] into computing the minimum of two K-length subarrays. There are exactly (N - K + 1) subarrays of length K, so we can precompute the minimum of all such subarrays and store them to handle the general queries in O (1) time. In the next section we show that this pre-computation can be done in O (N) time.

Computing Minimum of All K-Length Subarrays:

There are two possible ways to compute the minimum of all K-length subarrays.

First Method:

In this method, we partition the original array into blocks of size K, i.e., A[0, K - 1], A[K, 2K - 1], \cdots. For each block we compute the minimum of each prefix and suffix of that block. In other words, for the block A[nK, (n + 1)K - 1], we compute the minimum of following subarrays:

Prefix:
A[nK, nK]
A[nK, nK + 1]
A[nK, nK + 2]
\cdots
A[nK, (n + 1)K - 1]

Suffix:
A[(n + 1)K - 1, (n + 1)K - 1]
A[(n + 1)K - 2, (n + 1)K - 1]
A[(n + 1)K - 3, (n + 1)K - 1]
\cdots
A[nK, (n + 1)K - 1]

For each block we are computing 2K values, and they can be computed in O (K). Hence, the overall time complexity is O (N).

Now let us see how to compute the minimum of subarray A[x, x + K - 1] using these values. If x is a multiple of K, then this subarray is the same as one of the blocks, so we already have this value. If x is not a multiple of K, then y = \lfloor (x / K) \rfloor-th block will contain the endpoint x, and (y + 1)-th block will contain the endpoint (x + K - 1). Hence, we can take the appropriate suffix of y-th block and prefix of (y + 1)-th block and compute their minimum to compute the minimum of subarray A[x, x + K - 1]. More formally,

\min (A[x, x + K - 1]) = \min(\min(A[x, (y + 1)K - 1]), \min(A[(y + 1)K, x + K - 1])).

Hence, we can compute the minimum of all K length subarrays in O (N) time.

Second Method:

This approach is slightly faster than the previous method, as it requires only a single scan of the array. This method is explained here in detail. We describe this method only briefly. We use a window of size K, and slide it from left to right so that it covers all K-length subarrays of A. Initially, the window corresponds to the subarray A[0, K - 1], when we slide it one step to the right it corresponds to the subarray A[1, K]. This sliding corresponds to adding A[K] into the window, and removing A[0] from the window.

The basic idea is that we maintain a list P, which consist of potential minimum element of the current and future windows. Whenever, we add an element A[x] into the window, we discard all elements of the list which are larger than A[x], this is because these elements can never be the minimum element of any future window, as any future window containing these elements will also contain A[x], which is strictly smaller than these elements. This means element of P will be in non-decreasing order. When we remove an element from the window, we check if the removed element is the same as the first element of list P, if so, we have to discard it, as this element no longer belongs to the window. The first element of the list is the minimum element of the current window. The following snippet contains the pseudocode for this method.

// B[i] will contain the minimum of subarray A[i, i + K - 1]
B[1..N] = {INF}; 

// deque, which will contain the potential candidate for minimum elements
// of current and future windows.
P = {};

for (int i = 0; i < N; ++i) {
  // Discard elements of the list larger than current element.
  while (!P.empty() && P.back() > A[i])
    P.pop_back();

  // Add the new element.
  P.push_back(A[i]);

  // Remove the first element of the window,
  // and from the list P as well, if it belongs there.
  if (i >= K && A[i - K] == P.front()) {
    P.pop_front();
  }

  // Set the minimum of the window
  if (i >= (K - 1)) {
    B[i - K + 1] = P.front();
  }
}

Since each element can be added into the list P at most once, and removed at most once, the complexity of this algorithm remains O (N)

Time Complexity:

O (N + Q)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

8 Likes

please check my solution http://www.codechef.com/viewsolution/6977118
I’ve tried a lot…but i found no mistake in it.

@arpit165 The generator code implemented by you seems slightly incorrect. I think instead of
“if(a2[x+1] <=r)” you must use “if(a2[x] <=r)”

@abhra73 thanks…:slight_smile:

Hi, i am stuck at a little awkward problem in this problem, i, after frustration, decided to brute force the problem, and to my surprise i found that whenever i used an array of 1-based indexing my solution were showing Accepted result, but the same code for 0 based indexing isn’t working(but why?), i am still surprised where the problem is please look at the solution, it is in python so it wouldn’t take too long to understand what i did there :slight_smile:
1 Based Indexing http://www.codechef.com/viewsolution/6960249
0 Based indexing http://www.codechef.com/viewsolution/6960258

@lwmarsh06 The generator defined is for generating a 1-based indexed array. Since the index is part of the generator, if you want to generate the same array with 0-based indexing, you were required to modify the generator accordingly which you didn’t.

@abhra73 The arrays coming out are almost the same(just in 1 indexing the 0th element is irrelevant),
i tried some test cases, some of my own too, and i found the arrays coming out to be the same, i shifted the variable x from 2 to 1 and x<=n to x<n. Can you please point out the correction and by any chance a test case for which my 0 indexing solution is failing so that i can figure out the difficulty.
I am getting identical answers for both solution on the test cases which i can think of :slight_smile:

How much efficient is the sparse table algorithm … can it be used for this case ?

I solved the problem during the contest but TLE in the third subtask,Solution which part of the solution need improvement? can someone help me with that?

Yes. Sparse Table Algorithm will give you 100 points, but after so many optimizations & that too will bring the runtime just inside the specified limits…
Here’s my solution if you want some reference: http://www.codechef.com/viewsolution/6916718

Title spelling wrong :slight_smile:

@Sabari You can optimise your solution by using just using the following things::

  1. While generating the array A[] don’t use power() function. since every time t is taken to the power of x which is also equal to the iteration of loop, so simply make a variable and in every iteration of loop multiply it by t.
  2. Use % (modulo) only if a number becomes greater or equal to modulo … ie. if(A[x] >= m ) then take modulo.
    Rest is all fine…I was also doing same mistake…and i’ve done about 60 submissions
    For referance you can see my submission here link text
    link text

@madhur123Thanks a lot!!! cleared all sub-tasks. I never knew load posed by mod operation.

I am applying second method still getting TLE for one test case out of 6 solution link http://ideone.com/rkAgT2 please help

I used Sparse Table Algorithm and i am not getting why it gives SIGSEGV for subtask 3 (after running for 2 secs). Please help and guide me. Here is my solution : http://www.codechef.com/viewsolution/6955887

I used Sparse Table Algorithm and i am not getting why it gives SIGSEGV for subtask 3 (after running for 2 secs). Please help and guide me. Here is my solution : http://www.codechef.com/viewsolution/6955887

I used Sparse Table to solve this problem. Can someone please tell me why I am getting TLE in last test case of third subtask.Here is my solution : http://www.codechef.com/viewsolution/6973627

I am applying second method still getting TLE for one test case out of 6 solution link http://ideone.com/rkAgT2 please help

http://www.codechef.com/viewsolution/6980436
could you explain, why isn’t my solution right?

@nil96 remove modulo while you are generating array use only once when number exceeds m.i was doing same mistake after 4 days i got this…:stuck_out_tongue: