STRQ - editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Pushkar Mishra
Editorialist: Florin Chirica

PROBLEM

You’re given a string containing only letters c h e and f. You have to answer queries asking how many words start in a given letter and end in other letter (necessarily different by first one) considering only positions from the string between two given numbers.

QUICK EXPLANATION

Let’s calculate ways[A][i] = in how many ways can we choose a word with beginning letter A, ending letter B and its ending position up to i. Also, let cnt[A][i] = how many letters A appear in the first i characters. This information is enough to answer queries in O(1): for two characters A and B and two positions i and j, the answer is ways[A][j] - ways[A]**[i - 1] - cntA * cntB, where cntA = number of characters equal to A from [1…i - 1] and cntB = number of characters equal to B from [i…j].

EXPLANATION

Number of letters is small

A first thing we should observe is the number of letters available is 4 (c h e and f). This low number of letters will help us to solve the problem with a simple and efficient solution.

The idea with having 4 letters is that we can precalculate something, then we can answer all queries in constant time.

Let’s inspect how queries can look like. We start by looking how beginning and ending of a good substring can look like. There are only 12 possibilities.

  • (start) c (end) h
  • (start) c (end) e
  • (start) c (end) f
  • (start) h (end) c
  • (start) h (end) e
  • (start) h (end) f
  • (start) e (end) c
  • (start) e (end) h
  • (start) e (end) f
  • (start) f (end) c
  • (start) f (end) h
  • (start) f (end) e

Since there are only 12 possibilities, we can iterate over them and store something for each configuration. For a configuration, what we computed should be enough to solve all queries that correspond to that configuration.

For a fixed start and end letter

By now we can assume that our start and end letters are fixed (using the iteration). Let’s denote by A the start letter and by B the end letter.

What we need to do is to answer queries: for a subarray [i…j], how many indices i’, j’ exist, such as array[i’] = A and array[j’] = B, with i <= i’ <= j’ <= j.

The trick here is to solve an easier problem firstly: suppose we only had to count pairs (i’, j’) such as i’ <= j’ <= j (we erased i condition). Now the task can be solved by a simple precalculation.

Let ways[A]**[i] = number of ways to choose i’ <= j’ <= i such as array[i’] = A and array[j’] = B. We have two choices for j’.

Choice #1: Let j’ < i. All pairs (i’, j’) such as j’ < i are already calculated in ways[A]**[i - 1], so we can simply add this number and treat all case.
Choice #2: Let j’ = i. Obviously, for this to happen we’re forced to have array[i] = B. What’s left is to find positions i’ such as array[i’] = A and i’ < i. This is easily done by keeping a partial sum for each letter, something like sum[let][i] = how many times does letter let appear in positions [1…i].

Hence, the answer is in ways[A]**[j].

Now let’s consider full restrictions. In reality we have i <= i’ <= j’ <= j. Let’s see what elements are counted above, but should not be counted.

There are two cases

Case #1: i’ < j’ < i <= j

Case #2: i’ < i < j’ <= j

We have to erase from our result the results for those cases.

Case #1 is simple to calculate, as its answer is simply ways[A]**[i - 1].

Case #2 basically asks us to find a letter A in range [1…i - 1] and a letter B in range [i…j]. Let cntA the number of letters A in range [1…i-1] and cntB the number of letters B in range [i…j]. The answer is simply cntA * cntB. The values of cntA and cntB can be calculated by partial sums.

Time Complexity

The computation of ways takes O(n) time (with constant 12). Also, partial sums also take O(n) time. Then, a query is answered in O(1) as stated above.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

Setter’s solution

3 Likes

my solution gives SIGSEGV for the last sub-task .Please help me in understanding what the problem is.
http://www.codechef.com/viewsolution/6279777

What would the approach to solve the given problem had the number of characters be 26?

Hey pulkit the problem with your code was that you were initializing the large array of the order of 10^6 inside the main(which is a stack memory) , you should have done it outside the main(in heap memory) this resulted in SIGSEV . Also there was an overflow error which I corrected. Your AC solution
http://www.codechef.com/viewsolution/6297220 .

1 Like

Will you please elaborate?. If you mean as in this case we have only chef what if we have all 26 characters? than also I think we will move in the same direction. there will be 26*25 array.

Ya but in that case, the amount of memory usage will increase to 262510^6, which I think might give RE (SIGSEGV). Correct me if I am wrong. I just want to know is there a method which is more memory efficient with the similiar time complexity

1 Like

thanks a ton johri21.:slight_smile:

I tried to use segment tree approach but got TLE :confused:

http://www.codechef.com/viewsolution/6204146
why my this solution was giving WA in contest ?? :frowning:
i checked it for nearly 400 test cases :frowning:

Some one please tell me what’s wrong with my approach.

I took a 2d array and stored the location ( indices ) of each character in the string. Then i took the input of queries and made a binary search and found out the least index at which the character is present in the given range. Then i counted the no. of possibilities. First subtask is accepted but the second and third are resulting in a TLE. Someone please help me in my approach.

http://www.codechef.com/viewsolution/6261829

Thanks in advance

Simply because it’s too much to do for every query. Every query needs to be answered in O(1).

Hello frendz ,

Hope you like this problem.

May be some of you are annoyed due to the strict time limit for this problem but it was intentionally set to forbid the solutions based on data structures or any other slower solutions.

Here is link to my solution for this problem link

4 Likes

my solution gives SIGSEGV for the last sub-task .Please help me in understanding what the problem is.
http://www.codechef.com/viewsolution/6306768

@shivama7 i haven’t read your solution completely but i guess the problem is that you have declared array c (size ~10^6) in main, make it global n check.

@johri21 my


[1] is giving TLE for the last subtask, can you advice me on how to optimize it


  [1]: http://www.codechef.com/viewsolution/6307244

Hey, I got AC in the first 2 subtasks and tle in the 3rd.

(here’s the link : http://www.codechef.com/viewsolution/6307251 )

Then I switched to scanf instead of cin and ended up getting SIGSEGV for all 3 sub tasks.

(here’s the link for the modified code : http://www.codechef.com/viewsolution/6307266 )

Been at it since long now. Any help would be appreciated.

Thanks

http://www.codechef.com/viewsolution/6245563

being a noob in programming, i implemented same algorithm…feeling proud of myself:P

2 Likes

@skysarthak try solving the question without the use of map stl.

Hi @skysarthak your AC solution http://www.codechef.com/viewsolution/6307954
.Now the problem with your code was, as the author asked you to take FAST IO, so applied that ,than WA came which was due to overflow.

1 Like

please add proper category tags to problems of feb15.
It is very helpful for beginners like us.