You are not logged in. Please login at www.codechef.com to post your questions!

×

LFSTACK - Editorial

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 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)

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

asked 27 Aug '16, 17:13

pkacprzak's gravatar image

5★pkacprzak ♦♦
72483888
accept rate: 12%

edited 27 Aug '16, 22:32

admin's gravatar image

0★admin ♦♦
17.4k347486515


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

link

answered 27 Aug '16, 23:29

reikjavic's gravatar image

3★reikjavic
563
accept rate: 11%

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

link

answered 28 Aug '16, 08:51

ssaxena36's gravatar image

5★ssaxena36
7565
accept rate: 28%

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) satyroxx13975★

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!!!

link

answered 04 Sep '16, 13:55

namangupta01's gravatar image

2★namangupta01
11
accept rate: 0%

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

link

answered 28 Aug '16, 00:37

iam_ss's gravatar image

3★iam_ss
112
accept rate: 0%

edited 28 Aug '16, 00:38

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) code_hard1235★

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.

link

answered 27 Aug '16, 22:51

shubhiks's gravatar image

5★shubhiks
10113
accept rate: 0%

edited 27 Aug '16, 22:53

this approach fails in this case:
first thread: 1 2
second thread: 1 2
stack: 2 1 1 2

(28 Aug '16, 00:43) gvaibhav217★

Thanks a lot! :)

(28 Aug '16, 19:10) shubhiks5★

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

link

answered 27 Aug '16, 23:25

moodies's gravatar image

3★moodies
211
accept rate: 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?

link

answered 28 Aug '16, 00:07

mathecodician's gravatar image

6★mathecodician
2.6k322
accept rate: 8%

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

link

answered 28 Aug '16, 00:41

iam_ss's gravatar image

3★iam_ss
112
accept rate: 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.

link

answered 28 Aug '16, 10:14

suppu_the_boss's gravatar image

2★suppu_the_boss
1
accept rate: 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

link

answered 28 Aug '16, 22:07

garvit9613's gravatar image

2★garvit9613
1
accept rate: 0%

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

link

answered 28 Aug '16, 22:29

todumanish's gravatar image

4★todumanish
632
accept rate: 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).

link

answered 28 Aug '16, 23:38

srinathnairt's gravatar image

5★srinathnairt
213
accept rate: 0%

edited 29 Aug '16, 00:13

@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) srinathnairt5★

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

link

answered 28 Aug '16, 23:45

srd091's gravatar image

5★srd091
1.5k111
accept rate: 42%

edited 29 Aug '16, 01:27

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

link

answered 29 Aug '16, 10:30

econaxis's gravatar image

0★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

link
This answer is marked "community wiki".

answered 31 Aug '16, 00:21

rajdeep594's gravatar image

2★rajdeep594
1
accept rate: 0%

Hows does my solution without memoization gives AC?

Solution

link

answered 02 Apr, 13:34

makeitdonesolo's gravatar image

5★makeitdonesolo
31
accept rate: 0%

Please help. I can't ask any questions because of less Karma points.

link

answered 02 Oct, 18:13

shivam2296's gravatar image

2★shivam2296
192
accept rate: 0%

There is a thread named "I want to ask a question" . Redirect yourself there.

(02 Oct, 19:25) vijju123 ♦4★

weak test cases, got ac without using dp

link

answered 18 Oct, 08:55

joker_98's gravatar image

3★joker_98
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×12,235
×1,320
×255
×96
×43
×27
×9

question asked: 27 Aug '16, 17:13

question was seen: 5,963 times

last updated: 18 Oct, 08:55