ACM14KG1 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sort, Two Pointers Scan

PROBLEM:

There are N shops in a line and each of them has some different types of items (M types in total). For any i (1<=i<=N), find out the best interval [j, k] (j<=i<=k) such that there are all M types of items available in these shops and k-j is minimized. If there are several ties, take the smallest j.

EXPLANATION:

Minimal Intervals

Let define the minimal intervals are those intervals [j, k] such that there are all M types of items available in these shops but this condition will not be held for either [j + 1, k] and [j, k - 1].

Clearly, there are at most N different minimal intervals, because the left sides of different minimal intervals should be different.

Let right[i] be the right side of the minimal interval starting from i. It is worth noting that there might be impossible to have valid right[i] for some i because of there are not enough types in the tail of shops. In this case, we can set right[i] to INF, which is a very large number.

To compute all right[i], we can simply pass all shops once as following:

j = 1
For i = 1 to N
While (j < N) and ([i, j] does not have enough types):
        j += 1
    if j < N:
        right[i] = j
    else:
        right[i] = INF

Original Question

For a given i, there might be several minimal intervals containing it. For a specific minimal interval [j, k], it could be a possible solutions for the i inside it.

Therefore, we can maintain a data structure, which contains all feasible minimal intervals for current i, sorted by the length of intervals and its left side. By increasing i to i + 1, some intervals starting from i + 1 should be inserted while those intervals ended at i should be removed. Considering these types of operations, the balanced binary search tree is able to do it efficiently. In C++, you can refer to set, where Interval should be user defined struct/class with the special < operator.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

Author’s solution can be found here.
Tester’s solution can be found here.