×

# LFSTACK - Editorial

Author: Sergey Kulik
Tester: Harshil Shah
Editorialist: Pawel Kacprzak

SIMPLE-EASY

# 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:

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:

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:

and we are trying to produce sequence S = (4, 2, 3, 1)

Let 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[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:

Tester's solution can be found here.
Editorialist's solution can be found here.

This question is marked "community wiki".

73484390
accept rate: 12%

19.0k348495531

 6 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 56●3 accept rate: 11%
 4 This problem can also be solved by checking whether the stack input is a sub sequence of final set of integers my AC solution here answered 28 Aug '16, 08:51 766●5 accept rate: 28% 1 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)
 3 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 21 accept rate: 0%
 1 What's wrong with this approach: 1) Check the number which is taken out first if it is present at endpoint of one of the threads, if yes remove ALL those endpoint numbers and insert that number into a std::set. Move onto the next number to be taken out. 2)Keep on doing this and if we find that it doesn't match with any of the endpoints then check if it is present in set or not. If its not present then answer is NO. If yes move onto the next number to be taken out. 3)Atlast check the frequencies of each number to make sure that each number has occurred same no. of times in the final sequence and the initial threads. Its failing for the first test case of first subtask and passing all other tests. answered 27 Aug '16, 22:51 5★shubhiks 722●3●11 accept rate: 0% this approach fails in this case: first thread: 1 2 second thread: 1 2 stack: 2 1 1 2 (28 Aug '16, 00:43) Thanks a lot! :) (28 Aug '16, 19:10) shubhiks5★
 1 How did you get the number of stacks <= 20? Can you please explain more? answered 28 Aug '16, 00:37 3★iam_ss 41●3 accept rate: 0% 2 P = (a[1] + 1) * (a[2] + 1) * .... (a[n] + 1) and P <= 10^6 Let's try to maximize value of n greedily! We can do that replacing each a[i] with lowest possible value. (ie 1). So now P = 2 * 2 * ...... (let say x terms) so, P >= 2 ^ x ie x <= log2(P) Therefore x <= log2(10^6) which is 19. Hence number of stacks <= 20 :) (28 Aug '16, 01:22)
 0 guys help me to find error i got SIGSEGV ERROR https://www.codechef.com/viewsolution/11266659 answered 27 Aug '16, 23:25 3★moodies 21●1 accept rate: 0%
 0 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 2.6k●6●29 accept rate: 7%
 0 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 3★iam_ss 41●3 accept rate: 0%
 0 Can someone suggest a test case for the below approach: 1) Push the seq got onto a stack(s1) 2) For each thread Push the elements on a queue and then push that queue in a vector 3) Pop the top element from the stack(s1) and see if matches with the front of the any queue created in step 2 4) if it matches remove that element from the queue and jump to step 3 and if it doesnt that means the sequence is not possible. answered 28 Aug '16, 10:14 1 accept rate: 0%
 0 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 ? https://www.codechef.com/viewsolution/11266816 answered 28 Aug '16, 22:07 1 accept rate: 0%
 0 please tell me what is the problem with this solution www.codechef.com/viewsolution/11273565 answered 28 Aug '16, 22:29 63●2 accept rate: 0%
 0 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 21●3 accept rate: 0% @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)
 0 @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).the minimum value Ai can have is 1 so if we put A1=A2=A3=...=An=1, we will have P=$2^n$ and max value of sum of P is $10^6$ so n comes out to be less than 20. answered 28 Aug '16, 23:45 5★srd091 1.5k●1●11 accept rate: 41%
 0 wait, what if there are multiple matches available, then do you call 2 solves? answered 29 Aug '16, 10:30 2★econaxis 1 accept rate: 0%

# include<bits stdc++.h="">

using namespace std;

# define ll long long

int 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[a-i-1] != b[i]){ cout<<"No\n"; flag = 0; break; } } if(flag) { cout<<"Yes\n"; }

    } else {
int a[n];
stack<int> b[n];
ll p = 0;
for(ll i = 0; i < n; i++) {
cin>>a[i];
for(ll j = 0; j < a[i]; j++) {
ll k;
cin>>k;
b[i].push(k);
}
p = p + a[i];
}
int c[p];
for(ll i = 0; i < p; i++) {
cin>>c[i];
}
int flag = 0;
for(ll i = 0; i < p ; i++) {
flag = 0;
for(int j = 0; j < n; j++) {
if(!b[j].empty()){
int k = b[j].top();
if(c[i] == k) {
flag = 1;
b[j].pop();
break;
}
}
}
if(flag == 0) {  cout<<"No\n"; break; }
}
if(flag) {
cout<<"Yes\n";
}

}
}


} could you please tell me where am wrong

This answer is marked "community wiki".

1
accept rate: 0%

 0 Hows does my solution without memoization gives AC? Solution answered 02 Apr '17, 13:34 31 accept rate: 0%
 0 Please help. I can't ask any questions because of less Karma points. answered 02 Oct '17, 18:13 19●3 accept rate: 0% There is a thread named "I want to ask a question" . Redirect yourself there. (02 Oct '17, 19:25)
 0 weak test cases, got ac without using dp answered 18 Oct '17, 08:55 3★joker_98 1 accept rate: 0%
 0 I am getting 100 points by using recursion without memoization(DP). I guess test cases needs to be updated. Look at my solution: https://www.codechef.com/viewsolution/16555763 answered 11 Dec '17, 23:35 24●1●2●6 accept rate: 0%
 0 Hi guys, I'm not able to figure out why my solution is failing with NZEC. It works for small test cases - can it be because of StackOverflow? import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) { try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) { int T = Integer.parseInt(reader.readLine()); while (T-- > 0) { int N = Integer.parseInt(reader.readLine()); int[][] threads = new int[N][]; List threadLasts = new ArrayList<>(N); for (int i = 0; i < N; i++) { int[] inpArr = readArray(reader); int threadSize = inpArr[0]; threads[i] = Arrays.copyOfRange(inpArr, 1, threadSize + 1); threadLasts.add(threadSize - 1); } int[] sequence = readArray(reader); boolean sequenceValid = verifySequence(threads, sequence, 0, threadLasts, new HashMap<>()); System.out.println(sequenceValid ? "Yes" : "No"); } } catch (IOException e) { e.printStackTrace(); } } private static int[] readArray(BufferedReader reader) throws IOException { String[] strs = reader.readLine().trim().split("\\s+"); int[] items = new int[strs.length]; for (int i = 0; i < strs.length; i++) { items[i] = Integer.parseInt(strs[i]); } return items; } private static boolean verifySequence(int[][] threads, int[] sequence, int curr, List threadLasts, Map, Boolean> memo) { if (curr == sequence.length) { for (int threadLast : threadLasts) { if (threadLast != -1) { return false; } } return true; } if (memo.get(threadLasts) != null) return memo.get(threadLasts); int next = sequence[curr]; for (int i = 0; i < threadLasts.size(); i++) { if (threadLasts.get(i) != -1 && threads[i][threadLasts.get(i)] == next) { threadLasts.set(i, threadLasts.get(i) - 1); boolean isValid = verifySequence(threads, sequence, curr + 1, threadLasts, memo); memo.put(threadLasts, isValid); } } return false; } }  answered 29 May, 00:12 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,366
×1,754
×286
×104
×45
×28
×9

question asked: 27 Aug '16, 17:13

question was seen: 6,985 times

last updated: 29 May, 00:12