 # LFSTACK - Editorial

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

3 Likes

Hows does my solution without memoization gives AC?

Solution

weak test cases, got ac without using dp

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

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.util.*;

public class Main {
public static void main(String[] args) {

while (T-- > 0) {

for (int i = 0; i < N; i++) {

}

System.out.println(sequenceValid ? "Yes" : "No");
}

} catch (IOException e) {
e.printStackTrace();
}
}

int[] items = new int[strs.length];

for (int i = 0; i < strs.length; i++) {
items[i] = Integer.parseInt(strs[i]);
}
return items;
}

Map<List<Integer>, Boolean> memo) {

if (curr == sequence.length) {
return false;
}
}
return true;
}

int next = sequence[curr];

for (int i = 0; i < threadLasts.size(); i++) {
}
}

return false;
}
}``````

I am simulating excatly like the problem does, using a vector of stacks and poping elems after checking if the top mactches the elem as per sequence. My solution does not get accepted.

void solve_problems()
{
unsigned long int T = 0, N = 0;
long long int sum = 0, A = 0, B = 0, K = 0, M = 0;
std::cin >> T;
while (T–) {
sum = 0;
std::cin >> N;
std::deque<std::stack > stacks(N);
forl(i, 0, N) {
std::cin >> K;
sum = sum + K;
forl(j, 0, K) {
std::cin >> A;
stacks[i].push(A);
}
}
std::deque sequence(sum);
forl(j, 0, sum) {
std::cin >> sequence[j];
}

``````	forl(i, 0, sum) {
bool not_found = true;
if (sequence.empty()) break;
auto find = sequence.front();
forl(j, 0, N) {
if (!stacks[j].empty() && find == stacks[j].top()) {
not_found = false;
stacks[j].pop();
sequence.pop_front();
break;
}
}
if (not_found) {
std::cout << "No" << std::endl;
break;
}
}

bool all_stacks_empty = true;
forl(i, 0, N) {
if (!stacks[i].empty()) {
all_stacks_empty = false;
}
}

if (sequence.empty() && all_stacks_empty) {
std::cout << "Yes" << std::endl;
}
}
``````

}

this approach fails in this case:

stack: 2 1 1 2

1 Like

P = (a + 1) * (a + 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 5 Likes

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

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

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

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

Links to Tester’s and Editorialist’s solutions are not available. Please have a look My solution got accepted with Recursion approach using array of stacks. It’s test cases needs to be updated.
Solution

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

What will be the ans for