PHILOSOPHER - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pratik
Tester: Ankur
Editorialist: Pratik

DIFFICULTY:

EASY.

PREREQUISITES:

Strings

PROBLEM:

Chef and his wife Chevy are alchemists in search of the legendary Philosopher’s Stone. The Philosopher’s Stone is a very powerful substance which is believed to have the power to transmute precious metals, stones and even lives of living beings. Chef wishes to use the stone to restore his son Jim’s body to its original form following a terrifying accident in their lab.

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, Chef 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 encyclopaedic knowledge of alchemy, Chef 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 Ci 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 neutralise 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 Chef determine whether or not it’s possible to get to that point and hopefully save his son Jim, without causing any rebound explosions along the way.

EXPLANATION:

You have to just arrange data in such a way that no A should come next and before to B in pair of
three… it simply mean that the count of A should be equal to count of B+1 or count of B is equal to count of A+1. if this condition satisfied you will print Y otherwise N.

Setter's Solution

#include <bits/stdc++.h>
using namespace std;

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int t;
cin>>t;

while(t--)
{
     int n;
     string s;
     cin>>n>>s;

     int x=count(s.begin(),s.end(),'A'); 
     int y=count(s.begin(),s.end(),'B');

     if(x==(y+1) || y==(x+1))cout<<"Y"<<endl;
     else cout<<"N"<<endl;
}

return 0;

}

Tester's Solution

t=int(input())
for i in range(t):
N=int(input())
c=input()

countA=0
countB=0
for j in range(N):
    if(c[j]=='A'):
        countA+=1
    else:
        countB+=1
if(abs(countB - countA))==1:
    print('Y')
else:
    print('N')