Woburn Challenge 2016-17 Round 2 - Senior Division

Problem 3: Turbolift Testing

Lieutenant commander Scetty has been assigned quite the tedious task - testing a turbolift. Hardly a job worthy of the Enterprise's chief engineer! This particular turbolift has just 2 buttons – one to take the turbolift up 1 floor, and another to take it down 1 floor.

One "button press" is an action consisting of, well, pressing one of the buttons. It can be represented as a single character, either "U" if the up button is pressed, or "D" if the down button is pressed.

One "button sequence" is an ordered sequence of one or more button presses. The turbolift has the ability to perform N (1 ≤ N ≤ 200,000) different types of button sequences, numbered from 1 to N, with the i-th one represented by the string B_i. The j-th character in this string represents the j-th button press in the sequence. The strings B_1..N are not necessarily distinct, and the sum of their lengths is at most 200,000.

The turbolift will start on floor 0 of the Enterprise. Due to recent technological advances, the ship has infinitely many floors above floor 0 (numbered upwards from 1), and infinitely many basement floors below it (numbered downwards from −1). As part of the testing process, it will then be programmed to execute M (1 ≤ M ≤ 200,000) button sequences, one after another. The i-th button sequence in this sequence of sequences will be button sequence is S_i (1 ≤ S_i ≤ N). Note that some button sequences could be executed multiple times during the testing, while others could not be executed at all.

Throughout the process, Scetty will make notes about how low and high the turbolift ends up getting. In particular, he has Q (1 ≤ Q ≤ 200,000) questions to answer. The i-th one asks: "After the first P_i button presses, what are the minimum and maximum floor numbers that the turbolift will have reached up to that point?". P_i is a positive integer no greater than the total number of button presses which will be executed throughout the sequence of M button sequences. Note that both P_i and the answers may not fit within a 32-bit integer.

In test cases worth 12/27 of the points, N ≤ 3000, M ≤ 3000, and no single button sequence consists of more than 3000 button presses.

Input Format

The first line of input consists of three space-separated integers N, M, and Q.
N lines follow, the i-th of which consists of a single string B_i (for i = 1..N).
M lines follow, the i-th of which consists of a single integer S_i (for i = 1..M).
Q lines follow, the i-th of which consists of a single integer P_i (for i = 1..Q).

Output Format

Output Q lines, the i-th of which should consist of two space-separated integers – the lowest and highest floors that the turbolift will reach after no more than P_i button presses (for i = 1..Q).

Sample Input

2 3 3
DDUU
U
2
1
2
1
6
4

Sample Output

0 1
-1 2
-1 1

Explanation

The turbolift will receive 6 button presses in total, with the following results:

Button | Floor
--------------
   U   |   1
   D   |   0
   D   |  -1
   U   |   0
   U   |   1
   U   |   2

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Dec 11, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Any hint as to why I'm failing all of the large test cases would be appreciated :)
http://wcipeg.com/submissions/src/442086