Prerequisites

This problem features sets represented by bit sequences. Understanding the basic concepts introduced in the following articles (all in Japanese) may help understanding the editorial of this problem.

• APG4b-AC 3.05.ビット演算 (APG4b-AC 3.05. Bit operations)
• ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 (Representing subsets using bit sequences (bitmask trick Advent Calendar 2016 Day 1))

First of all, it is useful to define state \(0\) where no chemicals are mixed, which we assume safe.
In other words, modifying the string \(S\) to “0”+\(S\) may facilitate the implementation (given that most languages regard the first character as the “\(0\)-th” character).

This problem asks to determine if it is reachable to state \(2^N-1\) from state \(0\) by successively adding one chemical after another.

State \(0\) is obviously reachable; starting from there, we enumerate next states transitionable from the current state.

One can enumerate the states transitionable from a state \(x\) as follows:

• If state \(x\) is unreachable, we do not have to consider advancing from state \(x\).
• Otherwise, repeat the following for \(k=1,2,\dots,N\).
  • If the \(k\)-th least significant bit of \(x\) is set, then chemical \(k\) is not mixed yet. By mixing chemical \(k\), we advance to state \(y=x+2^{k-1}\).
  • If this \(y\) is safe, then state \(y\) is transitionable.

All that left is to perform this process in ascending order of state indices, in order to check if each state is reachable.

The time complexity is \(O(2^N N)\) per case.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n;
    cin >> n;
    string s;
    cin >> s;
    s="0"+s;
    vector<int> ok(1<<n,0);
    ok[0]=1;
    for(int i=0;i<(1<<n);i++){
      if(ok[i]==0){continue;}
      for(int j=0;j<n;j++){
        if(i&(1<<j)){continue;}
        int next=(i|(1<<j));
        if(s[next]=='0'){ ok[next]=1; }
      }
    }
    if(ok[(1<<n)-1]){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  return 0;
}