Hide

# Problem ABaby Names

Kattis is having a baby! O.o. However, she does not know what to name her baby. Thankfully, her friends have many ideas, giving suggestions for both genders.

Given $\textbf{N}$ distinct baby name suggestions (each babyName string consists of only UPPERCASE alphabet characters of no more than $30$ characters) and the genderSuitability of that name (integer $\textbf{1}$ for $\textbf{male}$ or integer $\textbf{2}$ for $\textbf{female}$) and given $\textbf{Q}$ queries, tell Kattis how many baby names start with a prefix that is inside a given query interval $[\textbf{start} \ldots \textbf{end})$, where $\textbf{start} < \textbf{end}$, and both are strings.

Note: A prefix of a string $T = T_{0}T_{1} \ldots T_{n-1}$ is string $P = T_{0}T_{1} \ldots T_{m-1}$ where $m \le n$

There will be $4$ types of commands:

1. Stop: This will be indicated by a $0$. Stop your program upon encountering this.

2. Add Suggestion: This will be indicated by a starting integer $1$ followed by a string babyName and an integer genderSuitability, e.g. $1$ SIMBA $1$.

3. Remove Suggestion: This will be indicated by a starting integer $2$ followed by a string: babyName, e.g. $2$ SIMBA. The babyName is guaranteed to have already been suggested earlier.

4. Query: This will be indicated by a starting integer $3$ followed by two strings: start, end, and an integer genderSuitability. Your job is to return the number of names that is inside the interval $[\textbf{start} \ldots \textbf{end})$ subject to the following criteria.

• If genderSuitability = $0$: report number of names for both genders

• If genderSuitability = $1$: report number of male names

• If genderSuitability = $2$: report number of female names

## Input

Each line will be a certain command. The program terminates when it encounters $0$. There are up to $200\, 000$ babyName suggestions and $Q$ is up to $500\, 000$.

## Output

Each time the $\textbf{Query}$ command is encountered, the number of suitable names should be printed.

1. $\textbf{(30 points)}$: $1 \le N \le 20$, $1 \le Q \le 10$, and all baby names have distinct first letters

2. $\textbf{(30 points)}$: $1 \le N \le 20\, 000$, $1 \le Q \le 20\, 000$

3. $\textbf{(40 points)}$: $1 \le N \le 200\, 000$, $1 \le Q \le 500\, 000$

Sample Input 1 Sample Output 1
1 KATTISJR 2
1 OLIVER 1
1 SIMBA 1
3 A Z 0
3 A Z 1
3 A Z 2
2 SIMBA
3 A Z 0
3 A Z 1
3 A Z 2
0

3
2
1
2
1
1
{"ft_lang_label":"__label__en","ft_lang_prob":0.7310118,"math_prob":0.99775326,"size":2403,"snap":"2023-14-2023-23","text_gpt3_token_len":747,"char_repetition_ratio":0.12671946,"word_repetition_ratio":0.098086126,"special_character_ratio":0.3241781,"punctuation_ratio":0.114754096,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9961083,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-03-22T18:46:37Z\",\"WARC-Record-ID\":\"<urn:uuid:b6d12bc0-2ccd-4cd6-a947-917788b5f200>\",\"Content-Length\":\"32660\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b4dd6217-bbfa-4a4d-b01c-7020094d32b1>\",\"WARC-Concurrent-To\":\"<urn:uuid:07f2d5a6-6ac8-4425-88b8-e7aa25014b45>\",\"WARC-IP-Address\":\"172.66.40.162\",\"WARC-Target-URI\":\"https://nus.kattis.com/courses/CS2040C/CS2040C_S1_AY1920/assignments/gsfm3j/problems/babynames\",\"WARC-Payload-Digest\":\"sha1:AKQQUOTJMNDNIXKNTFVYJF7MJH4XLBQT\",\"WARC-Block-Digest\":\"sha1:ZU6NHZDM7MJRPW26OVS3V224NQWENDMF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-14/CC-MAIN-2023-14_segments_1679296944452.74_warc_CC-MAIN-20230322180852-20230322210852-00294.warc.gz\"}"}