VM7WC '16 #2 Silver - GG

View as PDF
Submit solution
Points: 5
Time limit: 0.1s
Java 0.5s
Python 0.5s
Memory limit: 64M
Author:
JeffreyZ
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 18. The integrity of the second string, SKGCGUSGGGGOGGELGGG, is 11.

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 1, 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 10^5 characters long and is comprised of only capital letter alphabetical characters.

On the second line is a single positive integer Q (1 \le Q \le 10^5), the number of queries the program must process. The next Q lines each contain two non-negative integers i and j (0 \le i \le j < N), where N 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 i and j 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

Comments


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

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


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

    Will a query ever be repeated?


    • 0
      mse387  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


      • 0
        Pleedoh  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.


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

    G-String!


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

    TLE is destroying my brain! Any tips?


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

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


      • 0
        ceongh  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.


        • 0
          r3mark  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.


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

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


            • 17
              Ninjaclasher  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?