VM7WC '16 #2 Silver - GG

View as PDF

Points: 5
Time limit: 0.1s
Java 0.5s
Python 0.5s
Memory limit: 64M

Author:
Problem type

G's are delivered through G-strings, which are made mostly of G's, and are not to be confused with the article of clothing. Sometimes, G's can be contaminated with other alphabetical characters—from old age or memory issues—and the integrity of the G-string becomes compromised.

Here is a prime G-string, made only of G's:

GGGGGGGGGGGGGGGGGG

Here is a contaminated G-string, with some other characters among the G's:

SKGCGUSGGGGOGGELGG

G-strings may be contaminated to the point that they contain no G's at all!

G-strings are only as good as the longest run of G's in the G-strings. Define the integrity of a G-string as the number of G's that are present in the string. For example, the integrity of the first string, GGGGGGGGGGGGGGGGGG, is . The integrity of the second string, SKGCGUSGGGGOGGELGGG, is .

We can find the integrity of a substring of a G-string as well. Using zero-based indexing, the substring from positions 0 to 3, inclusive, of the second given G-string is:

SKGC

The integrity of this substring is , as there is only one G in the entire substring. Create a program that, when given a G-string and a list of ranges queries, can determine the integrity of the substring within each range.

Input Specification

The input is a single line, containing the G-string to be examined. The length of the G-string is at most characters long and is comprised of only capital letter alphabetical characters.

On the second line is a single positive integer , the number of queries the program must process. The next lines each contain two non-negative integers and , where is the length of the given G-string.

Output Specification

For each query and on separate lines, print the integrity of the substring between positions and in the G-string, inclusive, and using zero-based indexing.

Sample Input 1

GGGGGGGGGGGGGGGGGG
4
1 3
2 9
3 4
0 17

Sample Output 1

3
8
2
18

Sample Input 2

KGCGUSGGGGOGGELGGG
5
1 3
2 9
3 4
0 0
0 17

Sample Output 2

2
5
1
0
11

• commented on July 20, 2019, 9:17 p.m.

Is this really dynamic programming, or do I just not really understand what that is?

• commented on June 3, 2017, 5:06 p.m.

Will a query ever be repeated?

• commented on June 3, 2017, 8:12 p.m.

It has not been noted in the question statement and is not the reason for your TLE. https://dmoj.ca/problem/vmss7wc16c2p2#comment-2632

• commented on June 3, 2017, 10:35 p.m.

I know, I'm not doing the problem right, but I don't understand how prefix sum arrays help. Doing some research and learning.

• commented on April 27, 2017, 4:34 p.m.

G-String!

• commented on Jan. 19, 2016, 7:17 p.m.

TLE is destroying my brain! Any tips?

• commented on Jan. 20, 2016, 12:54 a.m.

No regular user can see your submissions since the contest is still ongoing.

• commented on Jan. 21, 2016, 6:08 p.m.

Sure, looking at my submission might help you come up with tips. but giving general information on making programs more efficient or efficient methods are also valuable information to a beginner like me.

• commented on Jan. 21, 2016, 7:26 p.m.

This problem requires knowledge about prefix sum arrays. A quick Google search should be enough to figure out how to solve this.

• commented on Jan. 16, 2017, 2:09 p.m.

I personally always called them tallies- have I been wrong this whole time?

• commented on June 1, 2017, 10:10 p.m. edited

I don't really understand how this is a Dynamic Programming question. Isn't this supposed to be Data Structures?