VM7WC '16 #2 Silver - GG

View as PDF

Submit solution

Points: 5
Time limit: 3.0s
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 from 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 \leq Q \leq 10^5), the number of queries the program must process. The next Q lines each contain two non-negative integers i and j, (0 \leq i, 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


  • 1
    sankeeth_ganeswaran  commented on July 20, 2019, 5: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, 1:06 p.m.

    Will a query ever be repeated?


    • 0
      mse387  commented on June 3, 2017, 4: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, 6:39 p.m.

        Also if you don't mind, please tell me why the C++ is TLE on cases that Java does just fine, not really sure what the difference between the programs is.


      • 0
        Pleedoh  commented on June 3, 2017, 6: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.


        • 0
          mse387  commented on June 3, 2017, 6:59 p.m.

          Since I obviously shouldn't outline solutions here, and the discussion is drifting off topic, do you mind joining the DMOJ Slack @ https://slack.dmoj.ca/ ?


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

    G-String!


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

    TLE is destroying my brain! Any tips?


    • 0
      jeffreyxiao  commented on Jan. 19, 2016, 7:54 p.m.

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


      • 0
        ceongh  commented on Jan. 21, 2016, 1: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, 2: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.


          • 0
            println_hi_  commented on Jan. 16, 2017, 9:09 a.m.

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


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

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


  • 0
    LordSparks86  commented on Jan. 15, 2016, 3:57 a.m.

    The second string, SKGCGUSGGGGOGGELGG is said to have an integrity of 10, but is it not 11?


    • 0
      JeffreyZ  commented on Jan. 15, 2016, 8:55 a.m. edited

      Yes, problem statement fixed. The sample test cases were correct from the beginning.