Problem: alchemy (2020 quals)

Edgar and his younger brother Alfred are alchemists in search of the legendary Philosopher's Stone. The Philosopher's Stone (also known as the Red Stone, the Fifth Element, and the Elixir of Life in liquid form) is a powerful alchemical substance rumoured to support the transmutation of silver, gold, and even human lives. Edgar is hoping to use the stone to restore his brother's body to its original form following a terrifying human transmutation accident.

It is known that Philosopher's Stones break apart into an odd number of shards when they're used up. After searching far and wide, Edgar has collected \(N\) shards of what he believes to be a previously-used Philosopher's Stone, where \(N\) is an odd integer. He believes that fusing these shards back together will yield a real stone in its entirety.

Leveraging his encyclopedic knowledge of alchemy, Edgar recalls an ancient book with the following ritual for fusing shards:

  1. Arrange the \(N\) shards in a row, numbered from 1 to \(N\).
  2. Note the colour \(C_i\) of each shard \(i\), which is either *auburn* or *black* (denoted by the characters *"A"* and *"B"* respectively).
  3. Choose a consecutive sequence of three shards, remove them from the row, and fuse them together into one new shard. The three shards must not all be the same colour, or such an intense concentration of similar energies will cause a dangerous rebound explosion. Instead, there must be two differently-coloured shards that will neutralize each other, get converted into energy (via the Law of Equivalent Exchange), and become infused with the third shard. In other words, assuming no explosion, the resulting shard's colour will be equal to the most common colour present amongst the three chosen shards.
  4. Place the resulting shard back into the original gap in the row, with the remaining shards in the same relative order before and after it.
  5. Repeat steps 3 and 4 until only one shard remains.

Note that each time steps 3 and 4 are performed, the number of remaining shards decreases by 2. Therefore, given that the initial number of shards is odd, enough successful repetitions will result in exactly one final shard: the Philosopher's Stone. Help Edgar determine whether or not it's possible to get to that point and hopefully save Alfred, without causing any rebound explosions along the way.


# Input

Input begins with an integer \(T\), the number of Philosopher's Stones that Edgar tries to reconstitute. For each stone there are two lines. The first contains the integer \(N\). The second contains the length-\(N\) string \(C_{1..N}\).

# Output

For the \(i\)th stone, output a line containing *"Case #i: "* followed by a single character, either *"Y"* if it's possible For Edgar to end up with the Philosopher's Stone, or *"N"* if not.

# Constraints

\(1 \le T \le 95\)
\(3 \le N \le 99,999\)
\(N\) is odd
\(C_i \in \{A, B\}\)

The sum of \(N\) over all test cases is at most 1,000,000.

# Explanation of Sample

In the first case, Edgar is able to fuse the three shards together, as they include two differently-coloured shards, yielding a single black-coloured shard: the Philosopher's Stone.

In the second case, the three black shards will inevitably cause a rebound explosion if fused.

In the third case, Edgar can begin by fusing the first three shards into a single auburn-coloured shard. The row of shards will then feature colours *"ABA"*, and those shards can be fused into the Philosopher's Stone.



Sample input:
6
3
BAB
3
BBB
5
AABBA
7
BAAABAA
11
BBBAABAAAAB
11
BABBBABBABB


Sample output:
Case #1: Y
Case #2: N
Case #3: Y
Case #4: N
Case #5: Y
Case #6: N


Solution: Let \(F_A\) and \(F_B\) be the number of *"A"* (auburn) shards and the number of *"B"* (black) shards, respectively.

We can observe that every time shards are fused \(F_A\) and \(F_B\) each decrease by \(1\). One implication of this is that total number of shards \(F_A + F_B\) decreases by \(2\) each time. Since \(N\) is initially a positive odd integer, this means that the sequence of shards will always be reduced to a single shard after enough fusing operations, as long as they can all be performed safely. A more interesting implication is that \(F_A - F_B\) remains constant between operations. Since \(F_A - F_B\) must be equal to either \(1\) or \(-1\) when there's one shard remaining, we must also have \(|F_A - F_B| = 1\) in the initial sequence in order for that final state to be achievable.

So far, we've shown that the answer must be *"N"* if \(|F_A - F_B| \neq 1\). The remaining question is whether the answer is always *"Y"* if \(|F_A - F_B| = 1\). The only way it could be *"N"* is if it were impossible to perform a fusing operation at any point while there are three or more shards. This is only impossible if all shards are the same colour (as there must otherwise be at least one consecutive triple of shards not all sharing the same colour), which cannot ever be the case if \(N \geq 3\) and \(|F_A - F_B| = 1\) (as we must have \(F_A \geq 1\) and \(F_B \geq 1\)).

Therefore, we have only to loop over the shards in \(O(N)\) time to compute \(F_A\) and \(F_B\), and then check whether or not \(|F_A - F_B| = 1\).


Code: // Alchemy
// 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 100001

int N;
char P[LIM];

bool ProcessCase()
{
  // input
  Read(N);
  scanf("%s", P);
  // count difference between counts of As and Bs
  int i, c = 0;
  Fox(i, N)
    c += (P[i] == 'A' ? 1 : -1);
  // absolute difference must be equal to 1
  return(Abs(c) == 1);
}

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