for i in range(int(input())):
n = int(input())
if n == 1:
a = [int(j) for j in input().split()]
b = [int(k) for k in input().split()]
c = a[::-1]
if b == c[:len©-1]:
print(“Yes”)
else:
print(“No”)
else:
a = []
for j in range(n):
a.append([k for k in input().split()][1:])
b = [l for l in input().split()][::-1]
f = 0
for m in range(len(b)):
for x in range(len(a)):
for y in range(len(a)):
if a[x][0] == a[y][0] and x != y:
f = 1
for oo in range(len(a)):
if len(a[oo]) != 0:
if a[oo][0] == b[m]:
a[oo].remove(a[oo][0])
break
else:
print(“No”)
f = 1
if f == 0:
print(“Yes”)
else:
print(“No”)
# Why did I get only 11 points for this?
How did you get the number of stacks <= 20? Can you please explain more?
2 Likes
Check out this test case.
1 3 5 1 1 1 1 1 3 1 1 2 3 2 1 1 2 1 1 1 1 1 1 1 1 2 1
Output: Yes
1 Like
This problem can also be solved by checking whether the stack input is a sub sequence of final set of integers
my AC solution
here
4 Likes
Can someone suggest a test case for the below approach:
-
Push the seq got onto a stack(s1)
-
For each thread Push the elements on a queue and then push that queue in a vector
-
Pop the top element from the stack(s1) and see if matches with the front of the any queue created in step 2
-
if it matches remove that element from the queue and jump to step 3 and if it doesnt that means the sequence is not possible.
My solution got accepted but it doesn’t handle the following test case:
1
2
2 3 2
2 3 2
2 3 3 2
My ans :“Yes”.
Actual ans should be “No”, I suppose.
Could someone have a look at my submission and confirm whether the test case has been missed ?
Can someone explain how did they come up with (equation of) the maximum number of states ie. P = (A1 + 1) * (A2 + 1) * … * (AN + 1).
@srinathnairt the result P=(A1+1)(A2+1)…(An+1) can be inferred from that initially we can insert 0 elements of A1 or 1 element of A1 or 2 elements consecutively of A1…or all elements of A1 consecutively i.e., A1+1 total combinations similarly for other threads which results in total combinations equal to (A1+1)(A2+1)…(An+1).
the minimum value Ai can have is 1 so if we put A1=A2=A3=…=An=1, we will have P=2^n and max value of sum of P is 10^6 so n comes out to be less than 20.
wait, what if there are multiple matches available, then do you call 2 solves?
2 Likes
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int t;
cin>>t;
int n;
while(t–) {
cin>>n;
if(n == 1) {
int a;
cin>>a;
int b[a];
int c[a];
for(int i = 0; i < a; i++) {
cin>>b[i];
}
for(int i = 0; i < a; i++) {
cin>>c[i] ;
}
int flag = 1;
for(int i = 0; i < a; i++) {
if(c[a-i-1] != b[i]){
cout<<“No\n”;
flag = 0;
break;
}
}
if(flag) { cout<<“Yes\n”; }
} else {
int a[n];
stack<int> b[n];
ll p = 0;
for(ll i = 0; i < n; i++) {
cin>>a[i];
for(ll j = 0; j < a[i]; j++) {
ll k;
cin>>k;
b[i].push(k);
}
p = p + a[i];
}
int c[p];
for(ll i = 0; i < p; i++) {
cin>>c[i];
}
int flag = 0;
for(ll i = 0; i < p ; i++) {
flag = 0;
for(int j = 0; j < n; j++) {
if(!b[j].empty()){
int k = b[j].top();
if(c[i] == k) {
flag = 1;
b[j].pop();
break;
}
}
}
if(flag == 0) { cout<<"No\n"; break; }
}
if(flag) {
cout<<"Yes\n";
}
}
}
}
could you please tell me where am wrong
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