TOMGRDNR - Editorial

editorial
1

Problem Link:

https://www.codechef.com/GHC22019/problems/TOMGRDNR

Problem:

Given an array A of n numbers where 0<=A[i]<=9 for every valid i (for understanding's sake suppose 0<=i<=n-1). We need to find the smallest length x such that all possible subarrays of array A having length x have at least one common number. 

Prerequisite:

Arrays

Expected Complexity:

O(n*10)

Solution:

Mathematically, the problem says: 

find smallest number x such that 

{A[0], A[1], .., A[x-1]} \(\cap\) {A[1], A[2], .., A[x]} \(\cap\) ... \(\cap\) {A[n-x], A[n-x+1], .., A[n-1]} \(\neq\)  \(\phi\) (nothing)

Now, let us call S be the intersection set (which is \(\phi\)  above).

{A[0], A[1], .., A[x-1]} \(\cap\) {A[0], A[1], .., A[x-1]}  \(\cap\) {A[0], A[1], .., A[x-1]}  \(\cap\) ... \(\cap\) {A[n-x], A[n-x+1], .., A[n-1]} \(=\) S

Then, S can contains multiple numbers.So, we also need to find the smallest number in x.

Suppose that smallest number is p.

Traverse the array to find the positions of all p. Suppose p occurs as follows:

X p p X X p X p X X X
0 1 2 3 4 5 6 7 8 9 10

p occurs at 1,2,5,7. From the positions we can see that between 5 and 7 the gap is maximum. So, a p always occurs in a subarray of length 3 (7-5+1=3. a subarray of length 3). But we are ignoring the gap at the beginning and at the end. The first p occurs at index 1 but the last p occurs at index 7. So, the gap is maximum towards the end which is 10-7+1=4. So, we can say that a p always occurs in a subarray of length 4 in this case. Now, we can generalise it and solve for all p between 0 and 9 to get the answer.

Here in the solution, we store positions of p in v[p]. If v[p] is empty, then there p can't be that common flower. So, we search for another p. mx[p] will store the maximum subarray size for a particular p such that every subarray of size mx[p] contains a flower of type p. Finally we find minimum of all mx[p] and get the answer.

int n;
cin >> n;
int a[n];
vector<int> v[10];
for (int i = 0; i < n; i++) {
    cin >> a[i];
    v[a[i]].push_back(i);
}
int mx[10], res_len = n + 10, res_num = -1;
for (int i = 0; i < 10; i++) {
    if (v[i].empty())
        continue;
    mx[i] = max(v[i].front() + 1, n - v[i].back());
    for (int j = 1; j < v[i].size(); j++) {
        mx[i] = max(mx[i], v[i][j] - v[i][j - 1]);
    }
    if (mx[i] < res_len) {
        res_len = mx[i];
        res_num = i;
    }
}
cout << res_len << " " << res_num;

Solution Link:

Author's : https://www.codechef.com/viewsolution/24044636