PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:SIMPLEEASY PREREQUISITES:Recursion, DP, memoization PROBLEM: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. QUICK EXPLANATION: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. EXPLANATION:Subtask 1Various 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. Subtask 2In 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. Subtask 3Let A_{i} denote the number of integers to be pushed to the stack by the i^{th} 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 = (A_{1} + 1) * (A_{2} + 1) * … * (A_{N} + 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 ≤ 10^{6}, the number of stacks is quite small, in fact, less than 20. For example, if we have 2 threads: Thread #1: [1, 2] Then all the states can be described by a pair of integers (K_{1}, K_{2}), where K_{i} denotes the number of integers remaining to be pushed from the i^{th} thread to the stack. Moreover, K_{i} can be any integer in range [0, A_{i}], so in this particular case, we have (A_{1} + 1) * (A_{2} + 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] and we are trying to produce sequence S = (4, 2, 3, 1) Let First, we try to match S[1] = 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:
This question is marked "community wiki".
asked 27 Aug '16, 17:13

Sorry, this is off topic but since this is the top post, how am I supposed to ask questions on here, it says that I don't have enough "Karma". answered 27 Aug '16, 23:29

This problem can also be solved by checking whether the stack input is a sub sequence of final set of integers
answered 28 Aug '16, 08:51
No it cannot be solved by this method. Check the test case here : 1 2 2 1 4 2 1 4 4 1 1 4 the answer should be No but your code is giving Yes.Obviously the test cases are weak.
(28 Aug '16, 14:02)

ADMIN test cases for this questions is weak. Add these test case in the test case file then most of the submission that already done will fail. 1 2 6 1 5 7 10 12 14 5 1 6 9 4 3 3 4 1 14 12 9 10 7 6 5 1 Happy coding!!! answered 04 Sep '16, 13:55

guys help me to find error i got SIGSEGV ERROR https://www.codechef.com/viewsolution/11266659 answered 27 Aug '16, 23:25

for i in range(int(input())): n = int(input()) if n == 1: a = [int(j) for j in input().split()] b = [int(k) for k in input().split()] c = a[::1] if b == c[:len(c)1]: print("Yes") else: print("No") else: a = [] for j in range(n): a.append([k for k in input().split()][1:]) b = [l for l in input().split()][::1] f = 0 for m in range(len(b)): for x in range(len(a)): for y in range(len(a)): if a[x][0] == a[y][0] and x != y: f = 1 for oo in range(len(a)): if len(a[oo]) != 0: if a[oo][0] == b[m]: a[oo].remove(a[oo][0]) break else: print("No") f = 1 if f == 0: print("Yes") else: print("No") # Why did I get only 11 points for this? answered 28 Aug '16, 00:07

Check out this test case. 1 3 5 1 1 1 1 1 3 1 1 2 3 2 1 1 2 1 1 1 1 1 1 1 1 2 1 Output: Yes answered 28 Aug '16, 00:41

Can someone suggest a test case for the below approach:
answered 28 Aug '16, 10:14

My solution got accepted but it doesn't handle the following test case: 1 2 2 3 2 2 3 2 2 3 3 2 My ans :"Yes". Actual ans should be "No", I suppose. Could someone have a look at my submission and confirm whether the test case has been missed ? answered 28 Aug '16, 22:07

please tell me what is the problem with this solution www.codechef.com/viewsolution/11273565 answered 28 Aug '16, 22:29

Can someone explain how did they come up with (equation of) the maximum number of states ie. P = (A1 + 1) * (A2 + 1) * … * (AN + 1). answered 28 Aug '16, 23:38
@srd091 I meant how to come up with that equation "P = (A1 + 1) * (A2 + 1) * … * (AN + 1)" (edited the post)
(29 Aug '16, 00:12)

@srinathnairt the result P=(A1+1)(A2+1)..(An+1) can be inferred from that initially we can insert 0 elements of A1 or 1 element of A1 or 2 elements consecutively of A1...or all elements of A1 consecutively i.e., A1+1 total combinations similarly for other threads which results in total combinations equal to (A1+1)(A2+1)..(An+1). answered 28 Aug '16, 23:45

wait, what if there are multiple matches available, then do you call 2 solves? answered 29 Aug '16, 10:30

include<bits stdc++.h="">using namespace std; define ll long longint main(){ int t; cin>>t; int n; while(t) { cin>>n; if(n == 1) { int a; cin>>a; int b[a]; int c[a]; for(int i = 0; i < a; i++) { cin>>b[i]; } for(int i = 0; i < a; i++) { cin>>c[i] ; } int flag = 1; for(int i = 0; i < a; i++) { if(c[ai1] != b[i]){ cout<<"No\n"; flag = 0; break; } } if(flag) { cout<<"Yes\n"; }
} could you please tell me where am wrong
link
This answer is marked "community wiki".
answered 31 Aug '16, 00:21

Please help. I can't ask any questions because of less Karma points. answered 02 Oct, 18:13
