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

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

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

@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.
My Answer

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

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?

@payal2605 The answer should be no for this case.

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