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

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

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

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.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<Integer> 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<Integer> threadLasts,
Map<List<Integer>, 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;
}
}
```

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:

first thread: 1 2

second thread: 1 2

stack: 2 1 1 2

1 Like

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

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.

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

first thread: 1 2

second thread: 1 2

stack: 2 1 1 2

no or yes?

Why this problem is not taking the submissions?

Giving the error message - "Solutions to this problem cannot be submitted now! ".