LFSTACK - Editorial

editorial
, , , , , ,
21

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

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

}

24

this approach fails in this case:

first thread: 1 2

second thread: 1 2

stack: 2 1 1 2

1 Like
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.