ZCO - STRIMPOR (Unofficial) Editorial

THIS EDITORIAL IS AN UNOFFICIAL ONE AND THE REASONING BEHIND THE LOGIC MAY DIFFER FROM THE OFFICIAL ONE.

PROBLEM LINK:

Contest

DIFFICULTY:

Easy

PREREQUISITES:

Sliding Window Algorithm

PROBLEM:

The problem statement is clear and short. It can’t be more shorter.

QUICK EXPLANATION:

Calculate all the points from where a Good substring starts, and all the points where the Good substring ends. Now, run a window of length K through the whole array. This is done to minimize the time complexity from O(N * N) to only O(N), thus solving it for 100 points.

EXPLANATION:

Please go step by step, as the points are inter-related.

AC (10pts)

Let us first define a Brute Force approach to the problem.

So, we will keep an array which will help us in calculating the minimum Importance of a substring of length K.

Definition of arr(i)

arr[i] = the number of Good substrings the ith index overlaps with.

So what are we going to do will be increasing the length by 3 every time, and iterate through the whole array. We check the following,

  1. a[start_pos] == X
  2. a[end_pos] == Z.

If both are true, now we will update our arr[] array which will take O(len) time.

Solution Snippet
for(int len = 3; len <= n; len += 3) { //the length of the Good substring
     for(int i = 1; i <= n - len; i++) { //1 indexing
          int j = i + len;
          if(a[i] == 'X' && a[j] == 'Z') //checking the conditions
          {
               for(int k = i; k <= j; k++) { 
                       arr[k]++; //incrementing the value of arr[i], arr[i + 1] ... arr[j]
               }
          }
     }
}

So we are increasing the length of the Good substring - O(N)
Within that, we are iterating through the array - O(N)
Within that we are updating our arr[] array - O(N)

So, The Time Complexity of this Approach is (O(N * N * N ) )
This will AC only on the first sub-task. :frowning:
This motivates us to make this code efficient.

AC (25pts)

In the brute force solution, when we are traversing for each i and j, and checking whether the condition holds true, can’t we update the values after the traversing is over? This will make this code quite efficient. But how?

Answer to this question

We can just easily store i and j in a vector of pairs. Then, we can traverse it after the loops end.

Solution Snippet
vector<pair<int, int> >pos; //The pair is start_pos, end_pos of each Good substring
for(int len = 3; len <= n; len += 3) { // The length of the Good substring
    for(int i = 1; i <= n - len; i++) { // 1 indexing
        int j = i + len;
        if(a[i] == 'X' && a[j] == 'Z') { // checking the conditions
            pos.push_back(make_pair(i, j)); //making the pair
        }
    }
}
for(int i = 0; i < pos.size(); i++) { // iterating through the pos array
    for(int j = pos[i].first;  j <= pos[i].second; j++) { // updating arr[]
        arr[j]++;
    }
}

Nicely done. We just have to optimize our code a bit further, and it will be 100pts. :slight_smile:

AC (100pts)

Have you thought, do we ever have to care about the exact length of the substring.

Answer

No. We are just given that it has to be a multiple of 3. Now it can be 3, 6, 9 and so on and so forth. The only condition over here is that the length has to be a multiple of 3.

So we can easily compute the starting position and ending position of substrings without even caring about its length.

Basic idea to calculate the starting positions

The ending positions are Z. So we traverse from the back (coz we have to find the starting positions, which can only be counted from the back in the problem). Suppose we encounter a Z at index i. So we increase the count of the number of Z’s in the (i % 3) position.

Why at (i % 3), and not i

Because we do not care about the length. Why not all the Z’s who have the same remainder when divided with 3, be kept in a single position.

Now, here is the tricky part. If you find an X in the index i, where (i % 3) = 0, then we do not do operations with the count of Z’s in position 0. Try counting it yourself.

Then on which position should we do the operation

The answer is, we should do the operation on ((i - 1) % 3), if i is not negative. Else we will do it on the 2nd position.
Lets see it ourselves:

1. cnt = 1; index = i, //cnt is the number of characters in the 'Good' string
2. cnt = 2; index = i + 1.
3. cnt = 3; index = i + 2.

Thus, we saw that the operations part is a bit tricky.

Now in the same way, calculate the ending position. Be careful of the tricky part.
We store the starting and ending positions in arrays, where start[i] is the number of good substrings that start from index i, and vice-versa for end[i].

Now, calculate the Minimum Importance of all the substrings, using Sliding Window.

Technique of using it

So, whenever we move one ahead, we subtract the number of ending positions at (i - k) where i is the last index of the array, in the window. We alse add the number of starting positions at i. Answer will be the minimum of all.

Solution Snippet
long long ans = 0;
for(long long i = 1; i <= k; i++) { // 1 indexing
    ans += start[i]; //the number of substrings starting at i
}
for(long long i = k + 1; i <= n; i++) { // sliding window technique applied
    ans = min(ans, ans - end[i - k] + start[i]); // we select the minimum of the two
}
cout << ans << endl;

TIME COMPLEXITY:

O(N) per each test case

SOLUTIONS:

My solution.

Any comments on how to improve this editorial is openly welcomed!

1 Like

I have a small doubt about 10pts and 25pts. In both of these what will be our output?
Also, in 25pts u just moved the third loop outside the other two, but I think it shouldn’t have any effect. Because we are still going to run it that many times only. Nice editorial btw.

Edit: Thanks for the editorial, I understand it now. I submitted my solution, but I am getting RE(SIGABRT) in 15pts. Here is my solution -> https://www.codechef.com/viewsolution/27988896

In both of these what will be our output?

The output will be:

min(max(arr[i], arr[i + 1], ..., arr[i + k - 1]))

It is applicable for all i from 1 to (n - k) ---- (1 indexing)

Also, in 25pts u just moved the third loop outside the other two, but I think it shouldn’t have any effect. Because we are still going to run it that many times only.

No, the time complexity gets affected. Yes, I agree the difference between the two sub-tasks is pure observation and that is the reason you will find very few (maybe 1 or 2) who have done it for 10 points, and haven’t done it for 25.