LFSTACK - Editorial

[pkacprzak]

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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:

Subtask 1

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.

Subtask 2

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.

Subtask 3

Let 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) * (A₂ + 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⁶, 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 (K₁, K₂), 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) * (A₂ + 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)

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.

[shubhiks]

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.

[moodies]

guys help me to find error i got SIGSEGV ERROR
https://www.codechef.com/viewsolution/11266659

[reikjavic]

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”.

[mathecodician]

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©-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?

[iam_ss]

How did you get the number of stacks <= 20? Can you please explain more?

[iam_ss]

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

[gvaibhav21]

this approach fails in this case:

first thread: 1 2

second thread: 1 2

stack: 2 1 1 2

[code_hard123]

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§

Therefore x <= log2(10^6) which is 19.

Hence number of stacks <= 20

[ssaxena36]

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

[suppu_the_boss]

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.

[satyroxx1397]

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.

[shubhiks]

Thanks a lot!

[garvit9613]

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

[todumanish]

please tell me what is the problem with this solution www.codechef.com/viewsolution/11273565

[srinathnairt]

Can someone explain how did they come up with (equation of) the maximum number of states ie. P = (A1 + 1) * (A2 + 1) * … * (AN + 1).

[srd091]

@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.

[srinathnairt]

@srd091 I meant how to come up with that equation “P = (A1 + 1) * (A2 + 1) * … * (AN + 1)” --(edited the post)

[econaxis]

wait, what if there are multiple matches available, then do you call 2 solves?

[rajdeep594]

#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