LFSTACK - Editorial

editorial
, , , , , ,
21

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

2 Likes
22

Hows does my solution without memoization gives AC?

Solution

23

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

24

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

25

weak test cases, got ac without using dp

26

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

27

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;
    }
}
28

Please help me why the following code is giving NZEC error (Lock free stack problem)

for i in range(int(input())):

n = int(input())
t1 = list(map(int, input().strip().split()))
t2 = list(map(int, input().strip().split()))
t1.extend(t2[1:])
s = []
s.append(t1[1:])
revers = list(map(int, input().strip().split()))
if revers == s[0][::-1] :
    print("Yes")
else :
    print("No")
#print("Yes" if revers == s[0][::-1] else "No")