LFSTACK - Editorial

editorial
, , , , , ,
25

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

5 Likes
26

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.

1 Like
27

Thanks a lot! :slight_smile:

28

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

29

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

30

Please tell me what is wrong in my code or give me test cases that may fail. Thanks.
My Answer

31

Links to Tester’s and Editorialist’s solutions are not available. Please have a look :slight_smile:

32

My solution got accepted with Recursion approach using array of stacks. It’s test cases needs to be updated.
Solution

33

Testcase for no constraints:
1
2
2 -1 -2
2 -3 -4
-4, -2, -3, -1
Yes

34

What will be the ans for
first thread: 1 2

second thread: 1 2

stack: 2 1 1 2

no or yes?

36

@payal2605 The answer should be no for this case.

37

Why this problem is not taking the submissions?
Giving the error message - "Solutions to this problem cannot be submitted now! ".

1 Like
38

Once we get a match for a solve, the answer would be “yes”. There is no need to call solve again.

39

https://www.codechef.com/viewsolution/37397643
please help me I am getting WA for my sol can you figure out the mistake in it

40

How do I solve test cases where there can be multiple matches and if choosing one match instead of other can result in ‘no’ but choosing another match results in ‘yes’ ?

Example:
first thread: 1 2
second thread: 2 3
2 3 2 1
Result is ‘yes’ but if I choose 2 from first thread instead of second results in ‘no’.

Another example:
First thread: 1 2 4
Second thread: 3 2 4 8
4 8 4 2 2 3 1
Result is ‘yes’ only if 4 from second thread is chosen on encountering first 4 in the sequence otherwise result comes out to be ‘no’, even though the sequence is valid.
How do I solve this?

41

Your approach is Partially Correct i.e for some test Cases

42

That post was made in 2016.

43

You have made the qq array with size q and above your code q is 0, thus you are getting segmentation fault SIGSEV.

44

can someone please tell me ,why my code gives TLE in subtask3.
https://www.codechef.com/viewsolution/48329409
thanks in advance.

45

https://www.codechef.com/viewsolution/57452032

I have tried backtracking and I got a segmentation error. Can anybody tell me where I did the mistake??

Thanks in Advance!