Recursion, DP, memoization
Given initially empty stack, a sequence of integers S, and N threads pushing integers to the stack in unspecified order across them, decide if there exists an order of pushes to the stack, such that after all pushes are performed, the sequence produced by popping all integers from the stack equals S. For each thread, the sequence of pushes of integers it performs is known and cannot be changed.
Use recursion to solve the problem. Try to match integers pushed from threads to the stack in all possible ways. Use memoization in order to avoid solving same subproblems many time.
Various approaches are possible for the first subtask. For example, since constraints are quite small here, a slow implementation of method described for the third subtask will do the job.
In the second subtask, we know that N = 1, which means that there is only a single thread. In order to solve this subtask, it is sufficient to check if after the thread pushed all its integers to the stack, the sequence of pops performed on the stack until it is empty equals the input sequence S. This can be done by explicitly using a stack data structure to simulate the process, or by just reversing the sequence of integers in the thread and comparing it to the sequence S. This works because the last element pushed to the stack is the first returned from it by the pop operation.
Let Ai denote the number of integers to be pushed to the stack by the ith thread. Remember that for a single thread they are pushed in the order they appear for this thread. The crucial observation is that there are at most P = (A1 + 1) * (A2 + 1) * … * (AN + 1) states in which all threads can ever be during any execution performing pushes from them to the stack - each state corresponds to the number of integers across all threads already pushed to the stack. Moreover, since P ≤ 106, the number of stacks is quite small, in fact, less than 20.
For example, if we have 2 threads:
Thread #1: [1, 2]
Thread #2: [2, 3, 4]
Then all the states can be described by a pair of integers (K1, K2), where Ki denotes the number of integers remaining to be pushed from the ith thread to the stack. Moreover, Ki can be any integer in range [0, Ai], so in this particular case, we have (A1 + 1) * (A2 + 1) = 12 possible states: (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3).
Knowing that, we can solve the problem using recursion, trying to match the current integer in sequence S, starting from the first one, with first not yet matched integer in any of the threads (in reverse order they appear on the list in a single thread), simulate the push operation from the selected thread if there is a match and solve the resulting smaller problem in the same way. The base case of recursion is when all threads are empty. If this state can be ever achieved, the solution exists. Otherwise, there is no solution to the problem.
As an example, let’s try to solve the instance of the problem given in the statement. We have two threads:
Thread #1: [1, 2]
Thread #2: [3, 4]
and we are trying to produce sequence S = (4, 2, 3, 1)
solve(cur_pos, cur_state) denote the instance of the problem when threads are in state
cur_state and we are trying to match the suffix of S starting at
cur_pos position. The answer to the problem is the result of solving solve(1, (2, 2)).
First, we try to match S = 4 with any of first not yet matched integers in the threads (for each thread this integer is denoted clearly by the number of elements remaining to be pushed from this thread, so in the first call, for the first thread it is 2 and for the second thread it is 4). Since there is only a single match possible, we simulate pushing 4 from the second tread and call solve(2, (2, 1)). The next recursive call will be solve(3, (1, 1)) and so one until we finally reach state (0, 0) for which we know that all integers in S are matched, so the solution exists. Notice that since the number of all threads is small, we can explicitly iterate over all of them to check for a possible matches.
The last thing is to remember to implement the solution efficiently. In other words, to avoid solving same subproblems many times, which may occur and slow the solution significantly. This can be done by memoization technique, i.e. by storing states for each results are already computed in a set along with result for them. Now if there is a need to solve some subproblem, first check if its result is already computed and if it is, return the result immediately. Otherwise, compute the result using recursion described above. For implementation details please refer to author’s and tester’s solutions.
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester's solution can be found [here]. Editorialist's solution can be found [here].