Problem: travel_restrictions (2020 quals)

2020 has been a tough year for travelers. Air travel is especially problematic as passengers need to spend long periods in security lines, waiting areas, and crowded cabins where social distancing is difficult to maintain.

To minimize the spread of COVID-19, each airline has decided to reorganize all of their flight routes in a linear fashion. The airlines are hoping that by not making any one country a "hub", the spread of the virus will be significantly limited.

An airline's flights normally service \(N\) countries, running in various directions. Amidst the pandemic, each airline has carefully arranged these \(N\) countries in a sequence with each assigned a number from \(1\) to \(N\). Flights are limited to run only between pairs of countries that are adjacent in this sequence, with service in both directions. No other flights are available. That is, flights are available from country \(i\) to country \(j\) if and only if \(|i - j| = 1\).

To make things more complicated, some countries have issued their own restrictions on incoming and outgoing travel. These restrictions are indicated by the characters \(I_{1..N}\) and \(O_{1..N}\), each of which is either *"N"* or *"Y"*:

  - If \(I_i\) = *"N"*, then incoming flights to country \(i\) from any other country are disallowed. Otherwise, if \(I_i\) = *"Y"*, they may be allowed.
  - If \(O_i\) = *"N"*, then outgoing flights from country \(i\) to any other country are disallowed. Otherwise, if \(O_i\) = *"Y"*, they may be allowed.

If a flight between adjacent countries is disallowed by the restrictions of neither its departure country nor its arrival country, then it's allowed.

As a consulting data scientist in the airline industry, your job is to determine which trips between the various countries are possible. Let \(P_{i,j}\) = *"Y"* if it's possible to travel from country \(i\) to country \(j\) via a sequence of 0 or more flights (which may pass through other countries along the way), and \(P_{i,j}\) = *"N"* otherwise. Note that \(P_{i,i}\) is always *"Y"*. Output this \(N*N\) matrix of characters.

# Input

Input begins with an integer \(T\), the number of airlines. For each airline, there are three lines. The first line contains the integer \(N\). The second line contains the length-\(N\) string \(I_{1..N}\). The third line contains the length-\(N\) string \(O_{1..N}\).

# Output

For the \(i\)th airline, output a line containing *"Case #i:"* followed by \(N\) more lines, the \(i\)th of which contains the length-\(N\) string \(P_{i,1..N}\).

# Constraints

\(1 \le T \le 100\)
\(2 \le N \le 50\)

# Explanation of Sample

In the first case, there are two countries with no restrictions. Therefore, trips between all pairs of countries are possible.

In the second case, there are two countries, and traveling into country 1 is restricted. Since country 2 is the only country adjacent to country 1, the only impossible trip is from country 2 to country 1.

In the third case, there are two countries, both of which restrict inbound travel.

In the fourth case, one may not enter countries 2 or 3, nor exit country 4.


Sample input:
5
2
YY
YY
2
NY
YY
2
NN
YY
5
YNNYY
YYYNY
10
NYYYNNYYYY
YYNYYNYYNY


Sample output:
Case #1:
YY
YY
Case #2:
YY
NY
Case #3:
YN
NY
Case #4:
YNNNN
YYNNN
NNYYN
NNNYN
NNNYY
Case #5:
YYYNNNNNNN
NYYNNNNNNN
NNYNNNNNNN
NNYYNNNNNN
NNYYYNNNNN
NNNNNYNNNN
NNNNNNYYYN
NNNNNNYYYN
NNNNNNNNYN
NNNNNNNNYY


Solution: For each starting country \(s\), the set of destination countries which it's possible to reach must form some consecutive interval \(A_s..B_s\), such that \(A_s \leq s \leq B_s\).

We can begin by assuming that \(B_s = s\), and then repeatedly increase \(B_s\) until it has reached either country \(N\) or the first country after \(s\) which is unreachable from it. As long as \(B_s < N\), it should be incremented if flights are allowed from country \(B_s\) to country \(B_s+1\), which is the case if and only if \(O_{B_s} = I_{B_s+1} =\) *"Y"*.

The above process can be performed for each starting country \(s\), and repeated similarly to compute each \(A_s\) value. \(A_{1..N}\) and \(B_{1..N}\) may then be used to populate the required \(P\) matrix. Each part of this solution takes \(O(N^2)\) time.


Code: // Travel Restrictions
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x) {
  char c, r = 0, n = 0;
  x = 0;
  for (;;) {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      x = x * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 55

int N;
char I[LIM], O[LIM];
bool P[LIM][LIM];

void ProcessCase()
{
  // input
  Read(N);
  scanf("%s%s", I, O);
  // simulate rightward trips
  int i, j;
  Fill(P, 0);
  Fox(i, N)
  {
    j = i;
    for (;;)
    {
      P[i][j] = 1;
      if (j + 1 == N || O[j] == 'N' || I[j + 1] == 'N')
        break;
      j++;
    }
  }
  // simulate leftward trips
  Fox(i, N)
  {
    j = i;
    for (;;)
    {
      P[i][j] = 1;
      if (j - 1 < 0 || O[j] == 'N' || I[j - 1] == 'N')
        break;
      j--;
    }
  }
  // output
  Fox(i, N)
  {
    Fox(j, N)
      printf("%c", P[i][j] ? 'Y' : 'N');
    printf("\n");
  }
}

int main() {
  int T, t;
  Read(T);
  Fox1(t, T)
  {
    printf("Case #%d:\n", t);
    ProcessCase();
  }
  return(0);
}